11:23 a.m.
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/o...
[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;
}
}