LRU cache for ~=

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Mon Oct 19 12:27:00 PDT 2009


dsimcha wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s 
> article
>> 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
> 
> 1.  I assume the LRU cache would be thread-local, so no lock would be
>  necessary?

Yes.

> 2.  I don't understand how this solves the safety problem:

It's rather subtle. I'd figured it out in the morning and forgot it by
the time I explained to Walter.

> // foo lives on the heap b/c we've idup'd it. string foo = "This is 
> only a test.".idup; string bar = foo[0..4]; bar ~= " is _not "; 
> writeln(foo);  // prints "This is _not a test."

Upon the call to ~=, bar is not in the LRU cache so ~= conservatively 
reallocates it.

As a rule of thumb (which takes care of the subtler issues): if a
growing slice is not found in the LRU cache, it will always be
conservatively reallocated. This is exactly because you don't know
whether that slice was reduced from a larger slice.

> Having access to the capacity in an LRU cache doesn't help if I 
> understand it correctly.
> 
> 3.  I'm pretty familiar with these parts of druntime and would 
> probably be willing to do the implementation after I understand a few
>  details of it a little better.

That would be awesome!!!


Andrei



More information about the Digitalmars-d mailing list