Spin-lock with Compare-and-Swap

1. What is a Spin-lock?

Before we build one, let's define what it is. A spin-lock is a type of lock used for mutual exclusion. When a thread tries to acquire a spin-lock that is already held by another thread, it doesn't go to sleep. Instead, it "spins" in a tight loop, repeatedly checking the lock's status until it becomes available.

To get a quick overview, let's hear it explained in the first minute of this video.

The key trade-off is this:

• Spin-locks are efficient for very short critical sections. The cost of spinning for a few hundred cycles is much lower than the overhead of a context switch (telling the OS to pause your thread and run another one), which can take thousands of cycles.
• Mutexes (std::mutex) are better for long critical sections. Spinning for a long time wastes CPU cycles, whereas putting a thread to sleep allows the CPU to do other useful work.

For a high-frequency telemetry system, where events are captured and processed in nanoseconds, spin-locks can be a valuable tool.

2. The Atomic Workhorse: Compare-and-Swap (CAS)

To implement any lock-free or low-level synchronization primitive, you need an atomic operation that can read, modify, and write a value as a single, indivisible step. The most versatile of these is Compare-and-Swap (CAS). In C++, this is provided by std::atomic::compare_exchange_strong.

Here’s the concept:
bool compare_exchange_strong(T& expected, T desired);

This function does the following atomically:

1. It reads the current value of the atomic variable.
2. It compares this current value with the expected value you provide.
3. If they are identical, it writes the desired value into the atomic variable and returns true.
4. If they are different, it loads the atomic's current value into your expected variable and returns false.

The most crucial part is that your expected variable is passed by non-const reference. If the CAS fails because the atomic variable held a different value, expected is updated for you. This is incredibly convenient, as it tells you what the value was, so you can use it in your next attempt.

As the video explains, this CAS operation allows you to build a retry loop: attempt a change, and if another thread got there first, the CAS fails, and you simply try again with the new value.

3. Implementing a Spin-lock

Let's build our spin-lock. We'll start with a simple but slightly inefficient version and then improve it. A spin-lock needs two things: a piece of state and two methods, lock() and unlock().

Our state will be a single atomic boolean flag:
std::atomic<bool> flag = {false}; // false means unlocked, true means locked.

The unlock() Method

This is the easy part. To unlock, we just need to set the flag to false. Based on our previous lessons, what memory order should we use? We are "releasing" the lock and making the data protected by it visible to other threads. This calls for std::memory_order_release.

void unlock() {
    flag.store(false, std::memory_order_release);
}

The lock() Method: A First Attempt (Test-and-Set)

For the lock() method, we need to atomically change the flag from false (unlocked) to true (locked). A simple way to do this is with atomic::exchange, which unconditionally swaps the value and returns the old one. This is often called a Test-and-Set (TAS) lock.

The code from the article, adapted for clarity, looks like this:

// A simple, but inefficient, Test-and-Set (TAS) spinlock
void lock() {
    // exchange() returns the *previous* value.
    // We keep trying until the previous value was `false`, which means we successfully
    // swapped `false` for `true`.
    while (flag.exchange(true, std::memory_order_acquire)) {
        // Spin...
    }
}

The problem? exchange() is a read-modify-write (RMW) operation. Every thread that is spinning is constantly trying to write to the cache line containing flag. This creates a storm of cache coherency traffic, as the cache line is continuously invalidated and passed between CPU cores. This severely degrades performance under contention.

A Better lock() Method: Test-and-Test-and-Set (TTAS)

We can do much better. The key insight is to separate the "testing" from the "setting".

1. Test: Spin using a cheap, read-only load() operation. Multiple threads can read a cache line simultaneously without causing traffic.
2. Set: Only when the load() shows the lock is free (false), do we attempt the expensive RMW operation to acquire it.

This pattern is called Test-and-Test-and-Set (TTAS). Now we'll use compare_exchange_strong for the "Set" part, as it's more expressive for this conditional update.

4. The Final Implementation

Let's put everything together into a complete Spinlock class using the efficient TTAS pattern with compare_exchange_strong.

#include <atomic>

// On GCC/Clang, use __builtin_ia32_pause(). On MSVC, use _mm_pause().
// This intrinsic is a hint to the CPU that we are in a spin-wait loop.
// It can reduce power consumption and improve performance on hyper-threaded CPUs.
#if defined(_MSC_VER)
#include <intrin.h>
#define CPU_PAUSE() _mm_pause()
#else
#define CPU_PAUSE() __builtin_ia32_pause()
#endif

class Spinlock {
public:
    Spinlock() : flag_(false) {}

    void lock() noexcept {
        for (;;) {
            // Optimistically try to acquire the lock.
            // This is the "Test-and-Set" part of TTAS.
            bool expected = false;
            if (flag_.compare_exchange_strong(expected, true, std::memory_order_acquire, std::memory_order_relaxed)) {
                // Succeeded, we have the lock.
                return;
            }
            
            // The lock is held by someone else. Spin while waiting for it to be released.
            // This is the "Test" part of TTAS. We use a relaxed load because we're
            // just polling and don't need synchronization guarantees here.
            while (flag_.load(std::memory_order_relaxed)) {
                // Hint to the CPU that we are spinning.
                CPU_PAUSE();
            }
        }
    }

    void unlock() noexcept {
        // Release the lock. Use `release` to ensure that all writes
        // inside the critical section are visible to the next thread
        // that acquires the lock.
        flag_.store(false, std::memory_order_release);
    }

private:
    std::atomic<bool> flag_;
};

Let's break down the lock() method:

1. We start an infinite loop for (;;) because we will keep trying until we get the lock.
2. We first optimistically try to acquire the lock with compare_exchange_strong. If the lock is free, this will likely succeed on the first try, and we can return immediately. This is the low-contention fast path.
3. We use memory_order_acquire for the success case. This synchronizes with the release in unlock() and ensures we see all the memory writes from the previous lock holder. The failure case can be relaxed as no synchronization is happening.
4. If the CAS fails, it means the lock is held. We now enter the spin loop: while (flag_.load(std::memory_order_relaxed)). Here we spin on a cheap, read-only load with relaxed ordering.
5. Inside the spin loop, we call CPU_PAUSE(). This is a crucial optimization that prevents the spinning thread from consuming all available execution resources, which is especially important on hyper-threaded cores.
6. Once the while loop exits (because another thread called unlock()), we loop back to the top of the for (;;) and try the compare_exchange_strong again.

Spinlock spin;
int shared_data = 0;

// Thread 1
spin.lock();
shared_data = 42;
spin.unlock(); // What if this was relaxed?

// Thread 2
spin.lock();
assert(shared_data == 42); // Could this assert fail?

Conclusion

Congratulations! You have successfully designed and implemented a correct, high-performance spin-lock from first principles. This is a significant step in your journey into systems programming.

Key Takeaways:

• A spin-lock is a synchronization primitive where waiting threads "spin" in a loop, ideal for short-lived locks to avoid OS context-switching overhead.
• Compare-and-Swap (compare_exchange_strong) is a fundamental atomic read-modify-write operation used to conditionally update a value, forming the basis of many low-level concurrent algorithms.
• The Test-and-Test-and-Set (TTAS) pattern is a crucial optimization for spin-locks. It avoids excessive cache-coherency traffic by spinning on cheap read-only load operations and only attempting the expensive write (CAS) when the lock appears free.
• Correct memory ordering (acquire on lock, release on unlock) is essential for ensuring that the data protected by the lock is correctly synchronized between threads.

What's Next?

You've now seen relaxed and acquire-release used in a real-world primitive. In our next lesson, we'll formalize this knowledge. We will analyze the different scenarios you'll encounter in concurrent programming and establish clear guidelines for when to use different memory orderings to balance safety and performance. This will equip you with a robust decision-making framework for all your future concurrent code.