LRU cache for ~=

[Chris Nicholson-Sauls]

Andrei Alexandrescu wrote:
> I just wrote this to Sean and Walter and subsequently discussed it with 
> Walter. Walter thinks this should work. Does anyone have the time and 
> inclination to test this out? It would involve hacking into druntime's 
> implementation of ~= (I'm not sure what the function name is). I'd 
> really appreciate this; I'm overloaded as it is.
> 
> ==================
> 
> In wake of the recent demise of T[new], I was thinking of finding ways 
> of making ~= efficient for T[].
> 
> Currently ~= is slow because accessing GC.sizeOf(void*) acquires a 
> global lock and generally must figure out a lot of things about the 
> pointer to make a decision.
> 
> Also, ~= is dangerous because it allows slices to stomp over other slices.
> 
> 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.
> 
> So whenever code calls arr ~= b, the LRU is searched first. If the 
> system finds "arr" (both bounds) in the LRU, that means the cached 
> capacity is correct and can solve the matter without an actual trip to 
> the GC at all! Otherwise, do the deed and cache the new slice and the 
> new capacity.
> 
> This also solves the lack of safety: if you request a growth on an array 
> you just grew, it's impossible  to have a valid slice beyond that array.
> 
> This LRU would allow us to keep the slice API as it currently is, and 
> also at excellent efficiency.
> 
> What do you think?
> 
> 
> Andrei

Its an interesting idea, and if I have time tonight I'll take a crack at it.  For those 
others who may, the function you care about is "_d_arrayappendcT" in compiler/dmd/lifetime.

-- Chris Nicholson-Sauls