Verify ConcurrentDictionary use, taking into account GetOrAdd can call creation callback more than once

[rclabo]

Recently I saw that David Fowler, lead architect on the .Net Core team at Microsoft, commented that one of the common issues that he has observed is that when people use ConcurrentDictionary they don't take into account that the GetOrAdd method executes the creation callback more than once.

And this can be a problem if the code is creating something expensive for example.

Apparently this is documented but certainly not the behavior that one would expect. We should review the use of ConcurrentDictionary GetOrAdd calls to ensure we are accounting for this odd behavior.

[jeme]

David Fowlers statement makes it sound like the implementation would call "the" callback (singular) multiple times, I don't feel like that is quite an accurate way of describing the behavior. In the actual behavior, it makes a bit more sense why this happens.

The basics is that the factory is called outside of a lock, which means if you call GetOrAdd simultaneously on two threads, each or their value factories will be executed.

This may be a good read: https://andrewlock.net/making-getoradd-on-concurrentdictionary-thread-safe-using-lazy/

Usages:

ConcurrentDictionary<TKey, TValue>

Reference source:

• https://github.com/dotnet/runtime/blob/8399bae467ad521af58d37ae0fa27fd7df9e5e26/src/libraries/System.Collections.Concurrent/src/System/Collections/Concurrent/ConcurrentDictionary.cs
• https://github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/Concurrent/ConcurrentDictionary.cs
• https://github.com/dotnet/corefx/blob/v3.1.12/src/System.Collections.Concurrent/src/System/Collections/Concurrent/ConcurrentDictionary.cs

GetOrAdd

Lucene.Net:
https://github.com/apache/lucenenet/blob/master/src/Lucene.Net/Support/IO/FileSupport.cs#L363
-> Probably not that big of a deal, paths are always of a limited length so the code should be reasonably fast and produce the same result.

https://github.com/apache/lucenenet/blob/master/src/Lucene.Net/Support/Configuration/EnvironmentVariablesConfigurationProvider.cs#L67
-> Probably not that big of a deal, It should produce the same result and is not likely to be that expensive.

https://github.com/apache/lucenenet/blob/master/src/Lucene.Net/Search/SearcherLifetimeManager.cs#L174
-> Already uses lazy so the worst case scenario here is that we end up creating to Lazy objects, then discarding one of them immediately and never running it's factory.

Lucene.Net.TestFramework:

lucenenet/src/Lucene.Net.TestFramework/Support/Configuration/TestConfigurationFactory.cs

Line 56 in f5cca0b

return configurationCache.GetOrAdd(testDirectory, (key) =>

-> Could be candidate for using Lazy pattern unless we say that this is "TestFramework" and therefore unlikely to cause a problem. Also I did not dive deep into what the builder does and how expensive it is. The fix is not that problematic in the end though.

Lucene.Net.Spatial:

lucenenet/src/Lucene.Net.Spatial/Prefix/PrefixTreeStrategy.cs

Line 225 in d5c5ca4

var p = provider.GetOrAdd(FieldName, f => new PointPrefixTreeFieldCacheProvider(m_grid, FieldName, m_defaultFieldValuesArrayLen));

-> Assuming inexpensive call to constructor.

AddOrUpdate

Could not find any usages.

ConditionalWeakTable<TKey, TValue>

Reference source:

• https://github.com/dotnet/runtime/blob/c1a21a031925ce6261fadcfed26e098ab1bf46a6/src/libraries/System.Private.CoreLib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs

GetValue

AddOrUpdate

GetOrCreateValue

LurchTable<TKey, TValue>

GetOrAdd

AddOrUpdate

[NightOwl888]

@jeme

Thanks for the insight. Lazy<T> does seem like a reasonable remedy in most (all?) cases where the call is expensive or needs to be atomic for another reason.

NOTE: I have read that LazyInitializer is faster than Lazy<T>, but given the fact that the former uses static methods I am not sure if we can find a way to make use of it in this scenario.

However, GetOrAdd is not the only API we need to watch out for. There are several usages of APIs of collections that may have been assumed to be atomic where locks have been replaced with these API calls, where the documentation states the calls are made outside of the context of locks.

ConditionalWeakTable<TKey, TValue>

• GetValue
• AddOrUpdate
• GetOrCreateValue

ConcurrentDictionary<TKey, TValue>

• AddOrUpdate
• GetOrAdd

LurchTable<TKey, TValue>

• GetOrAdd
• GetOrAdd
• AddOrUpdate

In addition, we should expand the search to include all of Lucene.NET's dependencies that we maintain.

• J2N
• ICU4N
• Spatial4n
• Morfologik.Stemming

Although the documentation doesn't specify that locking is an issue with TryGet, TryAdd, TryRemove, we should probably do a code review on those methods of the above collections (where applicable) as well as any caches that are built using them to ensure we are not missing any important locks.

Just doing a quick survey, I noticed there are some calls that should have locks in J2N and it is suspected that this may be the source of concurrency issues with ThaiTokenizer and ICUTokenizer tests of Lucene.NET, which are known to fail without extra locking that was not part of the original design as a result of missing locks in ICU4N.

[rclabo]

@jeme Great research. Thanks for pointing out Andrew Locks' article which explains the situation well. It was a good read.