Created
May 17, 2012 09:46
-
-
Save rklemme/2717818 to your computer and use it in GitHub Desktop.
Lazy cache with as few locking as possible
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package clj; | |
import java.util.concurrent.ConcurrentHashMap; | |
import java.util.concurrent.ConcurrentMap; | |
/** | |
* The cache works with as few locking as possible. Lookup is done in two steps | |
* on cache miss: | |
* <ol> | |
* <li>On a cache miss a retriever is inserted into the cache which will obtain | |
* the value synchronized from a {@link Calculator}.</li> | |
* <li>Once calculation has finished a simple lock free reference to the value | |
* replaces the retriever in the cache and the value is returned.</li> | |
* </ol> | |
* | |
* @author robert klemme | |
* | |
* @param <K> | |
* key type | |
* @param <V> | |
* value type | |
*/ | |
public final class LazyCache<K, V> { | |
/** | |
* Calculate values from given keys. | |
* | |
* @param <K> | |
* key type | |
* @param <V> | |
* value type | |
*/ | |
public interface Calculator<K, V> { | |
V get(K key); | |
} | |
/** | |
* Obtain a value. | |
* | |
* @param <V> | |
* value type. | |
*/ | |
private interface Reference<V> { | |
V get(); | |
} | |
/** | |
* Stupid simple reference which only hands out a fixed value all the time | |
* without synchronization. | |
* | |
* @param <V> | |
* value type. | |
*/ | |
private static final class Ref<V> implements Reference<V> { | |
private final V val; | |
public Ref(V val) { | |
this.val = val; | |
} | |
@Override | |
public V get() { | |
return val; | |
} | |
} | |
/** Mapping from keys to objects which yield values. */ | |
private final ConcurrentMap<K, Reference<V>> map = new ConcurrentHashMap<K, Reference<V>>(); | |
/** User provided. */ | |
private final Calculator<? super K, ? extends V> calc; | |
/** | |
* Create a cache. | |
* | |
* @param calc | |
* user must provide a reasonable implementation, not | |
* <code>null</code>. | |
*/ | |
public LazyCache(final Calculator<? super K, ? extends V> calc) { | |
if (calc == null) | |
throw new NullPointerException(); | |
this.calc = calc; | |
} | |
/** | |
* Get a value from the cache. The value might have to be calculated. | |
* | |
* @param key | |
* lookup key. | |
* @return value, might even be <code>null</code> depending on algorithm. | |
*/ | |
public V get(final K key) { | |
Reference<V> ref = map.get(key); | |
if (ref == null) { | |
// miss | |
ref = new Reference<V>() { | |
private V val; | |
private boolean here = false; // superfluous but explicit | |
@Override | |
public synchronized V get() { | |
if (!here) { | |
val = calc.get(key); | |
here = true; | |
// next time lock free access: | |
Reference<V> x = map.put(key, new Ref<V>(val)); | |
assert x == this; | |
} | |
return val; | |
} | |
}; | |
final Reference<V> old = map.putIfAbsent(key, ref); | |
if (old != null) | |
ref = old; // someone else was faster | |
} | |
return ref.get(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment