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:

• /Core/Loyc.Collections/Other/SimpleCache.cs

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)
T	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