Monday 15 March 2010

Lock-free Synchronization in C# 4 Events

If you're keeping yourself up-to-date with .NET Framework 4.0 and C# 4, you might have read "Events get a little overhaul in C# 4" series on Chris Burrows' blog. He's explaining some changes to the intrinsic implementation of events. They were introduced in C# 4, which is in RC now. One important detail is that there are breaking changes included. So, you'd better get familiarized with that. If you haven't read his latest posts, please, do it now.

(intermission)

Welcome back. If you are fond of details like me, you might've gotten curious about that "lock-free synchronization code" used to add (and remove) event handlers in C# 4. That's exactly what I intend to show here.

The first step is simple. With a little help from Reflector, I disassembled the code generated for an simple event. After some variable renaming, here's what I've got:

private EventHandler dlgMyEvent;

public event EventHandler MyEvent
{
    add
    {
        EventHandler valueBeforeCombine;
        EventHandler valueBeforeAttribution = this.dlgMyEvent;
        do
        {
            valueBeforeCombine = valueBeforeAttribution;
            EventHandler newValue = (EventHandler) Delegate.Combine(valueBeforeCombine, value);
            valueBeforeAttribution = Interlocked.CompareExchange<EventHandler>(ref this.dlgMyEvent, newValue, valueBeforeCombine);
        }
        while (valueBeforeAttribution != valueBeforeCombine);
    }
    remove
    {
        // code ommitted (it's too similar to 'add')
    }
}

This code isn't obvious to understand (at least for me). I took quite some time to figure out what was happening. Of course, variables like handler2 and handler3 don't help much. I spared you from the trouble and renamed them.

Looking carefully, the secret ingredient is the Interlocked.CompareExchange. Since most people are not familiar with this function (I wasn't), let me explain it. An equivalent implementation would be like the code below. There's a very important difference, though. The real one runs as an atomic operation.
public static T CompareExchange<T>(ref T location, T value, T comparand)
{
    var previousValue = location;
    if (location == comparand) location = value;
    return previousValue;
}

Now, we have everything needed to comprehend the idea behind of the new event implementation. To make it crystal clear, let me expose it in human language. It goes like that:
  1. Copy this.dlgMyEvent into valueBeforeCombine;
  2. Create a new delegate called newValue by combining valueBeforeCombine with the supplied value;
  3. Atomically, verify that dlgMyEvent is equal to valueBeforeCombine, and overwrite dlgMyEvent with newValue;
  4. If the overwrite didn't happen (i.e., dlgMyEvent changed sometime between step 1 and 3), go back to step 1 and try everything again;
When I finally visualized this pattern, it felt like an epiphany. As a computer scientist, I'm ashamed of not knowing it before. Now, I know it's called compare-and-swap. Obviously, it can be used a other scenarios, but all this is very low-level coding. So, kids, don't try this at home. :)

I've a final comment. I decided to imitate MS and implemented a similar synchronization mechanism in my Custom Events. Here's the latest source download link.