[infinispan-dev] Faster LRU

[Dan Berindei]

On Tue, Jul 5, 2011 at 7:23 PM, Vladimir Blagojevic <vblagoje at redhat.com> wrote:
> Hey guys,
>
> In the past few days I've look around how to squeeze every bit of
> performance out of BCHM and particularly our LRU impl. What I did not
> like about current LRU is that a search for an element in the queue is
> not constant time operation but requires full queue traversal if we need
> to find an element[1].
>
> It would be be particularly nice to have a hashmap with a constant cost
> for look up operations. Something like LinkedHashMap. LinkedHashMap
> seems to be a good container for LRU as it provides constant time lookup
> but also a hook, a callback call for eviction of the oldest entry in the
> form of removeEldestEntry callback. So why not implement our segment
> eviction policy by using a LinkedHashMap [2]?
>

+1 Vladimir, I had a similar idea to implement a BCHM segment entirely
using a single LinkedHashMap - obviously that requires a lot more work
to integrate with the existing BCHM then using a LHM inside the
eviction policy, but it should also be more memory efficient.

> I've seen about 50% performance increase for smaller caches (100K) and
> even more for larger and more contended caches - about 75% increase.
> After this change BCHM performance was not that much worse than CHM and
> it was faster than synchronized hashmap.
>
> Should we include this impl as FAST_LRU as I would not want to remove
> current LRU just yet? We have to prove this one is correct and that it
> does not have have any unforeseen issues.
>

I would definitely remove the old LRU, it's much harder to understand
because of the batching and the JDK already has tests to guarantee
that LinkedHashMap is correct.

One idea for testing I was discussing with Galder on my pull request's
page was to simulate a real cache workload, with get misses triggering
a put and also a small delay, in order to evaluate how good an
eviction policy is at keeping the most used keys in.

We definitely need to *some* testing for this, we can't afford to wait
for another community member to come in a year's time and prove to us
that we're rubbish :)

Dan