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.
Reed Copsey, Jr.
-
http://www.reedcopsey.com
-
http://twitter.com/ReedCopsey
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
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
even it was throw away,still two instances were created ,and this is what we intended to avoid from the beginning
With the Lazy approach, two instances can be avoided. Without this, an instance will be created but thrown away.
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.
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.)
> With normal usage, this is effectively lock free
It’s *not* lock-free. This is a formal property, not open to negotiation or interpretation. To claim that it is, is a technical error – I suggest an edit.
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;
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
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.
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.
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;
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
Great idea, makes a lot of sense as well 🙂
Thank you for the post.
Thanks for this.
I added to an existing .NET Fiddle from a similar relevant post: https://blogs.endjin.com/2015/10/using-lazy-and-concurrentdictionary-to-ensure-a-thread-safe-run-once-lazy-loaded-collection/
My fiddle with your method shown is: https://dotnetfiddle.net/4qJZ6P