LRU cache for ~=

[Andrei Alexandrescu]

grauzone wrote:
> Andrei Alexandrescu wrote:
>> I was thinking of solving these issues by keeping an LRU (Least 
>> Recently Used) cache inside the implementation of ~=. The LRU would 
>> only have a few entries (4-8) and would store the parameters of the 
>> last ~= calls, and their cached capacities.
> 
> Sounds like a bad hack, but at least it would solve the issue about 
> overwritten slices.
> 
> But for some uses of array appending, you had to use a library based 
> "Appender" (or whatever you have in Phobos 2):
> 
> class Something {
>    T[] data;
>    void add(T x) {
>      data ~= x; //chances that data are in the cache are minimal
>    }
> }
> 
> There's no "cache locality" or anything, but obviously you still would 
> like to have efficient appender behavior.

Why is there no cache locality?

> Also look at this:
> 
> string[] t;
> t ~= somefunction();
> t ~= someotherfunction();
> 
> Chances are high that those functions will remove "t" from the cache, 
> and it would all be inefficient again. Nothing solved!

Why are there chances those functions will remove "t" from the cache? 
For it to become a performance problem, there must be a loop with nine 
or more round-robin appends. When that does happen, yes, appends will 
become slower. (We may be able to make that better by using random 
eviction.)

> Now you could try to make the cache function local to solve this issue. 
> Whenever a function contains the ~= operator, the compiler allocates a 
> "cache" struct, and the ~= operator passes a hidden pointer to it to the 
> runtime.
> 
> But that wouldn't work if you want pass slices to other functions and to 
> append to them (but it would still be safe, I guess?).
> 
> Looks like these performance hacks just don't work out.

Caches have a long and solid history of working. You'd have a very hard 
time convincing me that a cache that directly addresses a performance 
problem is a hack.

> It'd be so much 
> simpler to make "a~=b;" equivalent to "a=a~b;". Then there's no 
> "mystery" about the performance of the ~= operator. You can explain 
> everyone: "yes, this allocates; if you want performance, use 
> ArrayAppender". Hey, you could alias this ArrayAppender type to 
> something like T[new] to make it feel more natural. But then, we're at 
> the beginning again.

I think making ~= faster is worth pursuing.


Andrei