CODEWITHSUNDEEP
c#multithreadingdictionarythread-safety
seesharper
seesharper

Reputation: 3379

Non-blocking key/value storage

I'm currently writing some extremely performance critical code that needs a way to retrieve values from a key-value storage without using locks.

I have tried using the ConcurrentDictionary, but that does not perform good enough for my needs in this case.

So what I'm after here is something similar to the GetOrAdd method found in ConcurrentDictionary, but I need it to be super fast (without locks) and still be thread safe :)

It should be noted here that it is assumed that we will mostly be doing retrieval of existing values and quite rarely add new values. It is also assumed that this list is not going to be very large.

I'm not a threading expert so it would be nice if anyone could comment on what I came up with.

public class Registry<TKey, TValue>
{
    private Dictionary<TKey, TValue> dictionary = new Dictionary<TKey, TValue>();

    public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory)
    {
        TValue value;            
        if (!dictionary.TryGetValue(key, out value))
        {
            var snapshot = new Dictionary<TKey, TValue>(dictionary);
            if (!snapshot.TryGetValue(key, out value))
            {
                value = valueFactory(key);
                snapshot.Add(key, value);
                dictionary = snapshot;
            }                
        }
        return value;
    }
}

The "trick" here is to create a snapshot of the actual dictionary if we actually need to add a new value to it. At the end we swap the reference so that the dictionary variable now points the snapshot. Remember I don't really care if I loose an update or two, here and there. What I need is really fast retrieval for existing values.

I'm a little uncertain about the code that swaps the reference.

dictionary = snapshot;

What happens if another thread tries to access the dictionary variable at the same time as the reference is being swapped. Is that even an issue here?

Regards

Bernhard Richter

Upvotes: 1

Views: 1331

Answers (3)

Ed Power
Ed Power

Reputation: 8531

Since your dictionary size isn't big and you're not updating it very often, you can use a double-buffered approach:

Create two identical dictionaries, and read from the first. Apply updates to the second dictionary and swap references so that you're now reading from the second dictionary. Then go back and apply the same updates to the first dictionary.

Apply the next updates to the first dictionary, swap references, then update the second dictionary. And so forth, flip-flopping between dictionaries each time you update.

Upvotes: 1

Alois Kraus
Alois Kraus

Reputation: 13545

Your first take is nearly correct. Swapping a reference is thread safe in the sense that the address is updated atomically. But your still need to take a lock when you want to update the dictionary since you do not want to loose any concurrent changes. The only way to achieve this is to take some sort of lock.

If do not do it you will use sometimes an older version of the dictionary altough the reference has been updated in between and your thread does then swap the reference with an updated dictionary which does contain old data.

The MS Threading handbook does also mentiond that ConcurrentDictionary does not scale so well when you are very rarely updating the dictionary. In this case a classic dictionary is still better.

I do not know in which problem domain you got into this but it could be that changing the data structures you are working on might give you even more performance than to optimize concurrent dictionary access. Dictionaries are very fast but CPU data cache unfriendly. If you want to get even faster it could be that you need to get rid of dictionaries or you need different data structures to get more linear reading in memory which is much more cache friendly. 

public class Registry<TKey, TValue>
{
    private Dictionary<TKey, TValue> dictionary = new Dictionary<TKey, TValue>();
    private object Lock = new object();

    public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory)
    {
        TValue value;            
        if (!dictionary.TryGetValue(key, out value))
        {
            lock(Lock)
            {
              var snapshot = new Dictionary<TKey, TValue>(dictionary);
              if (!snapshot.TryGetValue(key, out value))
              {
                  value = valueFactory(key);
                  snapshot.Add(key, value);
                  dictionary = snapshot;
              }
            }   
        }
        return value;
    }
}

Upvotes: 4

Ankush
Ankush

Reputation: 2554

This is not correct! The constructor of dictionary will iterate through whole dictionary before creating snapshot. This can lead to incorrect state of snapshot.

If ConcurrentDictionary doesn't help you, you can try with immutable data structures like prefix tree (aka radix tree or trie). These are thread safe.

Upvotes: 1

Related Questions