com.aliasi.util
Class FastCache<K,V>

java.lang.Object
  extended by java.util.AbstractMap<K,V>
      extended by com.aliasi.util.FastCache<K,V>
Type Parameters:
K - the type of keys in the map
V - the type of values in the map
All Implemented Interfaces:
Serializable, Map<K,V>

public class FastCache<K,V>
extends AbstractMap<K,V>
implements Serializable

A FastCache is a map implemented with soft references, optimistic copy-on-write updates, and approximate count-based pruning. It is intended for scalable multi-threaded caches. It sacrifices recall of mappings for speed of put and get operations along with conservative memory guarantees.

Note:The class HardFastCache is nearly identical to this class, but with no soft references around hash buckets.

The basis of the cache is a fixed-size hash map, based on values returned by objects' hashCode() and equals(Object) methods.

The map entries in the hash map are stored in buckets held by soft references. Thus entries in the mapping may be garbage collected. In the implementation, whole hash buckets are collected, which is safe and highly efficient but may require some additional recomputation of values that were removed by pruning.

Entries are stored in the map using a very optimistic update. No synchronization at all is performed on the cache entries or their counts. A copy-on-write strategy coupled with Java's memory model for references ensures that the cache remains consistent, if not complete. What this means is that multiple threads may both try to cache a mapping and only one will be saved and/or incremented in count.

When the table approximately exceeds the specified load factor, the thread performing the add will perform a garbage collection by reducing reference counts by half, rounding down, and removing entries with zero counts. Pruning is subject to the caveats mentioned in the last paragraph. Counts are not guaranteed to be accurate. Pruning itself is synchronized and more conservatively copy-on-write. By setting the load factor to Double.POSITIVE_INFINITY there will be never be any pruning done by this class; all pruning will take place by soft reference garbage collection.

A fast cache acts as a mapping with copy-on-write semantics. Equality and iteration are defined as usual, with the caveat that the snapshot taken of the elements may not be up to date. Iterators may be used concurrently, but their remove methods do not affect the underlying cache.

Serialization

A fast cache may be serialized if the keys and values it contains are serializable. It may always be serialized if it is first cleared using clear().

References

For more information on soft references, see:

For information on copy-on-write and optimistic updates, see section 2.4 of:

Since:
LingPipe2.2
Version:
3.8.3
Author:
Bob Carpenter
See Also:
Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from interface java.util.Map
Map.Entry<K,V>
 
Constructor Summary
FastCache(int size)
          Constrcut a fast cache of the specified size and default load factor.
FastCache(int size, double loadFactor)
          Construct a fast cache of the specified size (measured in number of hash buckets) and load factor.
 
Method Summary
 void clear()
          Removes all entries from this cache.
 Set<Map.Entry<K,V>> entrySet()
          Returns a snapshot of the entries in this map.
 V get(Object key)
          Returns the value of the specified key or null if there is no value attached.
 void prune()
          Prunes this cache by (approximately) dividing the counts of entries by two and removing the ones with zero counts.
 V put(K key, V value)
          Sets the value of the specified key to the specified value.
 
Methods inherited from class java.util.AbstractMap
clone, containsKey, containsValue, equals, hashCode, isEmpty, keySet, putAll, remove, size, toString, values
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

FastCache

public FastCache(int size)
Constrcut a fast cache of the specified size and default load factor. The default load factor is 0.5. See FastCache(int,double) for more information.

Parameters:
size - Number of buckets in cache
Throws:
IllegalArgumentException - if the size is less than 2.

FastCache

public FastCache(int size,
                 double loadFactor)
Construct a fast cache of the specified size (measured in number of hash buckets) and load factor. The size times the load factor must be greater than or equal to 1. When the (approximate) number of entries exceeds the load factor times the size, the cache is pruned.

Parameters:
size - Number of buckets in the cache.
loadFactor - Load factor of the cache.
Throws:
IllegalArgumentException - If the size is less than one or the load factor is not a positive finite value.
Method Detail

get

public V get(Object key)
Returns the value of the specified key or null if there is no value attached. Note that the argument is not the generic <K> key type, but Object to match the requirements of java.util.Map.

Warning: Because of the approximate cache-like behavior of this class, key-value pairs previously added by the put(Object,Object) method may disappear.

Specified by:
get in interface Map<K,V>
Overrides:
get in class AbstractMap<K,V>
Parameters:
key - Mapping key.
Returns:
The value for the specified key.

put

public V put(K key,
             V value)
Sets the value of the specified key to the specified value. If there is already a value for the specified key, the count is incremented, but the value is not replaced.

Warning: Because of the approximate cache-like behavior of this class, setting the value of a key with this method is not guaranteed to replace older values or remain in the mapping until the next call to get(Object).

Specified by:
put in interface Map<K,V>
Overrides:
put in class AbstractMap<K,V>
Parameters:
key - Mapping key.
value - New value for the specified key.
Returns:
null, even if there is an existing value for the specified key.

clear

public void clear()
Removes all entries from this cache.

Specified by:
clear in interface Map<K,V>
Overrides:
clear in class AbstractMap<K,V>

prune

public void prune()
Prunes this cache by (approximately) dividing the counts of entries by two and removing the ones with zero counts. This operation is approximate in the sense that the optimistic update strategy applied is not guaranteed to actually do any pruning or decrements of counts.


entrySet

public Set<Map.Entry<K,V>> entrySet()
Returns a snapshot of the entries in this map. This set is not backed by this cache, so that changes to the cache do not affect the cache and vice-versa.

Specified by:
entrySet in interface Map<K,V>
Specified by:
entrySet in class AbstractMap<K,V>
Returns:
The set of entries in this cache.