by Chris Cavanagh

ImmutableInterlocked

The Immutable Collections package is awesome.  If you’re writing concurrent code, immutable collections should be your new best friends (along with immutable classes in general).  Explicit locking is bad, bad, bad, with an extra helping of bad (repeat this until it sticks).

A typical pattern you’ll see when modifying a collection looks like this:

myCollection = myCollection.Add( "Banana" );

However if the “myCollection” above is a field you’re sharing between threads, you still need to protect it.  This is easy with the System.Threading.Interlocked helpers:

Interlocked.Exchange(
    ref myCollection,
    myCollection.Add( "Banana" ) );

But what if you’re updating an ImmutableDictionary and need an atomic update, so it’ll only add an item if it doesn’t exist?  Here’s where the ImmutableInterlocked helpers come in:

private ImmutableDictionary<string, Fruit> myDictionary
    = ImmutableDictionary<string, Fruit>.Empty;
…
var fruit = ImmutableInterlocked.GetOrAdd(
    ref myDictionary,
    "banana",
    new Banana() );

Now things could get interesting.  You’ll notice on the line above we create a new Banana instance.  If “banana” already exists in the dictionary, the nice fresh Banana we created will just be discarded.  In many cases this isn’t a problem (maybe a slip hazard); it’s just a redundant object creation.

But what if it’s something we only want to create once, and only if it doesn’t exist?  ImmutableInterlocked has a GetOrAdd override that takes a delegate:

var fruit = ImmutableInterlocked.GetOrAdd(
    ref myDictionary,
    "banana",
    _ => new Banana() );

It sure looks promising.  Presumably it only calls the delegate if the item isn’t in the dictionary?…  Nope!  Apparently it always calls the delegate, checks if the item exists, and discards the result if it does (while the source code isn’t currently available, we can get a vague idea how it might be implemented from this Unofficial port of Immutable Collections).

So it seems we need another solution.  We really don’t want to explicitly lock anything (bad, bad, bad).  Turns out we can get this for “free” if we use Lazy<T>:

private ImmutableDictionary<string, Lazy<Fruit>> myDictionary
    = ImmutableDictionary<string, Lazy<Fruit>>.Empty;
…
var fruit = ImmutableInterlocked.GetOrAdd(
    ref myDictionary,
    "banana",
    new Lazy<Fruit>( () => new Banana(), true ) ).Value;

This ensures there’s a Lazy<Fruit> in the dictionary that knows how to create a Banana on demand.  Lazy<T> already takes care of ensuring only one thread can actually create the instance.  It does some internal locking of its own, but apparently it’s super efficient so we can happily ignore it and go on our way.

Hope this helps!

5 Comments

      1. I used following flow, ImmutableInterlocked.GetOrAdd (for initial attempt), if I determined that the existing item had ‘expired’ and I needed to update it, I called ImmutableInterlocked.TryUpdate (for attempted update ‘lock’, i.e. it’ll take a bit to complete entire update, so I TryUpdate something quick, and if successful continue on), finally, after doing ‘lengthy’ update process, I use dict.SetItem( key, new Lazy( () => myT, true ) ). Wonder if InterLocked.Exchange is ‘same’ as dict.SetItem or if one i preferable to another?

  2. I’m pretty sure using Interlocked.Exchange() the way you are doing to protect the immutable collection is not safe at all.

    The call to myCollection.Add() will be performed before the call to Exchange(), and thus is not part of the atomic operation. It’s totally possible for two threads to perform that Add() first, and then both do the Exchange(), with the add done by the first being overwritten by the second.

    What you should be doing is:

    ImmutableInterlocked.Update(ref myCollection, x => x.Add(“Banana”));

    Reply

Leave a comment