[infinispan-dev] Faster LRU

Alex Kluge java_kluge at yahoo.com
Tue Jul 5 12:47:38 EDT 2011


Hi,

  I have a completely in-line limit on the cache entries built on a clock cache that is an approximation to an LRU cache, and is extremely fast (O(1)). It is not a strick LRU, but chooses a not recently used item for removal. I'll provide some more details soon.

  I'm not sure how far along you are, as some of this is in the future tense, and some in the past. But I'll dig up this code - it's been a while since I worked on the cache. :)

                                                                       Alex

--- On Tue, 7/5/11, Vladimir Blagojevic <vblagoje at redhat.com> wrote:

From: Vladimir Blagojevic <vblagoje at redhat.com>
Subject: [infinispan-dev] Faster LRU
To: "infinispan -Dev List" <infinispan-dev at lists.jboss.org>
Date: Tuesday, July 5, 2011, 11:23 AM

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]?

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.

Let me know what you think!

Vladimir








[1] 
https://github.com/infinispan/infinispan/blob/master/core/src/main/java/org/infinispan/util/concurrent/BoundedConcurrentHashMap.java#L467

[2] Source code snippet for LRU in BCHM.


static final class LRU<K, V> extends LinkedHashMap<HashEntry<K,V>, V> 
implements EvictionPolicy<K, V> {
       /** The serialVersionUID */
       private static final long serialVersionUID = -6627108081544347068L;

       private final ConcurrentLinkedQueue<HashEntry<K, V>> accessQueue;
       private final Segment<K,V> segment;
       private final int maxBatchQueueSize;
       private final int trimDownSize;
       private final float batchThresholdFactor;
       private final Set<HashEntry<K, V>> evicted;

       public LRU(Segment<K,V> s, int capacity, float lf, int 
maxBatchSize, float batchThresholdFactor) {
          super((int)(capacity*lf));
          this.segment = s;
          this.trimDownSize = (int)(capacity*lf);
          this.maxBatchQueueSize = maxBatchSize > MAX_BATCH_SIZE ? 
MAX_BATCH_SIZE : maxBatchSize;
          this.batchThresholdFactor = batchThresholdFactor;
          this.accessQueue = new ConcurrentLinkedQueue<HashEntry<K, V>>();
          this.evicted = new HashSet<HashEntry<K, V>>();
       }

       @Override
       public Set<HashEntry<K, V>> execute() {
          Set<HashEntry<K, V>> evictedCopy = new HashSet<HashEntry<K, V>>();
          for (HashEntry<K, V> e : accessQueue) {
             put(e, e.value);
          }
          evictedCopy.addAll(evicted);
          accessQueue.clear();
          evicted.clear();
          return evictedCopy;
       }



       @Override
       public Set<HashEntry<K, V>> onEntryMiss(HashEntry<K, V> e) {
          return Collections.emptySet();
       }

       /*
        * Invoked without holding a lock on Segment
        */
       @Override
       public boolean onEntryHit(HashEntry<K, V> e) {
          accessQueue.add(e);
          return accessQueue.size() >= maxBatchQueueSize * 
batchThresholdFactor;
       }

       /*
        * Invoked without holding a lock on Segment
        */
       @Override
       public boolean thresholdExpired() {
          return accessQueue.size() >= maxBatchQueueSize;
       }

       @Override
       public void onEntryRemove(HashEntry<K, V> e) {
          remove(e);
          // we could have multiple instances of e in accessQueue; 
remove them all
          while (accessQueue.remove(e)) {
             continue;
          }
       }

       @Override
       public void clear() {
          super.clear();
          accessQueue.clear();
       }

       @Override
       public Eviction strategy() {
          return Eviction.LRU;
       }

       protected boolean removeEldestEntry(Entry<HashEntry<K,V>,V> eldest){
          HashEntry<K, V> evictedEntry = eldest.getKey();
          
segment.evictionListener.onEntryChosenForEviction(evictedEntry.value);
          segment.remove(evictedEntry.key, evictedEntry.hash, null);
          evicted.add(evictedEntry);
          return size() > trimDownSize;
       }
    }
_______________________________________________
infinispan-dev mailing list
infinispan-dev at lists.jboss.org
https://lists.jboss.org/mailman/listinfo/infinispan-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/infinispan-dev/attachments/20110705/d91db706/attachment.html 


More information about the infinispan-dev mailing list