A Look on the Code: Implementing CacheDictionary–A Dictionary with a limited number of items that can be used as cache.

Hi All,

Today we consider the following scenario: There is a process that needs to generate many resources. The generation process takes a long time and each generated resource is taking a considerable amount of memory (you don’t want to store more than a few such resources in the memory at a time). After analysis it is evident that when the process runs it often generates the same resource over and over again such that while the total number of generated resources is quite large, all these resources are the same. The solution would be to generate each resource only once and store it in some dictionary. Each subsequent request to generate this resource would simply retrieve it from this dictionary. To solve the issue I have implemented a CacheDictionary which holds only a specified amount of items and has a versatile removal strategy (when trying to add an item over the allowed limit).

It is possible to solve this problem using WeakReferenced values using a regular dictionary. In this solution a regular dictionary holds the resources as WeakReferences and therefore the GC may collect them at any time. The main advantage here is that you allow the CLR to manage the memory itself but you lose the ability to tailor the memory allocation and freeing behavior to your exact needs. At some cases this solution is probably very good but for other cases we need the CacheDictionary.

The CacheDictionary

My implementation encapsulates (and not inherits from) a regular dictionary. I have implemented the IDictionary<TKey,TValue> interface delegating the methods to an internal instance of the dictionary. The constructor requires two arguments: The maximum number of items allowed in the CacheDictionary and the RemovalStrategy. The RemovalStrategy is a class which controls which key is removed from the CacheDictionary when the Add method is called but a full capacity is reached. This class implements the following interface:

 public interface ICacheDictionaryRemovalStrategy<TKey>  
{  
  /// <summary>  
  /// Initialize the strategy and pass the maximum number of allowed items  
  /// </summary>  
  /// <param name="maxSize">The maximum number of allowed items</param>  
  void Initialize(int maxSize);  
  
  /// <summary>  
  /// Notify the strategy that a key was added to the base collection  
  /// </summary>  
  /// <param name="key">The key that was added</param>  
  void KeyAdded(TKey key);  
  
  /// <summary>  
  /// Notify the strategy that a key was removed from the base collection  
  /// </summary>  
  /// <param name="key">The key that was removed</param>  
  void KeyRemoved(TKey key);  
  
  /// <summary>  
  /// Notify the strategy that a key was accessed (retrieved by the user) in the base collection  
  /// </summary>  
  /// <param name="key">The key that was retrieved</param>  
  void KeyAccessed(TKey key);  
  
  /// <summary>  
  /// Notify the strategy that the base collection was cleared  
  /// </summary>  
  void Clear();  
  
  /// <summary>  
  /// Get the most appropriate key to remove, this is called when the base collection runs out of space  
  /// </summary>  
  /// <returns>The key that the base collection will remove</returns>  
  TKey GetKeyToRemove();  
} 

Most of the methods are used to notify the strategy about changes in the underlying dictionary with two exceptions. Initialize method is called in the constructor of the CacheDictionary to allow the strategy run its initialization. The GetKeyToRemove is called when the user tries to add an item to the CacheDictionary but the items count is equal to the maxSize passed in the constructor. The CacheDictionary expects to get an existing key or an exception will be thrown. A noteworthy method is KeyAccessed. In my implementation this method is called whenever the user retrieves some value by using a key (see next section for details).

Tracking Access

As mentioned above, I define access to the CacheDictionary as retrieving some value by its key. The KeyAccessed method is therefore called in the following locations:

TryGetValue method if the underlying call to TryGetValue was successful.
The indexer property.
The Current property of the custom enumerator.

The third point is worth elaborating upon. I am implementing the IDictionary interface and therefore I must provide a way to enumerate over the Key-Value pairs inside the dictionary. If I would just delegate these calls to the regular enumerator then I would miss an access done by the enumerator itself. For this reason I have added a wrapper class (CacheDictionaryEnumerator) which wraps the calls to the underlying enumerator but calls KeyAccessed method when needed.

The full implementation is therefore:

 public class CacheDictionary<TKey, TValue> : IDictionary<TKey, TValue>  
{  
  private Dictionary<TKey, TValue> _data;  
  private int _maxSize;  
  private ICacheDictionaryRemovalStrategy<TKey> _removalStrategy;  
  
  public CacheDictionary(int maxSize, ICacheDictionaryRemovalStrategy<TKey> removalStrategy)  
  {  
    if (removalStrategy == null)  
      throw new ArgumentNullException("removalStrategy");  
    if (maxSize == 0)  
      throw new ArgumentException("maxSize must be a positive integer value");  
    _maxSize = maxSize;  
    _removalStrategy = removalStrategy;  
    _data = new Dictionary<TKey, TValue>();  
  
    _removalStrategy.Initialize(maxSize);  
  }  
  
  #region IDictionaty Implementation  
  
  public void Add(TKey key, TValue value)  
  {  
    if (_data.ContainsKey(key))  
      _data.Add(key, value); //I want to throw the same exception as the internal dictionary for this case.  
  
    if (_data.Count == _maxSize)  
    {  
      TKey keyToRemove = _removalStrategy.GetKeyToRemove();  
      if (_data.ContainsKey(keyToRemove))  
        _data.Remove(keyToRemove);  
      else  
        throw new Exception(String.Format("Could not find a valid key to remove from cache, key = {0}", key == null ? "null" : key.ToString()));  
    }  
    _data.Add(key, value);  
    _removalStrategy.KeyAdded(key);  
  }  
  
  public bool ContainsKey(TKey key)  
  {  
    return _data.ContainsKey(key);  
  }  
  
  public ICollection<TKey> Keys  
  {  
    get {return _data.Keys;}  
  }  
  
  public bool Remove(TKey key)  
  {  
    bool result = _data.Remove(key);  
    if (result)  
      _removalStrategy.KeyRemoved(key);  
    return result;  
  }  
  
  public bool TryGetValue(TKey key, out TValue value)  
  {  
    bool result = _data.TryGetValue(key, out value);  
    if (result)  
      _removalStrategy.KeyAccessed(key);  
    return result;  
  }  
  
  public ICollection<TValue> Values  
  {  
    get { return _data.Values; }  
  }  
  
  public TValue this[TKey key]  
  {  
    get  
    {  
      TValue result = _data[key];  
      _removalStrategy.KeyAccessed(key);  
      return result;  
    }  
    set  
    {  
      _data[key] = value;  
      _removalStrategy.KeyAccessed(key);  
    }  
  }  
  
  public void Add(KeyValuePair<TKey, TValue> item)  
  {  
    Add(item.Key, item.Value);  
  }  
  
  public void Clear()  
  {  
    _data.Clear();  
    _removalStrategy.Clear();  
  }  
  
  public bool Contains(KeyValuePair<TKey, TValue> item)  
  {  
    return _data.Contains(item);  
  }  
  
  public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)  
  {  
    ((IDictionary<TKey, TValue>)_data).CopyTo(array, arrayIndex);  
  }  
  
  public int Count  
  {  
    get { return _data.Count; }  
  }  
  
  public bool IsReadOnly  
  {  
    get { return ((IDictionary<TKey, TValue>)_data).IsReadOnly; }  
  }  
  
  public bool Remove(KeyValuePair<TKey, TValue> item)  
  {  
    bool result = ((IDictionary<TKey, TValue>)_data).Remove(item);  
    if (result)  
      _removalStrategy.KeyRemoved(item.Key);  
    return result;  
  }  
  
  public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()  
  {  
    return new CacheDictionaryEnumerator(_data.GetEnumerator(), _removalStrategy);  
  }  
  
  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()  
  {  
    return new CacheDictionaryEnumerator(_data.GetEnumerator(), _removalStrategy);  
  }  
  #endregion  
  
  public class CacheDictionaryEnumerator : IEnumerator<KeyValuePair<TKey, TValue>>  
  {  
    private IEnumerator<KeyValuePair<TKey, TValue>> _innerEnumerator;  
    private ICacheDictionaryRemovalStrategy<TKey> _removalStrategy;  
  
    internal CacheDictionaryEnumerator(IEnumerator<KeyValuePair<TKey, TValue>> innerEnumerator, ICacheDictionaryRemovalStrategy<TKey> removalStrategy)  
    {  
      if (innerEnumerator == null)  
        throw new ArgumentNullException("innerEnumerator");  
      if (removalStrategy == null)  
        throw new ArgumentNullException("removalStrategy");  
  
      _innerEnumerator = innerEnumerator;  
      _removalStrategy = removalStrategy;  
    }  
  
    public KeyValuePair<TKey, TValue> Current  
    {  
      get  
      {  
        KeyValuePair<TKey, TValue> result = _innerEnumerator.Current;  
        _removalStrategy.KeyAccessed(result.Key);  
        return result;  
      }  
    }  
  
    public void Dispose()  
    {  
      _innerEnumerator.Dispose();  
      _innerEnumerator = null;  
    }  
  
    object System.Collections.IEnumerator.Current  
    {  
      get {return this.Current;}  
    }  
  
    public bool MoveNext()  
    {  
      return _innerEnumerator.MoveNext();  
    }  
  
    public void Reset()  
    {  
      _innerEnumerator.Reset();  
    }  
  }  
} 

Strategy Implementations

For the solution to be useable out of the box (or out of the downloaded zip file) I have added three implementation of the ICacheDictionaryRemovalStrategy<TKey> interface. The three implementations are:

EmptyRemovalStrategy<TKey> – Removes the first item in it’s internal collection. Does not track access in any way.
MruRemovalStrategy<TKey> – Removes the most recently used (most accessed) item in the CacheDictionary.
LruRemovalStrategy<TKey> – Removes the least recently used (least accessed) item in the CacheDictionary.

These three implementation should allow you a basic use of the CacheDictionary right after download.

As usual you can download all the needed data from my skydrive (link below). The 7zip contains a small demo program on how to use the provided class. If you find bugs/improvements to my implementations I would be more than happy if you share those in the comments.

Thank you for reading,

Boris.

A Look on the Code

Saturday, March 3, 2012

Implementing CacheDictionary–A Dictionary with a limited number of items that can be used as cache.

Followers