LRUCache - a simple least recently used cache

[Bill Baxter]

Charles D Hixson wrote:
> 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..
>>
> 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.
> 2)  Whenever the cache is cleared, all the cache nodeId's are decreased 
> by the minimum nodeId (so the new minimum is zero...or one, I'd need to 
> check again.  This should decrease the rate at which the maximum nodeId 
> grows.
> 

I don't know why you chose to go with a short, but I have had situations 
in the past where using a short instead of an int had significantly 
worse performance.  In my case it was a big array of shorts vs a big 
array of ints, so probably there was extra alignment mojo that had to 
happen to fetch data from the short array into a register and then put 
it back.  But anyway CPUs seem to like working on chunks of 32-bits 
better than 16.  You might try making it an int just to see how it performs.

--bb