Personally, I think these (or signatures like them) would be fine additions. However, it's worth noting that these can be implemented as extension methods on top of the existing surface area, e.g.

public static TValue GetOrAdd<TKey, TValue, TArg>(
    this ConcurrentDictionary<TKey, TValue> dictionary,
    TKey key, 
    Func<TKey, TArg, TValue> valueFactory, 
    TArg arg)
{
    if (dictionary == null) throw new ArgumentNullException("dictionary");
    if (key == null) throw new ArgumentNullException("key");
    if (valueFactory == null) throw new ArgumentNullException("valueFactory");

    while (true)
    {
        TValue value;
        if (dictionary.TryGetValue(key, out value))
            return value;

        value = valueFactory(key, arg);
        if (dictionary.TryAdd(key, value))
            return value;
    }
}

public static TValue AddOrUpdate<TKey, TValue, TAddArg, TUpdateArg>(
    this ConcurrentDictionary<TKey, TValue> dictionary,
    TKey key, 
    Func<TKey, TAddArg, TValue> addValueFactory, 
    TAddArg addArg,
    Func<TKey, TValue, TUpdateArg, TValue> updateValueFactory,
    TUpdateArg updateArg)
{
    if (dictionary == null) throw new ArgumentNullException("dictionary");
    if (key == null) throw new ArgumentNullException("key");
    if (addValueFactory == null) throw new ArgumentNullException("addValueFactory");
    if (updateValueFactory == null) throw new ArgumentNullException("updateValueFactory");

    while (true)
    {
        TValue value;
        if (dictionary.TryGetValue(key, out value))
        {
            TValue updatedValue = updateValueFactory(key, value, updateArg);
            if (dictionary.TryUpdate(key, updatedValue, value))
            {
                return updatedValue;
            }
        }
        else
        {
            value = addValueFactory(key, addArg);
            if (dictionary.TryAdd(key, value))
            {
                return value;
            }
        }
    }
}

It's unlikely that the AddOrUpdate implementation could be much more efficient if done as part of the library. GetOrAdd could be made slightly more efficient if done internally, as the loop can be avoided using the internal TryAddInternal method, but it's a small enough win that performance wouldn't be a good argument for adding this to the library. The reason to add these would be if we believe that these methods would be used frequently enough to avoid the closure/delegate allocations that it'd be worth adding these rather than having the developer write their own helpers as I've done or having them in some 3rd-party extensions library.

In such cases I usually have to TryGet and then GetOrAdd. It allows to avoid closure allocation on the fast path.
And I am for @stephentoub's suggestion as we don't know how many arguments factory will need next time.

@stephentoub, thanks for demonstrating that these can be implemented as extension methods. I hadn't looked closely enough at the existing method implementations to know if extension methods were possible without access to TryAddInternal, but the loop is obvious now in hindsight.

I wonder whether implementing methods like these as extensions methods is the right approach for us moving forward. In the last years, we've preferred extension methods because it makes it easier for us to move this functionality out-of-band. However, there is a cost to extension methods as well. For one, they require additional types.

There are two cases where extension methods are clearly better (or the only sensible approach):

1. If the types themselves can't be extended (such as interfaces in case of Linq)
2. If the provided functionality sits at a higher layer (for example, adding path-based helpers to APIs that take streams and sit below the file system)

But for simple cases like this it doesn't seem to be worth the long term complexity to add this functionality as extension methods. There is certainly not a layer violation. It might buy us the ability to bring these APIs as an OOB component on .NET Framework but that isn't necessarily cheaper either. We'd have to expose this functionality not only on separate types but as a separate assembly and NuGet package.

If it's too late for adding these methods to the .NET Framework 4.6, then I'd prefer adding it to .NET Core only and then bring them into .NET Framework 4.7 (or whatever the next version number might be).

/cc @davkean @nguerrera @weshaggard

@terrajobst, I agree with all your comments. Just to be clear, though, I wasn't suggesting we ship these methods as extensions. I was suggesting that either we ship then as instance methods or we don't ship them at all, in which case anyone else can get the same functionality with these as extensions.

I was suggesting that [we could not] ship them at all, in which case anyone else can get the same functionality with these as extensions.

Ah, that makes sense to me.

Isn't AddOrUpdate equivalent to the indexer setter (i.e. set_Items)?

@KrzysztofCwalina, no, because when updating you get the existing value to use in determining what the new value should be. For example, if you wanted to count how many times something occurred, if you've not seen the thing before, you just add it with a count of 1, but if you have seen it before, you update it by adding 1 to whatever value was already there.

Ah, I just noticed the full signature of the method. I really think it's very specialized and we should be careful with adding such APIs to core types. It's a never ending stream of APIs with subtle differences and with diminishing returns in terms of value for the majority developers, but with added complexity cost.

@KrzysztofCwalina With normal dictionary, AddOrUpdate() doesn't add much, because you can write something like:

if (dict.ContainsKey(key))
    dict[key]++;
else
    dict[key] = 1;

(I think this is what you meant by "diminishing returns".)

But with concurrent dictionary, the code above wouldn't be thread-safe, and the correct code is much more complicated. So I think that having AddOrUpdate() and similar methods there is very useful, and not at all "specialized".

I am not saying that it should not be added. All I am saying is that the bar for such additions should be high. I worked on projects where hashtable APIs grew to something barely understandable because everybody wanted an API optimized for their corner case scenario. If we are sure that this is it (i.e. this is a mainline API for concurrent collections), then I have no objections.

In dotnet/corefx#426, I made some minor perf improvements to TryGetValue, GetOrAdd, and AddOrUpdate based on a suggestion from @KrzysztofCwalina to reuse the hash code wherever possible.

Privately I then implemented the suggested overloads, both internally on ConcurrentDictionary and as the above extension methods, to compare their performance. Before the change, I didn't see any measurable difference between doing these suggested overloads as extensions vs in the type's implementation. After the change, the difference was the same as mentioned in dotnet/corefx#426, anywhere from nothing to 10% (and of course it could be more if computing the hash code got ridiculously expensive, but that's not usually the case for common types used as keys in a dictionary).

As such, we could do these a bit more efficiently on the ConcurrentDictionary implementation, but at the same time performance of the implementation itself probably shouldn't be the driving factor. At this point, I'm still inclined to say we should add them, though, as ConcurrentDictionary is often used in performance-sensitive code, and if having the overloads there as an option can guide folks towards avoiding allocations in their own code, that alone could make it worthwhile.

We do need to be very careful though to avoid feature creep; there are lots of APIs in .NET that take delegates without a separate state parameter, and this pattern should really only be used on those where it's expected / demonstrated that they'll be used frequently in scenarios where avoiding the allocations is critical.

Thoughts?

Makes sense and thanks for doing the investigation and the PR. Separately, we should think about some general guidance for when to add delegate overloads with "context" parameters that allow to avoid creating closures.

We've reviewed this proposal and don't believe it's ready yet. Please take a look at the notes.

This implementation http://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentDictionary.cs,7996972d3d91c9d0 can produce deadlocks. Look at the comments.

        while (true)
        {
            TValue oldValue;
            if (TryGetValue(key, out oldValue))
            //key exists, try to update
            {
                //at this place Thread 2 deletes the key.
                newValue = updateValueFactory(key, oldValue);
                //there is no key, because it was deleted by Thread 2. TryUpdate will return false
                if (TryUpdate(key, newValue, oldValue))
                {
                    return newValue;
                }
                //at this place Thread 2 adds the key
                //and TryGetValue() at the beginning will return 'true'
            }

in this scenario there will be infinite loop.

GetOrAdd, AddOrUpdate are very usefull methods for ConcurentDictionary, because it's impossible to create such methods on the top of the API without locking access to the whole dictionary. Otherwise there is no guarantee that these operations perform atomically. This means that implementation of these methods should be inside ConcurentDictionary, using its internal synchronization objects.

Those would be quite handy indeed

On 20 Jan 2015, at 06:23, Sergey Zhukov notifications@github.com wrote:

GetOrAdd, AddOrUpdate are very usefull methods for ConcurentDictionary, because it's impossible to create such methods on the top of the API without locking access to the whole dictionary. Otherwise there is no guarantee that these operations perform atomically. This means that implementation of these methods should be inside ConcurentDictionary, using its internal synchronization objects.

—
Reply to this email directly or view it on GitHub.

@xplicit, this will not deadlock, nor in the absence of any other activity will it loop around. It's using standard optimistic concurrency techniques (you'll see loops similar in nature to this in many places where Interlocked.CompareExchange is employed), and if it fails to peform the add or the update because another thread managed to change the relevant state in the interim, then it will start over and try again... someone will always be making forward progress. While GetOrAdd internally is able to use the dictionary's lock(s) as part of the TryAdd call, it doesn't use it in the composite AddOrUpdate across calls to TryGetValue, TryUpdate, or TryAdd because that would result in running the user's delegate while holding the lock, and that's an even greater recipe for concurrency problems.

@stephentoub that's what I say too. It starts over and over again, which can produce infinite loop in the circumstances when two threads become synchronous to each other (running on two different cores or running on one core and get a context switch between them in the moments I pointed out). Even if they don't lock forever in real life (what is easy in theory) but only delays for a few milleseconds this can produce issues in real applications. I'd not like to understand in high-load multithreaded application why the code, which should work very fast, delays on a simply dictionary operation.

The calling user code in a lock can be avoided by using something like this:

lock (sync) {
   if (key exists) return value;
} 
//calling user delegate to create the object
var newObj =  userDelegate();
lock (sync) {
  if (key exists) return value;
  else {
       dictionary[key]=newObj;
  }
}

In this case user delegate are executed outside of lock block and it does not called in most cases when the key exists (for performance reasons).
I'm sure there is much more effective solution (which depends on ConcurentDictionary implementation) with more granular locks, but this just shows an idea how it can be done.

@xplicit, if you can create a more efficient AddOrUpdate and can demonstrate its superiority, please feel free to submit a PR, and we'll happily look at it. But, your pseudo-code is insufficient: in the case of an update, the delegate needs to be passed the existing value from the dictionary, and that value must still be the same as the one that's in dictionary when the replacement is performed... since between the time that the current value is accessed and the new value is stored the user delegate must be run with the former value to produce the latter value, I'm not clear on how you're expecting this to all be done in a thread-safe manner without either a) executing the delegate while holding the lock or b) using an optimistic concurrency loop like the one currently employed.

Regarding the hypothetical infinite loop or even milliseconds delay, can you share a compilable example that repros your concerns?

The pseudo-code was for GetOrAdd method, I look into current implementation of GetOrAdd and see it has been done in a same manner. You're right about the problem with passing current value to the factory.

The first sample about the infinite loop I've mentioned above (with two threads which works synchronous and one thread removes the key exact in the same time when the other tries to check it for update), if you're interested I can explain it more detaily. It's difficult to reproduce in real life, so I post another example, which can be reproduced more easily.

Let's say, we have a dictionary with predefined amount of keys.
Let's assume execution time of the TryGetValue(key1, out oldValue) - 1x, TryUpdate(key1, newValue, oldValue) - 1x, updateValueFactory(key1, oldValue) - 1000x (The times relation of TryUpdate(), TryGetValue() can be differ to each other, it does not matter. The main concern is that the updateValueFactory much slower than these functions). key1 - is a predefined key in the dictionary.

The first thread starts to run only one operation
AddOrUpdate(key1, ....)
The second thread in a loop changes the value of the key to the new random value.

while (true)
{
   var newValue=new randomValue();   //assume that this operation is almost immediately or comparable to 1x
   dict[key1]=newValue;                         //execution time 1x
}

Let's see the execution of the method AddOrUpdate

   if (TryGetValue(key, out oldValue))  //execution time 1x
   //key exists, try to update
   {
       newValue = updateValueFactory(key, oldValue);  //execution time 1000x
       //before we get to this point thread 2 updates the value of  'key1' 1000 times
       //and key value is not the same as it was passed to updateValueFactory 
       if (TryUpdate(key, newValue, oldValue))  //execution time 1x. 
       //The result will be always false (because oldValue differs from key value) 
       //and we will go into the loop again and again
       {
            return newValue;
        }
   }

So in this case operation AddOrUpdate() will never complete and will eat 100% of processor (core) resources. Maybe put user function in a lock associated with key/bucket will be a less evil. Or another solution (which of course has other issues like the key which has never got thread1 value): if someone was faster and updated the value between TryGetValue() and TryUpdate() then do not update the value at all (let say it was rewritten by another thread, before someone can read it)

@stephentoub @xplicit I think you're talking past each other. Using terminology for non-blocking operations:

@xplicit is saying "It's not wait-free" (a specific operation can theoretically take infinite amount of time, because of other operations).

@stephentoub is saying "It's lock-free" ("someone will always be making forward progress").

Those two are not mutually exclusive, wait-free is a stronger requirement, ConcurrentDictionary is only lock-free.

@svick, yes, that's a fair assessment, thanks.

@xplicit, any change that ran the user delegate under one of the locks would be vey prone to deadlock. All it would take, for example, would be for the delegate to call a method on the dictionary that requires taking all the locks (e.g. Clear), and deadlock becomes a very real and easily reproduced problem. I understand the theoretical concern around the loop, but I don't see an alternative. Regarding your second suggestion of not updating the value, isn't that something anyone could do just using TryGetValue and TryUpdate on their own?

This issue was reviewed today. It looks good as proposed.

Fixed by dotnet/corefx#1783

Hello @stephentoub
What if the value in the dictionary is some class and not a primitive type - for example a linked link for example of timestamps,
And when adding a key for the first time , I want to initialize the value to a list with current timestamp, and if the key already exists in the dictionary I want to append an item to the linkedlist.
How would you suggest to implement this to guarantee consistency of updates to the list ( in the scenario of having multiple threads calling the ConcurrentDictionary ). using the TryUpdate method with the comparisonValue doesn't work here since obvisouly the old and new linkedlists are the same class exact class. Also, as the documentation of MSDN specifies, using the AddOrUpdate method that gets delegates doesn't guarantee atomicy.

What if the value in the dictionary is some class and not a primitive type - for example a linked link for example of timestamps,
And when adding a key for the first time , I want to initialize the value to a list with current timestamp, and if the key already exists in the dictionary I want to append an item to the linkedlist.

LinkedListObj list = cd.GetOrAdd(key, k => CreateLinkedList(k));
lock (list) { list.Add(CurrentTimeStamp); }

Wow - really really appreciate your quick and smart reply !! :)
Seems to be working for me as well which is even better - I did some testings now.

So basically the calls to GetOrAdd might result in several empty linked lists being added and overriden (with the same key of course , due to lack of atomicy of the GetOrAdd as mentioned in MSDN) , but afterwards having the list at hand , the locking guarantees the consistency of the updates to the list.
Is this correct ?

Thanks a lot !!

Is this correct ?

Yup. Well, very close. If multiple threads race to create the entry for the key, they might each end up calling CreateLinkedList(), but only one of them will actually get added to the dictionary, and then whichever one got added will be the one that they all get handed back. Then as you say, they coordinate with each other with the lock on the specific linked list.

Great ! Thanks a lot for the explanation ! You're awesome :)