[
https://issues.apache.org/jira/browse/SOLR-665?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12617639#action_12617639
]
funtick edited comment on SOLR-665 at 7/28/08 6:28 PM:
-----------------------------------------------------------
This is extremely simple Concurrent LRU, I spent an hour to create it; it is
based on ConcurrentHashMap. I don't use java.util.concurrent.locks, and I am
trying to focus on _requirements only_ avoiding implementing unnecessary
methods of Map interface (so that I am not following _contract_ ;) very sorry!)
{code}
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentLRU<K, V> {
protected ConcurrentHashMap<K, ValueWrapper<V>> map;
protected int maxEntries;
public ConcurrentLRU(int maxEntries) {
map = new ConcurrentHashMap<K, ValueWrapper<V>>();
this.maxEntries = maxEntries;
}
public V put(K key, V value) {
ValueWrapper<V> wrapper = map.put(key, new
ValueWrapper<V>(value));
checkRemove();
return value;
}
void checkRemove() {
if (map.size() <= maxEntries)
return;
Map.Entry<K, ValueWrapper<V>> eldestEntry = null;
for (Map.Entry<K, ValueWrapper<V>> entry : map.entrySet()) {
long popularity = entry.getValue().popularity;
if (eldestEntry == null ||
eldestEntry.getValue().popularity > popularity) {
eldestEntry = entry;
}
}
map.remove(eldestEntry.getKey(), eldestEntry.getValue());
}
public V get(Object key) {
ValueWrapper<V> wrapper = map.get(key);
return wrapper == null ? null : wrapper.getValue();
}
public final static class ValueWrapper<V> {
static volatile long popularityCounter;
volatile long popularity;
V value;
ValueWrapper(V value) {
this.value = value;
popularity = popularityCounter++;
}
public boolean equals(Object o) {
if (!(o instanceof ValueWrapper)) {
return false;
}
return (value == null ? ((ValueWrapper) o).value ==
null : value.equals(((ValueWrapper) o).value));
}
public int hashCode() {
return value.hashCode();
}
public V getValue() {
popularity = popularityCounter++;
return value;
}
}
}
{code}
P.S.
Do we need to synchronize put() or checkRemove()? The only hypothetical problem
is OutOfMemoryException. But it is just first draft, very simplified... we do
not need to sort array.
was (Author: funtick):
This is extremely simple Concurrent LRU, I spent an hour to create it; it
is based on ConcurrentHashMap. I don't use java.util.concurrent.locks, and I am
trying to focus on _requirements only_ avoiding implementing unnecessary
methods of Map interface (so that I am not following _contract_ ;) very sorry!)
{code}
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentLRU<K, V> {
protected ConcurrentHashMap<K, ValueWrapper<V>> map;
protected int maxEntries;
public ConcurrentLRU(int maxEntries) {
map = new ConcurrentHashMap<K, ValueWrapper<V>>();
this.maxEntries = maxEntries;
}
public V put(K key, V value) {
ValueWrapper<V> wrapper = map.put(key, new
ValueWrapper<V>(value));
checkRemove();
return value;
}
void checkRemove() {
if (map.size() <= maxEntries)
return;
Map.Entry<K, ValueWrapper<V>> eldestEntry = null;
for (Map.Entry<K, ValueWrapper<V>> entry : map.entrySet()) {
long popularity = entry.getValue().popularity;
if (eldestEntry == null ||
eldestEntry.getValue().popularity > popularity) {
eldestEntry = entry;
}
}
map.remove(eldestEntry.getKey(), eldestEntry.getValue());
}
public V get(Object key) {
ValueWrapper<V> wrapper = map.get(key);
return wrapper == null ? null : wrapper.getValue();
}
public final static class ValueWrapper<V> {
static volatile long popularityCounter;
volatile long popularity;
V value;
ValueWrapper(V value) {
this.value = value;
popularity = popularityCounter++;
}
public boolean equals(Object o) {
if (!(o instanceof ValueWrapper)) {
return false;
}
return (value == null ? ((ValueWrapper) o).value ==
null : value.equals(((ValueWrapper) o).value));
}
public int hashCode() {
return value.hashCode();
}
public V getValue() {
popularity = popularityCounter++;
return value;
}
}
}
{code}
> FIFO Cache (Unsynchronized): 9x times performance boost
> -------------------------------------------------------
>
> Key: SOLR-665
> URL: https://issues.apache.org/jira/browse/SOLR-665
> Project: Solr
> Issue Type: Improvement
> Affects Versions: 1.3
> Environment: JRockit R27 (Java 6)
> Reporter: Fuad Efendi
> Attachments: FIFOCache.java
>
> Original Estimate: 672h
> Remaining Estimate: 672h
>
> Attached is modified version of LRUCache where
> 1. map = new LinkedHashMap(initialSize, 0.75f, false) - so that
> "reordering"/true (performance bottleneck of LRU) is replaced to
> "insertion-order"/false (so that it became FIFO)
> 2. Almost all (absolutely unneccessary) synchronized statements commented out
> See discussion at
> http://www.nabble.com/LRUCache---synchronized%21--td16439831.html
> Performance metrics (taken from SOLR Admin):
> LRU
> Requests: 7638
> Average Time-Per-Request: 15300
> Average Request-per-Second: 0.06
> FIFO:
> Requests: 3355
> Average Time-Per-Request: 1610
> Average Request-per-Second: 0.11
> Performance increased 9 times which roughly corresponds to a number of CPU in
> a system, http://www.tokenizer.org/ (Shopping Search Engine at Tokenizer.org)
> Current number of documents: 7494689
> name: filterCache
> class: org.apache.solr.search.LRUCache
> version: 1.0
> description: LRU Cache(maxSize=10000000, initialSize=1000)
> stats: lookups : 15966954582
> hits : 16391851546
> hitratio : 0.102
> inserts : 4246120
> evictions : 0
> size : 2668705
> cumulative_lookups : 16415839763
> cumulative_hits : 16411608101
> cumulative_hitratio : 0.99
> cumulative_inserts : 4246246
> cumulative_evictions : 0
> Thanks
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
