Using Bcl ImmutableDictionary in private field

Question

Let's say I have a class that will be called from multiple threads, and am going to store some data in an ImmutableDictionary in a private field in this class

public class Something {
    private ImmutableDictionary<string,string> _dict;
    public Something() {
       _dict = ImmutableDictionary<string,string>.Empty;
    }

    public void Add(string key, string value) {

       if(!_dict.ContainsKey(key)) {
          _dict = _dict.Add(key,value);
       }
    }
}

Could this be called in such a way by multiple threads that you will get an error about the key already existing in the dictionary?

Thread1 checks dictionary sees false Thread2 checks dictionary sees false Thread1 adds value and reference to _dict is updated Thread2 adds value, but it is already added because it uses the same reference?

Answer 1

You can absolutely be thread-safe in your use of immutable dictionary. The data structure itself is perfectly thread-safe, but you applying changes to it in a multi-threaded environment must be carefully written to avoid data loss in your own code.

Here is a pattern I use frequently for just such a scenario. It requires no locks, since the only mutation we do is a single memory assignment. If you have to set multiple fields, you need to use a lock.

using System.Threading;

public class Something {
    private ImmutableDictionary<string, string> dict = ImmutableDictionary<string, string>.Empty;

    public void Add(string key, string value) {
       // It is important that the contents of this loop have no side-effects
       // since they can be repeated when a race condition is detected.
       do {
          var original = _dict;
          if (local.ContainsKey(key)) {
             return;
          }

          var changed = original.Add(key,value);
          // The while loop condition will try assigning the changed dictionary
          // back to the field. If it hasn't changed by another thread in the
          // meantime, we assign the field and break out of the loop. But if another
          // thread won the race (by changing the field while we were in an 
          // iteration of this loop), we'll loop and try again.
       } while (Interlocked.CompareExchange(ref this.dict, changed, original) != original);
    }
}

In fact, I use this pattern so frequently I've defined a static method for this purpose:

/// <summary>
/// Optimistically performs some value transformation based on some field and tries to apply it back to the field,
/// retrying as many times as necessary until no other thread is manipulating the same field.
/// </summary>
/// <typeparam name="T">The type of data.</typeparam>
/// <param name="hotLocation">The field that may be manipulated by multiple threads.</param>
/// <param name="applyChange">A function that receives the unchanged value and returns the changed value.</param>
public static bool ApplyChangeOptimistically<T>(ref T hotLocation, Func<T, T> applyChange) where T : class
{
    Requires.NotNull(applyChange, "applyChange");

    bool successful;
    do
    {
        Thread.MemoryBarrier();
        T oldValue = hotLocation;
        T newValue = applyChange(oldValue);
        if (Object.ReferenceEquals(oldValue, newValue))
        {
            // No change was actually required.
            return false;
        }

        T actualOldValue = Interlocked.CompareExchange<T>(ref hotLocation, newValue, oldValue);
        successful = Object.ReferenceEquals(oldValue, actualOldValue);
    }
    while (!successful);

    Thread.MemoryBarrier();
    return true;
}

Your Add method then gets much simpler:

public class Something {
    private ImmutableDictionary<string, string> dict = ImmutableDictionary<string, string>.Empty;

    public void Add(string key, string value) {
       ApplyChangeOptimistically(
          ref this.dict,
          d => d.ContainsKey(key) ? d : d.Add(key, value));
    }
}

Answer 2

Yes, just the same race as usual applies (both threads read, find nothing, then both threads write). Thread-safety is not a property of a data-structure but of an entire system.

There is another problem: Concurrent writes to different keys will just lose writes.

What you need is a ConcurrentDictionary. You cannot make this work with the immutable one without an additional lock or a CAS-loop.

Update: The comments convinced me that an ImmutableDictionary used with a CAS-loop for writes is actually a very good idea if writes are infrequent. Read performance will be very nice and writes as cheap as it gets with a synchronized data structure.

Answer 3

There is now a class available in the BCL to do the same CAS loops. These are very similar to the extension method in Andrew Arnott's answer.

The code would look like this:

ImmutableInterlocked.AddOrUpdate(ref _dict, key, value, (k, v) => v);

Answer 4

Accessing the instance variable makes the Add() method non-reentrant. Copy/re-assign to the instance variable doesn't change the non-reentrancy (it is still prone to race conditions). A ConcurrentDictionary in this case will allow access without total consistency, but also without locking. If there is need for 100% consistency across threads (unlikely), then some kind of lock on the Dictionary is necessary. It's very important to understand that visibility and scope are two different things. Whether an instance variable is private or not has no bearing on its scope, and thus on its thread safety.