# Thread safe cache for write through and writeback

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>
/// </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>
{
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);

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.

The first thing I noticed (beside the things @RubberDuck mentioned) is that you compare with true for non nullable booleans, which is unnecessary.

if (m_cache.ContainsKey(key) == true)
...
Debug.Assert(found == true);

Here are my two cents worth for a possible solution to your problem. If you create a class which looks like this, you can use a ConcurrentDictionary<CacheKey, TItem>.

public class CacheKey<TKey>
where TKey : IComparable
{
public int HitCount;
public TKey Key;
}

This may take a (small?) performance hit when you need to find out the oldest with the lowest hit count, depending on the size, but it will be thread safe.

For example:

var dictionary = new ConcurrentDictionary<CacheKey<string>, string>();
var key = dic.Keys.OrderByDescending(p => p.HitCount)
.First();
string value;
dic.TryRemove(key, out value);

I hope it will at least get you a little bit further.

• Having a more complex key type is a great idea. You suggested replacement strategy is different frim mine. I would also require that a last hit DateTime. I am not sure about timestamps in the cache keys, I have to think more about it. – aggsol Mar 9 '15 at 8:24
• @CodeClown I suggested the time stamp because you stated that the new elements are put in the middle. I reasoned that the oldest least used items automatically end up on the bottom. – Mixxiphoid Mar 9 '15 at 19:34

Don't bury all of your private fields at the bottom of the file. I almost voted to close this question for being broken because I thought they weren't defined anywhere. Most developers will expect to see them defined at the top of the class. Also ditch the m_ prefix. It's unnecessary noise. Use an underscore if you like, but no more. Even using an underscore to denote private fields is a debatable topic.

You also missed filling in some documentation here.

/// <summary>
/// Invalidate a cache item by key
/// </summary>
/// <param name="key"></param>

XML doc comments are great, but only if you fill them in completely.

I don't like your constructor either.

public BodhiCache(int capacity = 1024)
{
this.Capacity = capacity;

m_keyOrder = new List<TKey>(this.Capacity);
m_cache = new Dictionary<TKey, TItem>(this.Capacity);

I'm wary of any constructor that "news up" anything. It makes it hard to test and inject dependencies. I would also be wary of using optional arguments. Now, I understand you're just making sure the class has what it needs to function, but you should carefully consider if you should have a default constructor and an overloaded one that takes a list, dict, and capacity in as dependencies.

I would write your constructor more like this.

//default, paramaterless contructor
public BodhiCache()
:this(1024)
{}

public BodhiCache(int capacity)
:this(capacity, new List<TKey>(capacity), new Dictionary<TKey, TItem>(capacity))
{}

public BodhiCache(int capacity, IList<TKey> keyOrder, Dictionary<TKey, TItem>)
{
_this.Capacity = capacity;
_keyOrder = keyOrder;
_cache = cache;
}

• Thanks fo the comment. It clearly shows that I am acutally a C++ coder ;-) What dou you mean by "news up"? So instead I have default ctor that delegates the construction with the default capacity. How would you "inject dependencies"? What could those dependecies be in this case? Prefetching? – aggsol Mar 6 '15 at 13:02
• You create new objects in your constructor, which is something we should avoid whenever possible. In this case, the KeyOrder list and cache dictionary are dependencies. Which can be "injected" into the class by passing them in as arguments. I added an example that uses ctor chaining to my answer. Hopefully that clears things up. – RubberDuck Mar 6 '15 at 13:15
• That's interesting. I don't see _keyOrder and _cache as dependencies but as internal artifacts that the class uses to do its job. In which use cases do you envision the ability to inject them being useful? – Saul Marquez Mar 12 '15 at 13:59
• @SaulMarquez if you read my answer again, you'll see that I did in fact mention the same thing. – RubberDuck Mar 12 '15 at 16:13
get { return m_keyOrder.Count; }

Based on reference source, I think this is going to be safe even without a lock. And I can't imagine a reasonable implementation of List<T> where this wouldn't be thread-safe. But the documentation doesn't guarantee it, so I would either add a lock here, or a comment explaining the situation.

m_keyOrder.Remove(key);

This is very inefficient ($O(n)$). I think you should consider a different way to implement the LRU strategy.

The same applies to most of your modifications of m_keyOrder.

Debug.Assert(m_keyOrder[m_keyOrder.Count - 1].CompareTo(key) == 0);

This seems to be the only place where you use the fact that TKey is IComparable. Instead, you should require IEquatable<TKey> and use Equals() instead of CompareTo().

m_insertIndex = m_keyOrder.Count / 2;

I don't understand this, why are you inserting in the middle? I think that you should have a really good reason for that and you should document it by adding a comment.

Also, why is m_insertIndex a field? It doesn't seem to be used anywhere else.

• IEquatable<TKey> is indeed the better choice. I fear that every variation of LRU is (O(n)) because you have to check every item if it is the least recently used one. See my edit1 why I insert in the middle. – aggsol Mar 11 '15 at 9:08