LRU cache for ~=

dsimcha dsimcha at yahoo.com
Mon Oct 19 12:10:37 PDT 2009


== 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?
2.  I don't understand how this solves the safety problem:

// 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."

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.



More information about the Digitalmars-d mailing list