A Least Recently Used Cache in C#
I recently (ha…) implemented a Least Recently Used (LRU) cache in C#, inspired by the one in Python’s functools library.
The way it works is you take an ordinary C# method such as this one…
public int Add(int x, int y)
{
int result = x + y;
return result;
}…and you add on an attribute from the LRU cache library:
[LruCache]
public int Add(int x, int y)
{
int result = x + y; return result;
}The presence of the LRUCache attribute says that if the parameters passed in exist in the cache, don’t execute the method, but instead return the cached result. In real life, the work done by the method could be a lot more costly than performing a simple addition, so by using caching, we can save a lot of time. In general, the technique of caching the results of a function is known as memoization.
Some Details
The cache is defined by the following interface:
public interface ICache
{
bool IsCached(object[] args);
bool Add(object[] args, object value);
CacheEntry Get(object[] args);
}The cache itself is a combination of two data structures: a <Dictionary<string, int>> and a List<CacheEntry>. The key of <Dictionary<string, int>> is a hash, and the value is an index into List<CacheEntry>.
CacheEntry is a POCO that looks like this:
public sealed class CacheEntry
{
public string Hash { get; set; }
public object Value { get; set; }
}In the sections below I’ll go a little bit into the implementations of the methods listed on the interface.
IsCached(object[] args)
All this method does is create a MD5 hash value out of the concatenated hash codes of the method’s parameters. This gives us a unique key, which we can look up in the dictionary to see whether those parameters have been called on the method before.
Add(object[] args, object result)
This method checks if the dictionary contains the hashed args, and if it doesn’t, it removes the least recently used entry from the back of the cache and inserts the hashed args and result into the front of the cache. The args hash value is added to the dictionary with an index value of 0 (meaning it’s at the “front” of the cache). If the cache already contains the hashed args, nothing happens.
If we imagine our cache can contain at most 3 items, ordered by when they were last used, then when a fourth item is added to the cache, the least recently used item is ejected.
Get(object[] args)
This method returns the cached result of the hashed args. As a side effect, it moves the CacheEntry to the front of the cache (it becomes the most recently used entry in the cache).
In a future blog post, I’ll cover just how adding an attribute on to a regular C# method can give us this seamless caching mechanism. If you’re curious and want to look at the code beforehand, you can find it here.
