What is the preferred method of updating a reference to an immutable object?

Question

In case we have an immutable object like an ImmutableList(). What is the preferred method for using this object in a multi threaded environment?

Eg

public class MutableListOfObjects()
{
   private volatile ImmutableList objList;

   public class MutableListOfObjects()
   {
       objList = new ImmutableList();
   }

   void Add(object o)
   {
      // Adding a new object to a list will create a new list to ensure immutability of lists.

      // Is declaring the object as volatile enough or do we want to
      // use other threading concepts?
      objList = objList.Add(o);
   }

   // Will objList always use that lest version of the list
   bool Exist(object o)
   {
      return objList.Exist(o);
   }
}

Is declaring the reference volatile sufficient for achieving the desired behavior? Or is it preferable to use other threading functions?

@Romoku if something is genuinely immutable, then **that one object** is thread-safe to all common meanings. — Marc Gravell, May 13 '13 at 11:31
@Romoku a *reference* is by itself thread-safe (and indeed guaranteed atomic). What *is not* thread-safe is complex organisation and changing composition of references. But that is because we aren't being immutable. If the composition was immutable, it would again be thread-safe. — Marc Gravell, May 13 '13 at 11:44

score 6 · Answer 1 · answered May 13 '13 at 11:29

6

"Preferred" is contextual. The simplest approach is to use a lock, and in most cases that will do the job very effectively. If you have good reason to think that lock is a problem, then Interlocked is useful:

bool retry;
do {
    var snapshot = objList;
    var combined = snapshot.Add(o);
    retry = Interlocked.CompareExchange(ref objList, combined, snapshot)
              != snapshot;
} while(retry);

This basically works on an optimistic but checked path: most times through, it'll only go through once. Occasionally somebody will change the value of objList while we aren't looking - that's fine, we just try again.

There are, however, pre-canned implementations of thread-safe lists etc, by people who really know what they are talking about. Consider using ConcurrentBag<T> etc. Or just a List<T> with a lock.

answered May 13 '13 at 11:29

Marc Gravell

1,026,079
266
2,566
2,900

I tried to start a discussion about volatile and locking concepts for this example but indeed I think we can not avoid the lock. Even in your example do 2 threads always see the correct list? What if they start from the same snapshot, add different objects and replace the reference? – user2377470 May 13 '13 at 11:48
2

@user2377470 the point of `Interlocked.CompareExchange` is that it is exclusively atomic; say two threads A and B both run the `snapshot = ` and `combined = ` lines at the same time. When they call `CompareExchange`, it is **impossible** for them both to succeed. At least one of them is going to fail and have to retry. Note that the version of `CompareExchange` I'm using there is "as one atomic operation, compare the current value to this expected value; if it is the same, replace it with this new value; otherwise ***do nothing***; either way, tell me what the field was" – Marc Gravell May 13 '13 at 12:22

score 2 · Answer 2 · answered Oct 29 '20 at 14:53

A simple and efficient approach is to use ImmutableInterlocked.Update. You pass it a method to perform the add. It calls your add method and then atomically assigns the new value to objList if the list didn't change during the add. If the list changed, Update calls your add method again to retry. It keeps retrying until it is able to write the change.

ImmutableInterlocked.Update(ref objList, l => l.Add(o));

If you have a lot of write contention, such that you'd spend too much time on retries, then using a lock on some stable object (not objList) is preferable.

score 0 · Answer 3 · answered May 13 '13 at 11:26

volatile will not help you in this case - it will not create the lock between reading objList, calling Add() and assigning objList. You should use a locking mechanism instead. volatile just protects against operation reallocations.

In your case you are creating a new list every time an object is added - usually a much better alternative would be to create the list inside a local thread variable (so that it is not subject to multi-threading issues) and once the list is created, mark it as immutable or create a immutable wrapper for it. This way you will get much better performance and memory usage.

What is the preferred method of updating a reference to an immutable object?

3 Answers3

Linked