khaines / enigo.com wrote:
> Well, let me tell you what I did.
>
> The mixin is used to turn the desired class into something that can be a
> linked list node.  It's a neat idea, but I don't like having to pollute my
> namespace, and it breaks down messily in some instances (try using the
> cache to cache fixnums...).
>
> So, I took a couple ideas from the implementation and built a doubly
> linked list implementation that doesn't need the mixin and also provides
> fast random access by using a hash in conjunction with the list.  So data
> access, modification, inserts, and deletes are all pretty fast, and no
> penalty is paid for having large numbers of items in the cache.
>
> I then used this as the basis for an LRU cache implementation.  Mine will
> also expire elements based on age.  So, for example, a cache with a max
> ttl of 1800 seconds will expire elements that haven't been accessed in
> more than half an hour, even if the cache isn't full.  I pay a small cost
> for this capability, though, in terms of speed, so it may not be something
> you would want in your implementation.
>
> The cache should be threadsafe, and I also have a capability in mine for
> finalizers -- blocks of code that are invoked immediately before something
> is expired from the cache -- which also does not come for free.
>
> I can happily make a version of the cache which doesn't include the TTL
> stuff or the finalizers, though, if you want it.  Note that the mixin
> approach of your current LRU cache definitely makes for the fastest cache,
> though, so I guess it depends on what one is selecting for.  I'm using a
> modified version of your LRUCache (I added finalizer support) in a place
> where I need a basic LRU cache, can live with the mixin, and just want it
> to be as fast as possible.

Well, I think those are useful features. It would be nice if it could
be implemented in such a way that the TTL and finializers were options
--but zero overhead when not used. But even if that's not reasonable,
then a second type of LRUCache per your implementation is still welcome
in Facets.

> You might also be able to use the raw linked list?

Yes!

T.