Ultimately, the whole point of a lock is to take a multi-part operation and make it atomic. The AddDagron() function from the previous post in the series, for example, takes the operations of incrementing the Dagron count, reallocating the array of Dagron pointers, and adding the new Dagron to the array, and effectively turns it into one operation. In order to accomplish that, though, we have a large structure (CRITICAL_SECTION takes up around 24 bytes in 32-bit), and we are forced to acknowledge that our quote-unquote “atomic” operation may actually be broken up into multiple pieces.

Wouldn’t it be cool if we could actually execute a complex sequence of operations in one CPU instruction? If we had such an operation, then there would be no way to interrupt it in the middle, and it would be truly atomic.

Fortunately, if we’re willing to narrow the scope of what operations we’d like to perform, then we already live in that world. Modern processors provide a set of instructions that let you perform some very interesting operations in precisely one CPU instruction.

You can see a full list of all Interlocked operations in Windows on this page. They all have esoteric and slightly scary-sounding names like InterlockedCompareExchangePointerAcquire. While I could tell you not to worry and that it’s not that complicated, I also don’t want to give a false sense that it’s not that complicated or hard.

So, let me get this out right now:

Tip #5: Lockless programming is complicated. It is hard. It is not for the faint of heart. It will suck your soul, give you heartburn, a migraine, and an ulcer. And that’s only if you’re doing the easy stuff.

That said, let’s delve right in! Understanding what the Interlocked functions do takes a bit of practice, but the one thing you have to keep in mind is that we are performing multiple operations in one atomic instruction. Let’s take a look at some examples, which I hope will illustrate the concept:

Note: All of these examples are PSUEDOCODE! If you try to use them as real code, then shame on you. We’ll start with the basics:

// PSEUDOCODE!  Do not use!  I repeat, DO NOT USE!
DWORD InterlockedIncrement(volatile DWORD* pValue)
{
    return ++(*pValue);
}

DWORD InterlockedDecrement(volatile DWORD* pValue)
{
    return --(*pValue);
}

Well, that’s anticlimactic, right? What’s so special about these operations? Let’s take a look at the non-interlocked version of the same code in a sort of pseudoassembly:

; ++(*pValue)
mov reg1, *pValue  ; Read *pValue into a register
inc reg1           ; Increment the value
mov *pValue, reg1  ; Write the value back into memory

Hmmm… That’s three operations. As per Tip #2, our code can be interrupted at any time, which means that somebody could come in and change the value of pValue after I’ve already read it, and then the value that I’m writing back to memory is wrong.

The InterlockedIncrement() and InterlockedDecrement() functions perform the same three (actually four, with the return) operations, but in one single atomic instruction, which is guaranteed by the operating system to be atomic. (Note that, while many or most of the Interlocked operations will be implemented at the CPU level as a single instruction, there is nothing requiring that to be the case. That’s why this guarantee is made by the OS, not by the CPU.)

Let’s take a look at a more interesting example:

// PSEUDOCODE!  Do not use!  I repeat, DO NOT USE!
DWORD InterlockedCompareExchange(volatile DWORD* pValue, DWORD dwExchange, DWORD dwComparand)
{
    if(*pValue == dwComparand)
    {
        *pValue = dwExchange;
        return dwComparand;
    }
    return *pValue;
}

Wow! All that in one CPU instruction. It’s probably not entirely obvious why that particular function is useful. The brief version of the answer is that it lets you try to assign a new value, but only if no other thread has come in and messed with your data in the meantime. You often see code like this:

DWORD dwOriginalValue = dwValue;
DWORD dwNewValue = SomeCalculation(dwValue);
if(InterlockedCompareExchange(&dwValue, dwNewValue, dwOriginalValue) != dwOriginalValue)
{
    // Some other thread has come in and messed with the value at the same time!
    // Deal with the situation.  What that means is very specific to your situation, but
    // there are a number of useful patterns.
}

I will not go into a lot of detail here on patterns and practices with lockless programming for the simple reason that somebody far more qualified than I has recently done a full 15-part blog series on lockless programming. Instead of attempting to do justice to Raymond Chen’s expertise, I will simply link to his posts:

Lock-free algorithms: Choosing a unique value (warm-up)
Lock-free algorithms: The singleton constructor
Lock-free algorithms: Choosing a unique value (solutions)
Lock-free algorithms: The one-time initialization
Lock-free algorithms: The singleton constructor (answer to exercises)
Patterns for using the InitOnce functions
Lock-free algorithms: The try/commit/(try again) pattern
Lock-free algorithms: Update if you can I’m feeling down
Lock-free algorithms: The opportunistic cache
Lock-free algorithms: The try/commit/(hand off) model
Don’t forget to include the message queue in your lock hierarchy
Visual Studio 2005 gives you acquire and release semantics for free on volatile memory access
Corrections to Patterns for using the InitOnce functions
The performance improvements of a lock-free algorithm is often not in the locking
Even if you have a lock, you can borrow some lock-free techniques

I heartily encourage you to read these posts (and the rest of Raymond’s blog). They are pure gold. Which brings me up to the next and final tip:

Tip #6: Just because lockless programming is hard, doesn’t mean you shouldn’t do it.

It just means that you should educate yourself, and that you should be diligent and very very careful when you do.

I hope that this series has been helpful and educational. Be sure to check out Tangle Trap if you have an iOS device, and keep an eye on this space for more technical articles, announcements, and updates from me and the rest of the BitFlip Games staff!