What's the difference between a ConcurrentDictionary and an ImmutableDictionary?

Question

I am reading Concurrency in C# Cookbook and the book told me that:

ConcurrentDictionary<TKey, TValue> is best when you have multiple threads reading and writing to a shared collection. If the updates are not constant (if they’re more rare), than ImmutableDictionary<TKey,TValue> may be a better choice.

I know that Add or Remove a large immutable collection can be slow, and my question is, is there any other difference between them? Now that they are all thread safe, why is ImmutableDictionary a better choice when the updates are not constant?

Answer 1

Here are the main differences between a ConcurrentDictionary<K,V> and an ImmutableDictionary<K,V>, in the context of a multithreaded environment.

1. The ConcurrentDictionary<K,V> is a hash-based collection, similar to the Dictionary<K,V>. Getting the value of a key is an O(1) operation (constant time, regardless of the number of elements). On the contrary the ImmutableDictionary<K,V> is a balanced binary tree, and getting the value of a key is an O(log N) operation. In both cases reading is lock-free.

2. Updating a ConcurrentDictionary<K,V> requires acquiring a lock. The ConcurrentDictionary<K,V> maintains multiple locker objects internally, so contention is normally not an issue. On the contrary updating a ImmutableDictionary<K,V> requires an Interlocked operation, which is generally cheaper than acquiring a lock, but is more susceptible to contention because all threads are attempting to Interlocked.CompareExchange the same memory location. The computational complexity is the same as before, O(1) for the ConcurrentDictionary<K,V> and O(log N) for the ImmutableDictionary<K,V>.

3. The ImmutableDictionary<K,V> can provide a snapshot of its contents for free, because each instance is essentially a snapshot. The contents of an ImmutableDictionary<K,V> instance are never affected by future modifications. On the contrary getting a snapshot of a ConcurrentDictionary<K,V> with the ToArray method is expensive. It requires the acquisition of all its internal lockers, and then the copying of all its contents in an array.

4. The Count property is cheap for the ImmutableDictionary<K,V> and expensive for the ConcurrentDictionary<K,V>. In both cases the property has snapshot semantics.

5. Updating an ImmutableDictionary<K,V> is more allocatey than updating a ConcurrentDictionary<K,V>. It creates more garbage that has to be recycled by the garbage collector. This is the cost of the free snapshots.

6. When a ConcurrentDictionary<K,V> has to be updated with a new value that depends on the existing value of the key, the performance is sensitive to the default equality comparer of the TValue. So if the EqualityComparer<TValue>.Default.Equals happens to be expensive, updating the dictionary will be expensive. More info about this undocumented behavior can be found here. The ImmutableDictionary<K,V> is not much different. It also compares TValues with one another during updates, but at least it provides a way to customize the valueComparer that is used internally by the collection with the WithComparers API. It should be noted that the hidden dependency on the default TValue comparer has thread-safety implications as well, for both collections.

7. The semantics of enumerating a ImmutableDictionary<K,V> are straightforward. On the contrary the semantics of the ConcurrentDictionary<K,V>.GetEnumerator are loosely defined. For example it's not guaranteed that a single enumeration of a ConcurrentDictionary<K,V> will return unique keys. Currently it does (.NET 9), but according to Microsoft this behavior is accidental ("a side-effect of the chosen implementation, rather than a guarantee the dev was trying to make."). Neither collection preserves the insertion order of the keys.

8. The ConcurrentDictionary<K,V> has a more familiar API. The ImmutableDictionary<K,V>, like all immutable collections, has unintuitive methods that return a new collection instead of mutating the existing collection. Working with immutable collections requires a small period of familiarization, until you stop doing rookie mistakes like calling Add and ignoring the result of the call.

I'll close this answer with an example of how to increment a value of a ConcurrentDictionary<TKey,int>, and then an ImmutableDictionary<TKey,int>:

_dictionary.AddOrUpdate(key, 1, (k, existing) => existing + 1);

ImmutableInterlocked.AddOrUpdate(ref _dictionary, key, 1, (k, existing) => existing + 1);

The ImmutableInterlocked.AddOrUpdate API replaces the existing dictionary with a new dictionary that contains the value returned by the updateValueFactory delegate. The updateValueFactory might be called more than once per each AddOrUpdate operation. In case you are interested to see the implementation of this API, the source code is here.

Answer 2

These two classes ConcurrentDictionary and ImmutableDictionary were compared just because of the simple reason, both are thread safe.

However, it is not a good idea to use ImmutableDictionary for multi-threading. It is designed to represent data which should be loaded once, and shouldn't be changed / modified later on. Any modifications would lead to creating new instance of ImmutableDictionary, which is not really efficient.

Answer 3

Immutable can't be changed, i.e. no add/remove can alter existing dictionary, rather would create a new one shipping all but deleted item. Concurrency proceeds on the lock { } statement which has nothing to do with immutability. Locks are necessary to manage write operations done by more than single thread to the same memory piece (i.e. same object).