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 <vblag...@redhat.com> wrote: From: Vladimir Blagojevic <vblag...@redhat.com> Subject: [infinispan-dev] Faster LRU To: "infinispan -Dev List" <infinispan-dev@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@lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev
_______________________________________________ infinispan-dev mailing list infinispan-dev@lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev