Enhanced C#
Language of your choice: library documentation
Properties | Public Member Functions | Protected Member Functions | Protected fields | List of all members
Loyc.Collections.SimpleCache< T > Class Template Reference

A cache designed to save memory by sharing instances of identical strings and other immutable objects. More...


Source file:

Remarks

A cache designed to save memory by sharing instances of identical strings and other immutable objects.

Template Parameters
T

SimpleCache is not thread safe. However, G.Cache() is.

SimpleCache is used simply by calling Cache(). For example, if C is a SimpleCache(of string), then C.Cache("Hello") adds the string "Hello" to the cache if it is not present already, or returns the existing string if it is.

I'll describe SimpleCache as a two-way set associative hash cache. An object O with some hashcode X is always located at one of two locations in the cache: XS or (X+1)S, where S is the size of the hashtable. If C.Cache(O) is called and O is not in the cache, O is always placed at position XS. If another object P with hash Y is added, and YS == XS, then O is moved to position (X+1)S so that P can take the position. Thus, an object is only located in the "plus one" position if it was less recently used, and the cache will choose to discard that object when necessary.

The cache size doubles when the number of objects discarded (replacements) reaches the cache size, provided that the cache is at least 50% used. The initial size is normally 32, and the maximum size can be specified in the constructor (default: 1024). Note that regardless of cache size, it is impossible for three objects to be in the cache at the same time if they all share the same hash code. But on the plus side, if you alternate between calling Cache(A) and Cache(B), for any A and B, you are guaranteed to get only cache hits in steady-state. (To prove this, by the way, one must consider not only when A and B have the same hash code, but when A.GetHashCode() == B.GetHashCode() + 1).

The algorithm is pretty simple–Cache() has no loops–so it should be quite fast as well.

TODO: try supporting hashtables with non-power-of-2 sizes for possible speedup.

Type Constraints
T :class 

Properties

int CacheHits [get]
 
int CacheMisses [get]
 

Public Member Functions

 SimpleCache (int maxSize)
 
 SimpleCache (int maxSize, IEqualityComparer< T > comparer)
 
Cache (T obj)
 
void Clear ()
 
void DebugCheck ()
 

Protected Member Functions

void Enlarge ()
 

Protected fields

IEqualityComparer< T > _comparer
 
int _mask
 
int _maxSize
 
T[] _table
 
int _replacementCount
 
int _inUse
 
int _cacheHits