This cache is like a list where new elements are inserted in the middle, cache hits are put to head of the list and replaced elements are taken from the end. Would I just use a list the lookup would take O(n). With a dictionary it is O(log(n)) but I lose the order of elements, so I use both.
.Net but only has ConcurrentDictionary but not a ConcurrentList so I did not mix it with a List. Even read access would end in a write (cache hit) so I just use a lock in every method. How could I achieve something like multiple reader - one writer locking?
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace Bodhi
{
/// <summary>
/// Simple threadsafe caching collection
/// </summary>
/// <typeparam name="TKey">Key of the cached item implementing IComparable</typeparam>
/// <typeparam name="TItem">Cached item</typeparam>
public class BodhiCache<TKey, TItem>
where TKey : IComparable
where TItem : class
{
/// <summary>
/// Initializes a new instance of BodhiCache.
/// </summary>
/// <param name="capacity">Capacity, default 1024</param>
public BodhiCache(int capacity = 1024)
{
this.Capacity = capacity;
m_keyOrder = new List<TKey>(this.Capacity);
m_cache = new Dictionary<TKey, TItem>(this.Capacity);
}
public int Capacity { get; private set; }
/// <summary>
/// Returns the current cache content including keys and items.
/// </summary>
public Dictionary<TKey, TItem> Content
{
get
{
lock (m_syncRoot)
{
return new Dictionary<TKey, TItem>(m_cache);
}
}
}
/// <summary>
/// Gets the current number of cached items
/// </summary>
public int Count
{
get { return m_keyOrder.Count; }
}
/// <summary>
/// Clears the cache. Get the content before hand to implement a cache flush.
/// </summary>
public void Clear()
{
lock (m_syncRoot)
{
Debug.Assert(m_keyOrder.Count == m_cache.Count);
Debug.Assert(m_keyOrder.Count <= this.Capacity);
m_cache.Clear();
m_keyOrder.Clear();
Debug.Assert(m_keyOrder.Count == m_cache.Count);
Debug.Assert(m_keyOrder.Count <= this.Capacity);
}
}
/// <summary>
/// Invalidate a cache item by key
/// </summary>
/// <param name="key"></param>
public void Invalidate(TKey key)
{
lock (m_syncRoot)
{
Debug.Assert(m_keyOrder.Count == m_cache.Count);
Debug.Assert(m_keyOrder.Count <= this.Capacity);
m_keyOrder.Remove(key);
m_cache.Remove(key);
Debug.Assert(m_keyOrder.Count == m_cache.Count);
Debug.Assert(m_keyOrder.Count <= this.Capacity);
}
}
/// <summary>
/// Get a cached item by key
/// </summary>
/// <param name="key"></param>
/// <returns>Returns cached item if found, null otherwise</returns>
public TItem Load(TKey key)
{
lock (m_syncRoot)
{
Debug.Assert(m_keyOrder.Count == m_cache.Count);
Debug.Assert(m_keyOrder.Count <= this.Capacity);
TItem result = null;
if (m_cache.ContainsKey(key) == true) // hit
{
m_keyOrder.Remove(key);
m_keyOrder.Add(key);
result = m_cache[key];
Debug.Assert(m_keyOrder[m_keyOrder.Count - 1].CompareTo(key) == 0);
}
Debug.Assert(m_keyOrder.Count == m_cache.Count);
Debug.Assert(m_keyOrder.Count <= this.Capacity);
return result;
}
}
/// <summary>
/// Store an item by its key in the cache. For write-back you have to implement it with the
/// replaced item.
/// </summary>
/// <param name="key"></param>
/// <param name="item"></param>
/// <returns>Returns a replaced item if cache is full, null otherwise</returns>
public TItem Store(TKey key, TItem item)
{
Debug.Assert(m_keyOrder.Count == m_cache.Count);
Debug.Assert(m_keyOrder.Count <= this.Capacity);
lock (m_syncRoot)
{
m_insertIndex = m_keyOrder.Count / 2;
TItem old = null;
// refresh
if (m_cache.ContainsKey(key) == true)
{
m_cache[key] = item;
m_keyOrder.Remove(key);
m_keyOrder.Insert(m_insertIndex, key);
}
else if (m_cache.Count == this.Capacity) // replacement
{
// remove old
var oldKey = m_keyOrder[0];
m_keyOrder.RemoveAt(0);
old = m_cache[oldKey];
bool found = m_cache.Remove(oldKey);
Debug.Assert(found == true);
m_cache[key] = item;
m_keyOrder.Insert(m_insertIndex, key);
}
else
{
m_cache[key] = item;
m_keyOrder.Insert(m_insertIndex, key);
}
Debug.Assert(m_keyOrder.Count == m_cache.Count);
Debug.Assert(m_keyOrder.Count <= this.Capacity);
return old;
}
}
private readonly object m_syncRoot = new object();
private Dictionary<TKey, TItem> m_cache;
private int m_insertIndex;
private List<TKey> m_keyOrder;
}
}
Cache strategy rationale: The insertion of new elements in the middle rates the new item higher than the lower half of older or low performing cache items. It would be possible to insert in the higher third or lower sixth.
You can find the improved version here while I am adding and testing the suggested ideas from here.
