Do me a favor and just run in place for a little while

A lot of developers don’t realize that sometimes asking your CPU to just spin its wheels can be more efficient than using more sophisticated signaling mechanisms.

Here’s an example: you’ve got code where you need to check the value of a field, and if it meets a certain condition, you will update that field. Now this is a classic example of a race condition: if your software is running on multiple threads, it’s possible that another thread may change the value of the field between when you check and when you update it. Which means the update may no longer be valid.

In C#, a common case where this can happen is when you’re trying to do a computation involving floating point numbers, e.g., double. Say you have this simple Add operation:

public double Add(double value)
{
    _field += value;
    return _field;
}

Looks good, except that the += operator actually comprises two steps: getting the value at _field, and then actually modifying it. Classic race condition.

Here’s a fix (in most cases, honestly, probably the right one:

public double Add(double value)
{
    // Use a local.
    double field;

    // Be explicit about these two operations needing to be synchronized.
    lock (someLock)
    {
        field = _field;
        _field = field + value;
    }

    // Return the local to ensure the value returned isn't changed after releasing the lock.
    return field;
}

The thought behind such code is that surely using a lock statement is the best option here, allowing the CPU to do whatever work it wants to between synchronized accesses to the locked section.

Here’s an alternative:

public double Add(double value)
{
    // NOTE: no locking!
    double current, original;
    do
    {
        // Use a local.
        original = _field;

        // Compute the sum.
        double updated = original + value;

        // Update the field (maybe?)...
        current = Interlocked.CompareExchange(ref _field, updated, original);
    }
    // Repeat as many times as necessary for the two operations above to occur
    // without interruption.
    while (current != original);
}

Pretty weird, right? You wouldn’t normally think that a method could possibly be made more efficient by introducing a do loop. But depending on your circumstances, this may actually work wonders. It’s particularly worthwhile in scenarios where you’ve got lots of CPUs. The higher the number of parallel processes trying to get into a locked section, the more overhead you’ll find coming from thread contention.

And now here’s my attempt to make this all make sense intuitively.

Say you are the foreman at a construction site, and you’ve got 50 workers below you. They’re all working more or less independently, but when it comes to one specific resource, they all must share it and only one can use it at a time. Let’s say it’s a water fountain.

Now, you could approach this one of two ways. The first would be to give your workers these instructions:

Anyone who comes to the water fountain, if someone else is using it, let me know and then go back to work. When I see that the fountain is free, I will let you know, and you can proceed. If twenty of you want to drink from the water fountain all at once, you must all get back to work, and one by one I will let you know when you can have a drink.

Compare this to a very different approach:

Anyone who comes to the water fountain, if someone else is using it, just run in place or do some jumping jacks while the other person finishes. Then go ahead and take your turn. Do not bother me about this as I have more important matters to attend to. If twenty of you want to drink from the water fountain all at once, you should all just run in place until it’s your turn.

On the surface, that second approach might sound horribly stupid. And in a certain sense, it is. To spin the CPU telling it to literally do nothing feels, intuitively, very wasteful. But it can be a lot less wasteful than tasking the system (the foreman in the example) with monitoring a locked resource and going to the trouble of letting threads know when it’s their turn to access it. Just imagine being that foreman and having to track down every single worker who told you he wanted water, one at a time.

When you think of it that way, I think letting them run in place for a few short moments seems a lot more reasonable.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: