LRU cache for ~=

Fawzi Mohamed fmohamed at mac.com
Mon Oct 19 13:24:15 PDT 2009


On 2009-10-19 21:53:53 +0200, Andrei Alexandrescu 
<SeeWebsiteForEmail at erdani.org> said:

> dsimcha wrote:
>> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
>>> dsimcha wrote:
>>>> 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.
>>> Let me stress a point harder that I think I expressed poorly:
>>> The LRU cache stores the capacity of a given slice given _BOTH_ the
>>> slice's left and right bounds. If you later come with a slice that has
>>> only one correct bound, the LRU doesn't care about it. That's the safety
>>> tidbit.
>>> Andrei
>> 
>> I think I get it now, although it's very conservative.
> 
> That's why we need experimentation. My gut tells me that linear search 
> will scram through 8 elements real fast, and if there's something in 
> the cache it will almost always be in a top position. Also, I think the 
> LRU will solve all cases that matter.

yes you are probably right

> 
>> One more question:  Is
>> this going to take the place of ArrayBuilder or be inaddition?  The LRU 
>> is a good
>> hack to preserve syntactic elegance and ease of use, but it's somewhat 
>> of a kludge
>> nonetheless and I'd ideally still like to see a real ArrayBuilder with full
>> array-like semantics if T[new] is definitely out.
> 
> Ideally we'd be able to render ArrayBuilder/Appender unnecessary. I 
> think there is a need for a UniqueArray, but that's only loosely 
> related.

a library array knowing its capacity is still useful I think.

Fawzi




More information about the Digitalmars-d mailing list