LRU cache for ~=

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Mon Oct 19 12:28:15 PDT 2009


Leandro Lucarella wrote:
> Andrei Alexandrescu, el 19 de octubre a las 13:51 me escribiste:
>> 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?
> 
> I think this is moving in the wrong direction. It's a patch, not
> a solution. And this makes dynamic arrays more coupled with the way the GC
> works. I think the GC shouldn't even provide a sizeOf(void*), we should
> move in that direction, removing restrictions to the GC instead of
> enforcing the current ones; at lest if the goal is to eventually have
> a better GC (a copying GC doesn't even have to store the size of the
> cell, for example).

The LRU doesn't need GC.sizeOf. It could always conservatively 
reallocate whenever in doubt.

> I hope you eventually realize that you are complicating things much more
> than necessary.

I actually did a couple of days ago :o).


Andrei



More information about the Digitalmars-d mailing list