LRU cache for ~=

Robert Jacques sandford at jhu.edu
Tue Oct 20 07:37:40 PDT 2009


On Tue, 20 Oct 2009 10:14:52 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:
> Steven Schveighoffer wrote:
>> On Mon, 19 Oct 2009 14:51:32 -0400, Andrei Alexandrescu  
>> <SeeWebsiteForEmail at erdani.org> 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.
>>>
>>> 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?
>>>
>>  This is a very good idea.  Incidentally, you only need the upper bound  
>> location, the beginning location is irrelevant, since you don't grow  
>> down.
>
> Awesome, didn't think of that. So now more cases are caught:
>
> auto a = new int[100];
> a ~= 42;
> a = a[50 .. $];
> a ~= 52;
>
> That wouldn't have worked with my original suggestion, but it does work  
> safely with yours.
>
>> What do you do in the case where the memory was recycled?  Does a GC  
>> collection cycle clean out the cache as well?
>
> As you saw, there was some discussion about that as well.
>
>> This is better than my two previous ideas.  The only drawback I see is  
>> if you have many threads doing appending, or you are appending more  
>> than 8 arrays at once in a round-robin fashion, you would lose all the  
>> benefit (although it shouldn't affect correctness).  At that point  
>> however, you'd have to ask yourself why you aren't using a specialized  
>> appender type or function.
>
> Yah. As I suspect a lot of code is actually doing round-robin naturally,  
> I'm considering using a random eviction strategy. That way performance  
> will degrade smoother. A more advanced algorithm would use introspection  
> to choose dynamically between LRU and random.
>
>
> Andrei

So you want to synchronize the ~= function? I thought the LRU would be  
thread local and therefore independent of these issues, as well as being  
faster. And if the LRU isn't thread-local, then why not make it part of  
the GC? It would both be more general and much simpler/cleaner to  
implement.



More information about the Digitalmars-d mailing list