Downloads for post:
- LruCacheOrig.zip Source code for this post.
- LruCacheLib.zip Source code from all three posts in series.
- LruCacheLib1.2.1.zip Updated after this post (added cache item expiration in LruCacheSlim).
I started with a basic implementation that uses .Net’s LinkedList<TValue>. There were two ways I could go with the cache’s field. I could have the the LinkedList store the key and the value pairs the cache contains, and then use the Dictionary to store the a pairing of the key with the associated LinkedListNode from the LinkedList. The only thing the cache really needs to store in the LinkedList is the key so that when the least recently used item is discarded from the LinkedList, I can use the key to delete the associated entry in the Dictionary as well. The second choice is to just store keys in the LinkedList, and store the key paired with a tuple of value and LinkedListNode in the Dictionary. I chose the later because it only puts the pieces in the collections where they’re needed. The following minimal implementation shows the basic operation of the class.
// Copyright ©2012 SoftWx, Inc.
// Released under the MIT License.
using System;
using System.Collections.Generic;
namespace SoftWx.Lib {
/// <summary>
/// Simple implementation of an LRU Cache (Least Recently Used). This uses
/// LinkedList for it's use-ordered list.
/// </summary>
/// <remarks> LruCache is conservative with regard to creating linked list node object.
/// Once the cache has filled, it re-uses the oldest node object to hold the incoming
/// newest object. So over its entire lifetime, it will not create more than Capacity
/// node objects.
/// </remarks>
public sealed class LruCacheOrig<TKey, TValue> {
private object lockObj = new object();
private int capacity;
private Dictionary<TKey, Entry> cacheMap;
private LinkedList<TKey> cacheList;
private LruCacheOrig() { }
/// <summary>
/// Create a new instance of LruCache with the specified capacity.
/// </summary>
/// <param name="capacity">Maximum capacity of the cache.</param>
public LruCacheOrig(int capacity) {
this.capacity = capacity;
this.cacheMap = new Dictionary<TKey, Entry>(capacity);
this.cacheList = new LinkedList<TKey>();
}
/// <summary>Gets the maximum capacity of this LruCache.</summary>
public int Capacity { get { return this.capacity; } }
/// <summary>Gets the count of items contained in this LruCache.</summary>
public int Count { get { return this.cacheMap.Count; } }
/// <summary>Clear the contents of the LruCache.</summary>
public void Clear() {
lock (lockObj) {
this.cacheList.Clear();
// break all links between nodes (may help garbage collection)
this.cacheMap.Clear();
}
}
/// <summary>Try and get the cached value with the specified key.</summary>
/// <param name="key">The key used to identify the cached item.</param>
/// <param name="value">When this method returns, contains the value
/// associated with the specified key, or the default value if the key
/// is not in the cache.</param>
/// <returns>True if the value associated with the specified key was found,
/// otherwise false.</returns>
public bool TryGetValue(TKey key, out TValue value) {
lock (lockObj) {
Entry entry;
if (this.cacheMap.TryGetValue(key, out entry)) {
Touch(entry.node);
value = entry.value;
return true;
}
}
value = default(TValue);
return false;
}
/// <summary>
/// Determines whether the LruCache containse the specified key.
/// </summary>
/// <param name="key">The key to locate in the LruCache.</param>
/// <returns></returns>
public bool ContainsKey(TKey key) {
lock (lockObj) {
return this.cacheMap.ContainsKey(key);
}
}
/// <summary>
/// Adds the specified value to the cache, associated with
/// the specified key. If a value is in the cache already
/// with that key, then the value in the cache is replaced
/// with the specified value.
/// </summary>
/// <param name="key">The key used to identify the cached item.</param>
/// <param name="value">The value to be stored in the cache.</param>
public void Add(TKey key, TValue value) {
lock (lockObj) {
Entry entry;
if (!this.cacheMap.TryGetValue(key, out entry)) {
LinkedListNode<TKey> node;
if (this.cacheMap.Count == this.capacity) {
// cache full, so re-use the oldest node
node = this.cacheList.First;
this.cacheMap.Remove(node.Value);
this.cacheList.RemoveFirst();
node.Value = key;
} else {
// add newest
node = new LinkedListNode<TKey>(key);
}
this.cacheList.AddLast(node);
// map the key to the node and value
this.cacheMap.Add(key, new Entry(node, value));
} else {
// key exists, so modify value and make node the newest
entry.value = value;
this.cacheMap[key] = entry;
Touch(entry.node);
}
}
}
/// <summary>
/// Make the cache item with the specified node be the most recently used item.
/// Must be called from code that is in a lock block.
/// </summary>
/// <param name="node">The cached item LruNode.</param>
private void Touch(LinkedListNode<TKey> node) {
if (node != this.cacheList.Last) {
// node is not already the newest
this.cacheList.Remove(node);
this.cacheList.AddLast(node);
}
}
private struct Entry {
public LinkedListNode<TKey> node;
public TValue value;
public Entry(LinkedListNode<TKey> node, TValue value) {
this.node = node;
this.value = value;
}
}
}
}
For the tuple stored in the Dictionary, I chose to declare a simple private struct called Entry. This helps the code read better than if I had used something like KeyValuePair, and avoids the object creations that would come with using the Tuple class.The only optimization I made, other than just trying to avoid unnecessary code, was some extra logic in the Add method. Once the cache reaches its capacity, any further adds require that the oldest item be removed to make room for the new one. In this case, I re-purpose the oldest LinkedListNode to hold the new data being added rather than discard the oldest node and create a new one to insert in the linked list. This ensures that the cache will create at most the number of LinkedListNodes equal to the capacity of the cache over the entire lifetime of the cache (assuming Clear() isn't called). For caches with large capacity (>1,000,000) this can nearly cut in half the time needed to add a new item to the cache, and is a little bit friendlier to the garbage collector.
 |
| Performance of LruCache that uses LinkedList |
In the next post, I’ll make a modified version of this class that uses a private implementation of a linked list.
