<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">Hi,<br><br> 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.<br><br> 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. :)<br><br>
Alex<br><br>--- On <b>Tue, 7/5/11, Vladimir Blagojevic <i><vblagoje@redhat.com></i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>From: Vladimir Blagojevic <vblagoje@redhat.com><br>Subject: [infinispan-dev] Faster LRU<br>To: "infinispan -Dev List" <infinispan-dev@lists.jboss.org><br>Date: Tuesday, July 5, 2011, 11:23 AM<br><br><div class="plainMail">Hey guys,<br><br>In the past few days I've look around how to squeeze every bit of <br>performance out of BCHM and particularly our LRU impl. What I did not <br>like about current LRU is that a search for an element in the queue is <br>not constant time operation but requires full queue traversal if we need <br>to find an element[1].<br><br>It would be be particularly nice to have a hashmap with a constant cost <br>for look up operations. Something like LinkedHashMap. LinkedHashMap <br>seems to be a good
container for LRU as it provides constant time lookup <br>but also a hook, a callback call for eviction of the oldest entry in the <br>form of removeEldestEntry callback. So why not implement our segment <br>eviction policy by using a LinkedHashMap [2]?<br><br>I've seen about 50% performance increase for smaller caches (100K) and <br>even more for larger and more contended caches - about 75% increase. <br>After this change BCHM performance was not that much worse than CHM and <br>it was faster than synchronized hashmap.<br><br>Should we include this impl as FAST_LRU as I would not want to remove <br>current LRU just yet? We have to prove this one is correct and that it <br>does not have have any unforeseen issues.<br><br>Let me know what you think!<br><br>Vladimir<br><br><br><br><br><br><br><br><br>[1] <br><a href="https://github.com/infinispan/infinispan/blob/master/core/src/main/java/org/infinispan/util/concurrent/BoundedConcurrentHashMap.java#L467"
target="_blank">https://github.com/infinispan/infinispan/blob/master/core/src/main/java/org/infinispan/util/concurrent/BoundedConcurrentHashMap.java#L467</a><br><br>[2] Source code snippet for LRU in BCHM.<br><br><br>static final class LRU<K, V> extends LinkedHashMap<HashEntry<K,V>, V> <br>implements EvictionPolicy<K, V> {<br> /** The serialVersionUID */<br> private static final long serialVersionUID = -6627108081544347068L;<br><br> private final ConcurrentLinkedQueue<HashEntry<K, V>> accessQueue;<br> private final Segment<K,V> segment;<br> private final int maxBatchQueueSize;<br> private final int trimDownSize;<br> private final float batchThresholdFactor;<br> private
final Set<HashEntry<K, V>> evicted;<br><br> public LRU(Segment<K,V> s, int capacity, float lf, int <br>maxBatchSize, float batchThresholdFactor) {<br> super((int)(capacity*lf));<br> this.segment = s;<br> this.trimDownSize = (int)(capacity*lf);<br> this.maxBatchQueueSize = maxBatchSize > MAX_BATCH_SIZE ? <br>MAX_BATCH_SIZE : maxBatchSize;<br> this.batchThresholdFactor = batchThresholdFactor;<br> this.accessQueue = new ConcurrentLinkedQueue<HashEntry<K, V>>();<br> this.evicted = new HashSet<HashEntry<K, V>>();<br> }<br><br> @Override<br> public
Set<HashEntry<K, V>> execute() {<br> Set<HashEntry<K, V>> evictedCopy = new HashSet<HashEntry<K, V>>();<br> for (HashEntry<K, V> e : accessQueue) {<br> put(e, e.value);<br> }<br> evictedCopy.addAll(evicted);<br> accessQueue.clear();<br> evicted.clear();<br> return evictedCopy;<br> }<br><br><br><br> @Override<br> public Set<HashEntry<K, V>> onEntryMiss(HashEntry<K, V> e) {<br> return Collections.emptySet();<br> }<br><br>
/*<br> * Invoked without holding a lock on Segment<br> */<br> @Override<br> public boolean onEntryHit(HashEntry<K, V> e) {<br> accessQueue.add(e);<br> return accessQueue.size() >= maxBatchQueueSize * <br>batchThresholdFactor;<br> }<br><br> /*<br> * Invoked without holding a lock on Segment<br> */<br> @Override<br> public boolean thresholdExpired() {<br> return accessQueue.size() >= maxBatchQueueSize;<br> }<br><br> @Override<br> public void
onEntryRemove(HashEntry<K, V> e) {<br> remove(e);<br> // we could have multiple instances of e in accessQueue; <br>remove them all<br> while (accessQueue.remove(e)) {<br> continue;<br> }<br> }<br><br> @Override<br> public void clear() {<br> super.clear();<br> accessQueue.clear();<br> }<br><br> @Override<br> public Eviction strategy() {<br> return Eviction.LRU;<br> }<br><br> protected boolean
removeEldestEntry(Entry<HashEntry<K,V>,V> eldest){<br> HashEntry<K, V> evictedEntry = eldest.getKey();<br> <br>segment.evictionListener.onEntryChosenForEviction(evictedEntry.value);<br> segment.remove(evictedEntry.key, evictedEntry.hash, null);<br> evicted.add(evictedEntry);<br> return size() > trimDownSize;<br> }<br> }<br>_______________________________________________<br>infinispan-dev mailing list<br><a ymailto="mailto:infinispan-dev@lists.jboss.org" href="/mc/compose?to=infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a><br><a href="https://lists.jboss.org/mailman/listinfo/infinispan-dev" target="_blank">https://lists.jboss.org/mailman/listinfo/infinispan-dev</a><br></div></blockquote></td></tr></table>