LRU cache for ~=

[Andrei Alexandrescu]

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.

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


Andrei