32
\$\begingroup\$

The ConcurrentDictionary<T,V> in .NET 4.0 is thread safe but not all methods are atomic.

This points out that:

... 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.

Example Problem:

It is possible for the delegate method to be executed more than once for a given key.

public static readonly ConcurrentDictionary<int, string> store =
    new ConcurrentDictionary<int, string>();

[TestMethod]
public void UnsafeConcurrentDictionaryTest()
{

    Thread t1 = new Thread(() =>
    {
        store.GetOrAdd(0, i =>
        {
            string msg = "Hello from t1";
            Trace.WriteLine(msg);
            Thread.SpinWait(10000);
            return msg;
        });
    });

    Thread t2 = new Thread(() =>
    {
        store.GetOrAdd(0, i =>
        {
            string msg = "Hello from t2";
            Trace.WriteLine(msg);
            Thread.SpinWait(10000);
            return msg;
        });
    });

    t1.Start();
    t2.Start();
    t1.Join();
    t2.Join();
}

The result shown in the Trace window shows "Hello from t1" and "Hello from t2". This is NOT the desired behavior for most implementations that we are using and confirms the problem noted in the MSDN link above. What we want is for only one of those delegates to be executed.

Proposed Solution:

I have to use the delegate overloads of these methods which led me to investigate this matter further. I stumbled onto this post which suggests using the Lazy<T> class to ensure the delegate is only invoked once. With that in mind I wrote the following extension methods to mask the adding of a Lazy<T> wrapper to the value.

public static V GetOrAdd<T, U, V>(this ConcurrentDictionary<T, U> dictionary, T key, Func<T, V> valueFactory)
where U : Lazy<V>
{
    U lazy = dictionary.GetOrAdd(key, (U)new Lazy<V>(() => valueFactory(key)));
    return lazy.Value;
}

public static V AddOrUpdate<T, U, V>(this ConcurrentDictionary<T, U> dictionary, T key, Func<T, V> addValueFactory, Func<T, V, V> updateValueFactory)
where U : Lazy<V>
{
    U lazy = dictionary.AddOrUpdate(key, 
                (U)new Lazy<V>(() => addValueFactory(key)), 
                (k, oldValue) => (U)new Lazy<V>(() => updateValueFactory(k, oldValue.Value)));
    return lazy.Value;
}

Testing Solution:

Executing the same test above using a ConcurrentDictionary that has a Lazy value results in the value delegate ONLY being executed once (you either see "Hello from t1" or "Hello from t2")!

public static readonly ConcurrentDictionary<int, Lazy<string>> safeStore =
            new ConcurrentDictionary<int, Lazy<string>>();

So it seems that this approach accomplished the goal.

What do you think of this approach?

\$\endgroup\$
  • \$\begingroup\$ So does this mean that if the dictionary was exposed by a third party and was not defined as a <T,Lazy<V>>, you would not be able to do it? \$\endgroup\$ – Daryl Jan 10 '12 at 18:57
  • \$\begingroup\$ @Daryl I don't get your question. These extension methods are designed to operate on a Dictionary<T, Lazy<V>>. If the third party doesn't expose the dictionary as that, then you could not use these extension methods without first converting it that type. \$\endgroup\$ – Adam Spicer Jan 10 '12 at 19:27
  • \$\begingroup\$ Your proposed solution was defined as a dictionary of type <T, U> but your accepted solution moved to one of type <T, Lazy<V>>. I was hoping to get this sort of functionality, without having to change my dictionary to <T, Lazy<V>>. I've instead settled on passing in a object to use as the lock \$\endgroup\$ – Daryl Jan 11 '12 at 19:58
  • \$\begingroup\$ It might be worth noting that this approach is not fully thread safe, it just reduces the chance of race a condition, but one can still occur. Consider a case in which the first thread calls Lazy.Value after the assignment of the first Lazy instance and before the the second one's. The next call to Lazy.Value will invoke the method again. This could be a real problem in very high performance applications. \$\endgroup\$ – Mohoch Aug 7 '19 at 9:10
14
\$\begingroup\$
  • Allowing the caller to provide the type argument U implies that they are allowed to use a subclass of Lazy<V>, but this will not work as your implementations always creates a new List<V> and cast it to U. Since this means U must always be a Lazy<V> then why not do away with the extra type argument.

    public static V GetOrAdd<T, V>(this ConcurrentDictionary<T, Lazy<V>> dictionary, T key, Func<T, V> valueFactory)
    
  • The name of the new extension methods conflict with the names of the existing methods. For the consumer to use yours instead of the existing methods, they would need to either access via your static class or use explicit type arguments. This could lead to subtle bugs when consumers try to use it as a extension method with type inference.

    ExtensionHost.GetOrAdd(safeStore, 7, (i) => i.ToString());             // uses yours
    safeStore.GetOrAdd<int, Lazy<string>, string>(6, (i) => i.ToString()); // uses yours
    safeStore.GetOrAdd(5, (i) => i.ToString());                            // uses existing
    
\$\endgroup\$
  • \$\begingroup\$ Thanks for your notes. Great point about the type U. Also, I have already been bitten by the subtle bug. I agree that my overload too closely resembles the existing GetOrAdd() method. I'll incorporate your recommendations. \$\endgroup\$ – Adam Spicer Apr 23 '11 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.