LRU cache for ~=

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Mon Oct 19 14:58:10 PDT 2009


Jason House wrote:
> 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.
> 
> Shouldn't it be MRU (Most Recently Used)?

Yes. LRU would be the eviction strategy.

> I assume ~= will be disallowed for shared arrays?

I think so.

> Will all arrays overallicate when created in order to allow efficient
> appending?

Upon the first append.

> I feel like bolting on ~= to slices gives mediocre performance and a
> lot of gotchas.

You may be right about the gotchas, but you better produce some numbers 
wrt performance.

> Some users may expect slices to be reference copied
> arrays and want to see appended data in other slices. Some may get
> away with mutating the array in the MRU or a slice and seeing the
> changes, only to get bitten later. A separate type really makes more
> sense to me...

Making ~= work well for slices does not preclude creating a distinct 
library type.


Andrei



More information about the Digitalmars-d mailing list