+972 52-548-6969
Code review challengeThe concurrent dictionary refactoring
time to read 2 min | 216 words
In a recent code review, I had modified the following code:
_freeSegments.AddOrUpdate(memoryDataForPointer.SizeInBytes, x =>
{
var newQueue = new ConcurrentQueue<AllocatedMemoryData>();
newQueue.Enqueue(memoryDataForPointer);
return newQueue;
}, (x, queue) =>
{
queue.Enqueue(memoryDataForPointer);
return queue;
});
Into this code:
var q = _freeSegments.GetOrAdd(memoryDataForPointer.SizeInBytes,
size => new ConcurrentQueue<AllocatedMemoryData>());
q.Enqueue(memoryDataForPointer);
Can you tell me why?
More posts in "Code review challenge" series:
- (31 Dec 2015) The concurrent dictionary refactoring–answer
- (30 Dec 2015) The concurrent dictionary refactoring
Comments
create action can be called multiple times concurrently, and then all but one results will be discarded?
In the first code, the update function can be called multiple times and then the same item is queues multiple times.
The first code would have been correct if you had been using an ImmutableQueue.
The documentation for ConcurrentDictionary notes that its atomicity guarantees do not extend to callbacks. It also notes that the add callback may be called multiple times and that not all the values returned will necessarily get added to the dictionary. It does not say anything about the update method, so it's not entirely clear whether that might see multiple calls, but if that is a possibility, it's important to move the call to Enqueue out of that callback.
(I'm guessing this is probably not the answer though, because the documentation around the race conditions that afflict AddOrUpdate and GetOrAdd are entirely concerned with calls to the Add callback whose results are ultimately abandoned, and not the update callback. I'd be surprised if you ever did see a double update callback in practice - if there is a scenario in which that happens, it's not evident from the documentation.)
Improved readability, reduced duplication. Depending on how things are called, you could have a modified closure around memoryDataForPointer iirc.
Other people have probably answered the real issue, but the GetOrAdd version has the added benefit of one less allocation for delegates, in fact since the delegate in question captures no state it can be allocated just once. Meaning only the queue will be allocated if it did not exist already.
There is no need to lock the dictionary for duration of update.
It's evident that you desire to add a queue to a dictionary if it's not there, or to update content of the queue which is already in the dictionary.
Second variant of code has performance benefit for two reasons.
First one: There is no need to hold lock for duration of updating the value. Since you're code is not replacing a reference, and since the object in question is ConcurrentQueue, we can be free to release the dictionary before updating the queue.
Second one: Lock duration for adding a value can be shortened by just adding an empty queue. We can release the dictionary and later insert new items to ConcurrentQueue.
Wouldn't be even more performant to do following? var newQueue = new ConcurrentQueue<AllocatedMemoryData>(); var q = _freeSegments.GetOrAdd(memoryDataForPointer.SizeInBytes, newQueue); q.Enqueue(memoryDataForPointer);
My guess is that in that case we save a method invocation in case of adding and hold the lock for shorter time.
After inspecting ConcurrentDictionary with ILSpy I see that it doesn't actually hold locks while executing delegates.
So I'm correcting myself. First version of code locks the dictionary in either case, whether values are being added or updated. Second version locks the dictionary in case of adding a new key/value pair. In case of updating the pair, there is no need for locking. Update concurrency is handled by the ConcurrentQueue itself.
Three reasons I can see immediately.
1) Removal of duplicate code.
2) The less work performed in a concurrent function, the less time resources have be locked.
3) Since ConcurrentQueue is itself concurrent, there is no need to use Enqueue() from within an atomic callback.
Cheers.
The Add delegate will not be synchronized by the ConcurrentDictionary which can cause multiple instances of the newQueue variable to be created in multiple threads.
Rafal, That is an issue, yes, but it isn't an important one. It might cause a few allocations, but not significant ones. That is a relatively rare occurrence, and it won't actually impact the system
Patrick, You are correct in principal, but that isn't actually how it works. See the code here: http://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentDictionary.cs,1148
In this case, we are returning the same value, so that will result in an always successful update. So this end up behaving correctly, although that is not ensured by the contract, mind.
Note that this is still doing a lot more work than we want it to do, because the TryUpdate needs to take a lock: http://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentDictionary.cs,562
This is typically an uncontended lock, though
HarryDev, Yes, that is what we are aiming at. This method has no locks, no allocations, and it is very cheap
Nikola, There are no locks held during the update or add. And your code will require us to do an extra allocation (of a relatively large object) on each call
because easy to read
Update with the same value is pointless. When a key exists in the dictionary you don't want to associate a different queue to the key, in other words, you don't want to update the dictionary entry, what you really want is to add a new entry to the queue associated to the key, so AddOrUpdate is no sense. Additionally, I'ts more complex. The refactorized code is to the point, simpler, more readable, and I bet it's faster.
I see two reason of making changes. 1. SRP violation in old method AddorUpdate(). 2. Duplicate code for Adding new item to dictionary.
Comment preview