Manage states in a multi-threaded environment without the synchronization pain

I see 4 common ways to deal with states in a multi-threaded environment:

  • Immutable objects: The idea is simple and efficient: make sure that the states of objects cannot be changed. This way, the object can be accessed concurrently by multiple threads without any risk of state corruption or thread race. I wrote a blog post on how to implement immutability with C# and how you can use NDepend facilities to enforce object immutability and method purity.
  •  Thread / Resource affinity: The idea is as simple as it is efficient here also: making sure that an object is always accessed by the same thread. The .NET Framework offers several ways to implement this paradigm: the System.ThreadStatic attribute on fields, Thread Local Storage API and the interface ISynchronizeInvokeThese are described in this article I published on CodeProject.
  • Synchronized objects / Thread-Safe class: Since v1.0, the .NET Framework comes natively with a way to implement synchronized objects through the lock C#/VB.NET keyword, alias the Monitor class. I found it convenient to implement this pattern this way.
  • Synchronization objects: The .NET Framework comes with several synchronization API. Some of them are based on Windows synchronization primitives (events, mutex, semaphore) and some of them are implemented by the CLR (ReaderWriterLock). These API have been proven to be not optimal and even buggy, with possible starvation phenomenon in some particular cases.

The cost of synchronizing

The goal of this post is to praise immutability and affinity over synchronization. There are 2 killer arguments against synchronization:

  • First, immutability and affinity are so efficient by-design that once you go with them you won’t get anymore any concurrent access bug. Every experienced programmer knows that synchronizing accesses to states is a real pain and generally ends-up in all sorts of non-deterministic bugs very hard to pinpoint and correct. 
  • Second immutability and affinity won’t hurt performance. Synchronizing thread accesses to states leads to thread-context-switches that are extremely costly. Also, threads are very expensive resources that are wasted each time a thread is put in a wait state. I agree that immutability sometime provokes extra object creation but frankly, this is neglectable compare to threading cost.

Why most of developers still opt for synchronization?

First it is a matter of education. Every programmer academic background comes with a course on how to program in a multi-threaded environment with synchronization primitives. This is an entertaining course illustrated with pleasant concurrent patterns and as far as I know, tricks such as immutability and affinity are not presented. 

Second, at first glance immutability and affinity doesn’t seem to solve any problem. In both case there are no shared and mutable states. And this is what programmers want: being able to read and write a state from several threads. Just have a look at this comment on my blog post on immutability

  • I’m doing concurrency because I want to calculate lots of things in parallel.  I want them to change. Immutable types don’t help concurrency much.  Sure you can prevent accidental changes to things that shouldn’t change.  Of course that’s just as valuable when coding single threaded.  I really don’t think you can have done much concurrent programming.

Immutable object / Changing state

Immutability is more subtle than this. The string class is immutable for example. Did you hear any programmer complain that he cannot code multi-threaded access to its strings? No, and the non-obvious reason actually lies in how we consider the state’s identity. A state is typically identified by an object and we write things like:

Person person = new Person(“Julien”);

person.FirstName = “Mathieu”;

We also write things like:

string personFirstName = “Julien”;

personFirstName = “Mathieu”;

The difference is that in the first case we have non-thread safe code because the object person can be read/write accessed by several threads. In the second case the state personFirstName had also been modified but now we won’t get multi-threading issue because the string class is immutable and the same state is handled by 2 different strings. We are losing the common one-to-one relation between a state and the underlying object. In other words, the identity of the state is not the object anymore but the value itself. But still, the state has been changed! The programmer is now free to expose the new “Mathieu” state to other threads without any kind of synchronization infrastructure.

The beauty of thread /resource affinity

 Thread / Resource affinity is also a concept that deserves more attention. It promotes task-oriented programming. A task is thoroughly executed by the same thread, from A to Z, and its states are not visible from other tasks. One famous application of affinity is the way win32/Windows Form works. For a given form, all tasks are executed by the same thread, essentially painting/refreshing/timer operations and input/mouse/keyboard event handlers.

The immense benefit that Windows Form users get is that we can be sure that the mouse click event handler won’t be triggered while the windows is re-painted. Thus all the states maintained behind our form don’t need to be synchronized. As we know, the down-side effect is that doing computation from the UI thread leads to unresponsive UI, and this is why there are tricks such as the BackgroundWorker class to make it easy to trigger task on tier threads.

To implement affinity, personally I am not a fan of ThreadStatic or Thread Local Storage because they both rely on costly Windows and CLR internals. Also, I remember this article from Juval Lowy that explains how to implement ISynchronizeInvoke but I especially remember how complicated and error-prone it is. I prefer to implement affinity by myself by:

  • Preferring to maintain states with thread affinity from method local variables instead of object fields. Local variables are by-design bound to the current thread. 
  • Writing contracts about affinity. Concretely, all methods of a class begin with something like:

Debug.Assert( MyHelperPlumbing.CurrentThreadIsInitialThread() );

The code is less readable but as long as the language teams don’t provide DbC facilities we don’t have the choice.

We are currently removing most of synchronized accesses from the code of NDepend. This is a needed refactoring that will greatly simplify the development of features we want to do next. I admit that managing changing states through immutable objects sometime require some intellectual gymnastic. For example, if the object tagged by a DataGridViewRow is immutable, the tag property needs to be updated when the state is changing. But clearly, this is a minor programming exercise compare to synchronization nightmare.

 

 

This entry was posted in Concurrency. Bookmark the permalink. Follow any comments here with the RSS feed for this post.
  • http://www.NDepend.com Patrick Smacchia

    Jared,

    I think there is a misunderstanding. The Debug.Assert(…) you are referencing is here to enforce the object / resource affinity and not to detect a race condition.

    I agree that race conditions problems sometime don’t appear in release mode and thus, contract with Debug.Assert(…) can sometime be not helpful. Also, a shared state can be sane during the execution of Debug.Assert(..) and corrupted just during the execution of the next instruction.

  • http://blogs.msdn.com/jaredpar Jared Parsons

    Good post but one point I don’t agree with.

    Debug.Assert( MyHelperPlumbing.CurrentThreadIsInitialThread() );

    A debug assert is great but ideally this should be a retail contract vs. a debug assert. As you pointed out debugging race conditions is a nightmare at best. This type of check can be invaluable when tracking down a race condition bug. Unfortunately there are many race conditions that just don’t repro in debug code. Moving this to a retail contract will help ensure that 1) your code fails and fails fast and 2) you learn about the race condition at the earliest possible moment.

  • http://weblogs.asp.net/gbarnett Granville Barnett

    Interesting.

    I have always been a fan of the immutable approach despite its larger memory demand – but like you say the cost of synchronisation is steep.