LRUCache - a simple least recently used cache

[renoX]

Charles D Hixson a écrit :
> renoX wrote:
>> Charles D Hixson a écrit :
>>> In the hopes that someone find this useful:
>>> http://www.prowiki.org/wiki4d/wiki.cgi?CharlesHixson
>>>
>>> This particular version presumes D2.x code, but I think the 
>>> adjustments are trivial for D1.x.
>>
>> I think that there is a flaw in your code: the access counter is a 
>> ushort (16bit value) and is incremented each time you access an 
>> element in the cache: it can overflow quickly and will wrap around..
>>
>> This means that recently used elements could have a _nodeId smaller 
>> than nodes used less recently, which means that the overflow handling 
>> code will drop the wrong elements..
>>
>> This may not be the case in your usage, but this is either a bug or at 
>> least a pretty big restriction in the usage which should be clearly 
>> indicated.
>>
>>
>> Regards,
>> renoX
> 
> Well, two things:
> 1)  This code isn't really adapted for large sets of data.  If you want 
> that, you'd better hand optimize it for your intended application.

I'm not talking about a large set of data, just about a program which 
runs for a long time and/or which make heavy usage of the data in the 
cache: each call to 'contains' or 'opIndex' increase maxNode so it could 
overflow quite quickly (an ushort isn't that big).

> Any suggestions for a quick and simple way to do this?

Just make the access counter 32bit, it should be enough for a 'normal' 
program (not an Apache style program though).

> Would it be reasonable to arbitrarily renumber everything in the cache 
> serially (i.e., without considering the current nodeIds) whenever the 
> maximum nodeId started to approach ushort.max?  (That's the direction 
> that I'm leaning in...but I haven't decided whether or not it's 
> reasonable.)

I'm not an expert in D's but I think that an array of
struct Node{ Key key; Body bdy; ushort _nodeId; } or an array of
struct Node{ Key key; Body bdy; uint   _nodeId; } have exactly the same 
size due to the padding..

And maybe on x86-64, you could use ulong without increasing the size of 
the array..

Could someone confirm/infirm?
For me, key and bdy are reference, so they have the same size as 
pointers, am I right?

Regards,
renoX