Building a custom GetOrAdd method for ConcurrentDictionary<TKey,TValue>

Building a custom GetOrAdd method for ConcurrentDictionary<TKey,TValue>

Rate This
  • Comments 6

I was recently asked by a developer about getting some additional information out of ConcurrentDictionary<TKey,TValue>’s GetOrAdd method. 

As a reminder, GetOrAdd either returns the value for a key currently in the dictionary, or if that key doesn’t have a value, it adds a value for the key as dictated by either a TValue provided by the caller or by executing a Func<TKey,TValue> provided by the caller.  It then returns the new value.  However, it doesn’t tell the caller which happened; all the caller knows is that it’s handed back the value (existing or new) that was associated with the key.  The developer wanted to know which occurred, as he needed to notify some other code that a new value had been added.

While the built-in GetOrAdd method doesn’t provide this, we can build our own GetOrAdd overload to provide this behavior, building it on top of the existing TryGetValue and TryAdd methods:

public static TValue GetOrAdd<TKey, TValue>(
    this ConcurrentDictionary<TKey, TValue> dict,
   
TKey key, Func<TKey, TValue> generator,
    out bool added)
{
    TValue value;
    while (true)
    {
        if (dict.TryGetValue(key, out value)) 
        { 
            added = false
            return value; 
        }

        value = generator(key);
        if (dict.TryAdd(key, value)) 
        { 
            added = true
            return value; 
        }
    }
}

The approach here is straightforward.  We try to get the key’s value in the dictionary.  If we can, then we use an out parameter to indicate that a new value was not added and we return the value we retrieved.  If we can’t, then we try to add a new value as generated by the provided Func<TKey,TValue>; assuming that succeeds, we note the addition via the out parameter and we return the newly added value.  If the addition fails (which should only happen if another thread concurrently added an item since we called TryGetValue), then we loop around and try the whole process again.

Using the TryGetValue, TryAdd, and TryUpdate on ConcurrentDictionary<TKey,TValue>, it’s possible to build many variations of this kind of behavior.

Leave a Comment
  • Please add 4 and 2 and type the answer here:
  • Post
  • Thank you for looking at ConcurrentDictionary<>. It is a powerful collection class, but we keep running into one significant limitation: inability to guarantee single factory execution per key, the way Lazy<> can be made to initialize only once. In other words, when calling GetOrAdd(key, factory), it is possible for the factory to be executed several times in parallel for the same key. Putting a global lock inside factory could be prohibitively expensive for large dictionaries. Ideally, ConcurrentDictionary should have a per-key lock in case the key does not yet exist. The behavior could be controlled by constructor's parameter the same way as Lazy<>. Could this be done, or was there a reason not to implement it?

  • We could have done it that way, but we didn't due to concerns around deadlocks that could result from the arbitrary code in the factory method running while holding a lock.

    That said, you can still achieve this.  Instead of creating a ConcurrentDictionary<TKey,TValue>, try creating a ConcurrentDictionary<TKey,Lazy<TValue>>.  That way it doesn't matter functionally if the factory gets executed several times; at most one Lazy<TValue> will be published, and its internal lock will serve as the per-key lock you're looking for, making sure that your actual factory method (the one provided to the Lazy<TValue>) only ever executes once, e.g.

       private static ConcurrentDictionary<string,Lazy<MyData>> s_dict = new ConcurrentDictionary<string,Lazy<MyData>>();

       ...

       MyData value = s_dict.GetOrAdd(theKey, key => new Lazy<MyData>(() => ProduceMyData(key))).Value;

  • Look like TryAddInternal has this functionality built in

    Perhaps in the next release you could expose some overloads that use it more directly?

  • Hi,

    I don't understand the while(true) infinite loop implementation. It seemly suggests that TryAdd could be failed and need to retry but TryGetValue is not?

    Thanks

  • Disregard my previous question. I figured out this is multithread spinning implementation

  • larry, remember that multiple threads might be accessing the collection concurrently.  Let's say the key does not currently exist, so the call to TryGetValue will return false.  Then before we call TryAdd, another thread might come along and add the value to the dictionary; as such even though TryGetValue returned false, the collection has since changed to now contain the key, so TryAdd will also return false.  That's why we loop around again.

Page 1 of 1 (6 items)