“Thread safe” Dictionary(TKey,TValue)

Update : Based on a comment on this post I’ve added a follow up post that covers the question: What is This “Thread Safe” Thing Anyway?

Introduction

A pet project I’m currently working on requires the use of an internal Dictionary to store “registered” data, which is a pretty common requirement. For this particular project I’d like to at least *attempt* to make it “thread safe” on .NET 3.5, with an eye to moving it to the ConcurrentDictionary in .NET 4 which promises not only thread safety, but more granular locking to increase multi-threaded performance.

A simple enough task, but one that I’ve seen many people make mistakes implementing.

Just Locking Writes?

It’s obvious we need to do some kind of syncronisation primitive around our writes, but first impressions might make you think that read should be ok – especially if we stick to the preferred TryGetValue pattern instead of “if it exists then get the value”:

object myValue;

// This is obviously not thread safe.
// Something else can alter the collection
// between ContainsKey and reading the
// value.
if (dictionary.ContainsKey("Testing"))
{     myValue = dictionary["Testing"];
}

// Using TryGetValue looks safe though?
// Doesn't it?!
if (!dictionary.TryGetValue("Testing", out myValue))     throw new KeyNotFoundException();

Unfortunately if we fire up Reflector, and take a look at how TryGetValue is implemented, it’s pretty obvious it has exactly the same concurrency problem as the first method above:

public bool TryGetValue(TKey key, out TValue value)
{
    int index = this.FindEntry(key);
    if (index >= 0)
    {
        value = this.entries[index].value;
        return true;
    }
    value = default(TValue);
    return false;
}

Ok, So I Will Lock Reads and Writes?

The next obvious approach would be to find everywhere in our code where we access the Dictionary, for either reading or writing, and use a syncronisation primitive, such as lock, to ensure we’re only accessing it from a single thread at any one time:

private readonly object padlock = new object();
private readonly Dictionary<string, object> dictionary = new Dictionary<string, object>();

private void Test()
{
    object myValue;

    // Now we lock before we do anything
    lock (padlock)
    {
        if (dictionary.ContainsKey("Testing"))
        {
            myValue = dictionary["Testing"];
        }
    }

    lock (padlock)
    {
        if (!dictionary.TryGetValue("Testing", out myValue))
            throw new KeyNotFoundException();
    }
}

Simple enough, but you’re relying on locking around every access, which is not only ugly, but also potentially prone to errors if you miss one. Also, once we move our code to .NET 4, and the new ConcurrentDictionary, we will have to go through the code and remove each lock in turn – pretty laborious!

Composition, Composition, Composition!

In this approach we wrap our nasty non-thread safe dictionary in our own class, expose the methods we want to use, and take any locks accordingly. This class only implements “array” access and TryGetValue, but is sufficient to show the approach:

public class SafeDictionary<TKey, TValue>
{
    private readonly object _Padlock = new object();
    private readonly Dictionary<TKey, TValue> _Dictionary = new Dictionary<TKey, TValue>();

    public TValue this[TKey key]
    {
        get
        {
            lock (_Padlock)
            {
                return _Dictionary[key];
            }
        }
        set
        {
            lock (_Padlock)
            {
                _Dictionary[key] = value;
            }
        }
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        lock (_Padlock)
        {
            return _Dictionary.TryGetValue(key, out value);
        }
    }
}

As we prevent any direct access to the Dictionary, and use our lock internally whenever we need to access it, we can now use our SafeDictionary in code without worrying about concurrency issues – both for reading and for writing!

To .Net 4 ?

As I mentioned earlier .Net 4 will be shipping with several “thread safe” collections, including a dictionary, in the new System.Collections.Concurrent namespace. As we have our own SafeDictionary implementation we have a few options here:

• We could go through our code and replace all references to SafeDictionary with ConcurrentDictionary. We don’t have any locks in our main code so we could do this with a direct replacement.
• We could alter our SafeDictionary to use a ConcurrentDictionary internally, and remove all of our internal locks.
• If we don’t mind exposing extra methods we can remove all of the implementation from SafeDictionary and just derive it from ConcurrentDictionary:

public class SafeDictionary<Tkey, TValue> : ConcurrentDictionary<Tkey, TValue>
{
}

Conclusion

Quite a long blog post for quite a simple issue, but even simple concurrency can be the source of mistakes and headaches. Once .NET 4 arrives with its concurrent collections, parallel extensions and parallel debugging options hopefully at least *some* of this headache will go away.

Technorati Tags: concurrency, concurrentdictionary, csharp, dictionary, locks