ConcurrentDictionary Pitfall - Are delegates factories from GetOrAdd and AddOrUpdate synchronized?

Question

The documentation of ConcurrentDictionary doesn't explicit state, so I guess we cannot expect that delegates valueFactory and updateValueFactory have their execution synchronized (from GetOrAdd() and AddOrUpdate() operations respectively).

So, I think we cannot implement use of resources inside them which need concurrent control without manually implementing our own concurrent control, maybe just using [MethodImpl(MethodImplOptions.Synchronized)] over the delegates.

Am I right? Or the fact that ConcurrentDictionary is thread-safe we can expect that calls to these delegates are automatically synchronized (thread-safe too)?

Solution 1

Yes, you are right, the user delegates are not synchronized by ConcurrentDictionary. If you need those synchronized it is your responsibility.

The MSDN itself says:

Also, although all methods of ConcurrentDictionary are thread-safe, 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. (This is done to prevent unknown code from blocking all threads.)

See "How to: Add and Remove Items from a ConcurrentDictionary

This is because the ConcurrentDictionary has no idea what the delegate you provide will do or its performance, so if it attempted lock around them, it could really impact performance negatively and ruin the value of the ConcurrentDictionary.

Thus, it is the user's responsibility to synchronize their delegate if that is necessary. The MSDN link above actually has a good example of the guarantees it does and does not make.

Solution 2

Not only are these delegates not synchronized, but they are not even guaranteed to happen only once. They can, in fact, be executed multiple times per call to AddOrUpdate.

For example, the algorithm for AddOrUpdate looks something like this.

TValue value;
do
{
  if (!TryGetValue(...))
  {
    value = addValueFactory(key);
    if (!TryAddInternal(...))
    {
      continue;
    }
    return value;
  }
  value = updateValueFactory(key);
} 
while (!TryUpdate(...))
return value;

Note two things here.

• There is no effort to synchronize execution of the delegates.
• The delegates may get executed more than once since they are invoked inside the loop.

So you need to make sure you do two things.

• Provide your own synchronization for the delegates.
• Make sure your delegates do not have any side effects that depend on the number of times they are executed.

Comments

[Brian Gideon]

@Luciano: I just checked and GetOrAdd appears to call ValueFactory a single time. So it is only AddOrUpdate that has the potential to call the delegates multiple times. That may be a bug on Microsoft's part...not sure. I discovered this a long time while answering a similar question.

[Luciano]

@BrianGideon: Off course, sorry I haven't noticed you were talking about AddOrUpdate rather than GetOrAdd. Thanks for answering.

[Sebastian]

Has this behaviour changed in any way so far?

[Brian Gideon]

@SebastianGodelet: I'm not sure. It does seem more like a bug so it is possible that this behavior gets "fixed" eventually.

[Softlion]

I confirm thatn as of 2012/08/22, GetOrAdd delegate is still called multiple times It is not a bug, but makes concurrentdictionary useless.See accepted answer.

[Brian Gideon]

@Softlion: That is unfortunate. It certainly diminishes the usefulness of AddOrUpdate. It looks like there could be some trivial enhancements to the logic to prevent those delegates from executing more than once so I'm a bit disappointed that Microsoft hasn't changed the logic yet.

[Softlion]

I understand the Ms point of view "don't call our support for this" or "be safe, stay home" which drives this implementation. It's a 0% risk point of view. But it so implied by the "concurrency" adjective that we now all have non-working code ! It may at least be opt-in with a warning in the doc... I'm lucky i found out something's going strange and dig it ... Otherwise non-working code would have been released to lots of customers.

[John]

So I am wrapping the GetOrAdd method call in a lock but that makes the purpose of the ConcurrentDictionary useless. Is there a best way?

[binki]

Actually, knowing that is uses this pattern is helpful. If your only goal is to determine which item in the dictionary was replaced during the AddOrUpdate(), you merely need to set a local variable to null in addValueFactory and set it to the value passed to updateValueFactory. If the loop needs to go again because conditions changed by the time it calls TryUpdate, the next loop will update your local correctly. And when it succeeds, your local will have the replaced value that actually was replaced (or null if it ended up not existing by the time the call succeeded).

[Snoop]

I am a bit confused by this, are we basically saying that if a delegate is passed as the key, that its execution will not be synchronized in evaluating the value? Or if we have a dictionary with type "delegate" as the value... that when we try to execute the delegate (i.e. dictionary[key](argument);) that the execution will not be synchronized? Or, am I missing the point entirely? Thanks.

[Snoop]

@BrianGideon Looks like James hasn't been on in a while, wondering if you could help (check my comment on James' answer). Thanks.

[Snoop]

@Luciano Can you also help me understand this?

[Brian Gideon]

@Snoopy: The delegate evaluating the value to add is not synchronized. This means that if your delegate does something that isn't thread-safe and you didn't make an attempt to synchronize that operation yourself then bad things will happen. But, the thing a delegate that acts as factory for a value wouldn't typically being doing things that aren't thread-safe by nature. Most of the time the delegate is probably just doing new SomeObject() which is definitely thread-safe because it's a stateless operation.

[David Burg]

@John: The part that isn't explained well, yet that makes it still valuable, is while the delegates may be executed multiple times, only if the value at the key has not been changed once the delegate has generated a new value then will the new value be inserted, otherwise -if the value changed while the delegate was running- it will try again.