ConcurrentDictionary in .NET 4, not what you would expect

.NET 4 brings some awesome support for multithreaded programming as part of Task Parallel Library, Concurrent collections and few other types that live now in the framework.

Not all behaviour they expose is… not unexpected thought. What would be the result of the following code:

        
private static void ConcurrentDictionary()
{
	var dict = new ConcurrentDictionary<int, string>();
	ThreadPool.QueueUserWorkItem(LongGetOrAdd(dict, 1));
	ThreadPool.QueueUserWorkItem(LongGetOrAdd(dict, 1));
}
 
private static WaitCallback LongGetOrAdd(ConcurrentDictionary<int, string> dict, int index)
{
	return o => dict.GetOrAdd(index,i =>
										{
											Console.WriteLine("Adding!");
											Thread.SpinWait(1000);
 
											return i.ToString();
										}
					);
}

We call GetOrAdd method from ConcurrentDictionary<, > on two threads trying to concurrently obtain an item from the dictionary, creating it using provided delegate in case it’s not yet present in the collection. What would be the result of running the code?

Surprisingly both delegates will be invoked, so that we’ll see the message “Adding!” being printed twice, not once. This unfortunately makes the class unusable for a whole range of scenarios where you must ensure that creation logic is only ran once. One scenario where I wished I could use this class was Castle Dynamic Proxy and its proxy type caching. Currently it uses coarse grained double checked locking. The code could benefit from more elegant API like the one exposed by ConcurrentDictionary and fine grained locking.

However looks like ConcurrentDictionary is not an option, not unless coupled with Lazy<>, which while I suppose would work, is far less elegant and would not perform so good, since both classes would use their own, separate locking, so we’d end up using two locks instead of one, and having to go through additional, unnecessary layer of indirection.

So the message of the day is – new concurrent classes in .NET 4 are awesome but watch out for issues anyway.

  • Omer Mor

    surprisingly you’re right.
    I found the reasoning behind this at the following msdn page:
    msdn.microsoft.com/en-us/library/dd997369.aspx

    "Also, although all methods of ConcurrentDictionary<TKey, TValue> are thread-safe, not all methods are atomic, specifically GetOrAdd and AddOrUpdate. The user delegate that is passed to these methods is invoked outside of the dictionary’s internal lock. (This is done to prevent unknown code from blocking all threads.) Therefore it is possible for this sequence of events to occur:

    1) threadA calls GetOrAdd, finds no item and creates a new item to Add by invoking the valueFactory delegate.

    2) threadB calls GetOrAdd concurrently, its valueFactory delegate is invoked and it arrives at the internal lock before threadA, and so its new key-value pair is added to the dictionary.

    3) threadA’s user delegate completes, and the thread arrives at the lock, but now sees that the item exists already

    4) threadA performs a "Get", and returns the data that was previously added by threadB.

    Therefore, it is not guaranteed that the data that is returned by GetOrAdd is the same data that was created by the thread’s valueFactory. A similar sequence of events can occur when AddOrUpdate is called."

  • Thanks Omer for finding this.

    I don’t buy this explanation though. I’m not a moron, they don’t have to protect me from myself. Whereas I see lots of scenarios where current behavior is desirable, there’s also as many scenarios where having just one delegate being invoked is desired. As such there should be another overload or GetOrAddBlocking method…

  • Omer Mor

    I agree.
    However your "lazy" suggestion could be not so bad.
    Maybe providing extension method that hides the Lazy<TValue>?

    Here’s what I’m thinking about:

    public static V GetOrAdd<K,V>(this ConcurrentDictionary<K,Lazy<V>> dic, K key, Func<K,V> valueFactory)
    {
    var lazy = dic.GetOrAdd(key, k => new Lazy<V>(() => valueFactory(k)));
    return lazy.Value;
    }

  • Andreas Köpf

    The point of the Collections.Concurrent classes is that they are as lock-free as possible. It would be IMO catastrophic if a potentially long-lasting lock would be held during the value factory methods that you pass to GetOrAdd(). Ensuring that only one thread executes a factory requires blocking wait operations or if you can allow them to run asynchronously a queue of operations of which deques the next when it finishes…

    Lock-Free operations rely ONLY on CAS (Compare and Swap) operations.
    BTW one of the important keys for scalability is Indempotency combined with immutability: This lets you rock on GPU threads, normal CPU threads or parallel computing on thousands of machines…

  • Omer Mor

    Small correction:
    public static V GetOrAdd<K,V>(this ConcurrentDictionary<K,Lazy<V>> dic, K key, Func<K,V> valueFactory)
    {
    var lazy = dic.GetOrAdd(key, new Lazy<V>(() => valueFactory(key)));
    return lazy.Value;
    }

    There was no need to use the delegate overload of GetOrAdd. I changed it to the instance overload and now I suppose it’ll run inside a lock, where there should be no race conditions.

  • Chen Kinnrot

    q: if you add a ContainsKey check before the return i.ToString(); would it work?