ConcurrentDictionary<TKey,TValue> used with Lazy<T>

In a recent thread on the MSDN forum for the TPL, Stephen Toub suggested mixing ConcurrentDictionary<T,U> with Lazy<T>.  This provides a fantastic model for creating a thread safe dictionary of values where the construction of the value type is expensive.  This is an incredibly useful pattern for many operations, such as value caches.

The ConcurrentDictionary<TKey, TValue> class was added in .NET 4, and provides a thread-safe, lock free collection of key value pairs.  While this is a fantastic replacement for Dictionary<TKey, TValue>, it has a potential flaw when used with values where construction of the value class is expensive.

The typical way this is used is to call a method such as GetOrAdd to fetch or add a value to the dictionary.  It handles all of the thread safety for you, but as a result, if two threads call this simultaneously, two instances of TValue can easily be constructed.

If TValue is very expensive to construct, or worse, has side effects if constructed too often, this is less than desirable.  While you can easily work around this with locking, Stephen Toub provided a very clever alternative – using Lazy<TValue> as the value in the dictionary instead.

This looks like the following.  Instead of calling:

MyValue value = dictionary.GetOrAdd(
                             key, 
                             () => new MyValue(key));

We would instead use a ConcurrentDictionary<TKey, Lazy<TValue>>, and write:

MyValue value = dictionary.GetOrAdd(
                             key, 
                             () => new Lazy<MyValue>(
                                 () => new MyValue(key)))
                          .Value;

This simple change dramatically changes how the operation works.  Now, if two threads call this simultaneously, instead of constructing two MyValue instances, we construct two Lazy<MyValue> instances.

However, the Lazy<T> class is very cheap to construct.  Unlike “MyValue”, we can safely afford to construct this twice and “throw away” one of the instances.

We then call Lazy<T>.Value at the end to fetch our “MyValue” instance.  At this point, GetOrAdd will always return the same instance of Lazy<MyValue>.  Since Lazy<T> doesn’t construct the MyValue instance until requested, the actual MyClass instance returned is only constructed once.

About Reed
Reed Copsey, Jr. - http://www.reedcopsey.com - http://twitter.com/ReedCopsey

Comments

14 Responses to “ConcurrentDictionary<TKey,TValue> used with Lazy<T>”
  1. Kshaban says:

    You state that if two threads call the following at the same time that two instances will be created and you are correct:
    MyValue value = dictionary.GetOrAdd(
    key,
    () => new MyValue(key));

    However, replacing the statement with the Lazy construct does not return the same instance of Lazy as you suggest, nor would it return the same instance of any two types created.

    And since they would be two different Lazy instances, they WILL generate two different Ts when accessed.

    Please consider testing your proposed solutions before posting.

    Thanks,

    KShaban

    • Reed says:

      Kshaban –

      Please read the post more carefully.

      The “trick” here is that we do allow two Lazy instances to be constructed, but GetOrAdd(..) will always return the single instance that was actually added to the collection. The second instance (of Lazy) will get “thrown away” silently.

      Since we’re only accessing .Value on the Lazy that was returned by GetOrAdd, we only ever access the .Value property of the single Lazy instance that made it into the Dictionary. This prevents us from constructing T more than once.

      -Reed

  2. Kshaban says:

    And BTW ConcurrentDictionary does acquire locks when GetOrAdd is called.

    Look at in reflector and see the forth parameter “bool aquireLock” is called with true.

    • Reed says:

      Yes, technically, there a Monitor being used in here, which is effectively a lock. However, it is not locking the entire ConcurrentDictionary, but rather the specific bucket required to hold this value. It’s about as fine grained as you can get… (A lock is only shared if GetHashCode has a collision. With normal usage, this is effectively lock free.)

  3. Maximusya says:

    To simplify things you can get rid of on unneeded lambda:
    instead of
    MyValue value = dictionary.GetOrAdd(
    key,
    () => new Lazy(
    () => new MyValue(key)))
    .Value;

    make it
    MyValue value = dictionary.GetOrAdd(
    key,
    new Lazy(
    () => new MyValue(key))
    .Value;

    • Reed says:

      Maximusya,

      You could do this, but it will be less efficient, as the Lazy will get constructed EVERY call, not just when the key doesn’t exist. Granted, the overhead of constructing a Lazy is fairly low, but I’d still avoid this by using the lambda.

      -Reed

      • Maximusya says:

        I don’t have much experience, but wouldn’t the code using lambda be compiled into constructing a new expression tree, generating a closure to access “key” etc? If so then performance would be comparable.

        • Reed says:

          It won’t get compiled into an expression tree – it’ll get compiled into a delegate (a Func), which will be implemented (in this case) by a static method, so it’s basically just a delegate call of a static method. This is quite a bit “cheaper” than constructing the Lazy instance each time, especially if this is called a lot.

          • Maximusya says:

            OK, now that you convinced me to use two nested lambdas, I tried to rewrite my code and turned out that GetOrAdd method does not have an overload that takes Func as a value factory:
            GetOrAdd(TKey, Func)
            GetOrAdd(TKey, TValue)

            So the code will have to look like
            MyValue value = dictionary.GetOrAdd(
            key,
            _ => new Lazy(() => new MyValue(key)))
            .Value;
            or
            MyValue value = dictionary.GetOrAdd(
            key,
            keyArg => new Lazy(() => new MyValue(keyArg)))
            .Value;

          • Maximusya says:

            Sorry, < > got stripped out in the previous post in a list of GetOtAdd overloads:
            GetOrAdd(TKey, Func<TKey, TValue>)
            GetOrAdd(TKey, TValue)

            http://msdn.microsoft.com/en-us/library/ee378676.aspx

  4. QuanEdys says:

    Great idea, makes a lot of sense as well :)

    Thank you for the post.

Trackbacks

Check out what others are saying about this post...
  1. [...] Breakpoint does not trigger on GetOrAdd method of ConcurrentDictionary<Lazy> I use ConcurrentDictionary<Lazy<T>> to be cache mechanism for my expensive initialization T object as suggested here http://reedcopsey.com/2011/01/16/concurrentdictionarytkeytvalue-used-with-lazyt/ [...]



Speak Your Mind

Tell us what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!