Instruction Reordering and Concurrency Bugs

The "As-If" Rule and Its Limits

Both compilers and processors are constantly looking for ways to make your code run faster. One of the most common techniques is to reorder instructions. This is governed by a principle often called the "as-if" rule: the final result of any single-threaded program must be the same as if the instructions were executed exactly in the order you wrote them. For single-threaded code, this optimization is completely invisible and safe.

However, this rule makes no guarantees about what other threads might observe while the code is running. When multiple threads share memory, these performance optimizations can suddenly become visible, leading to baffling concurrency bugs.

Let's break this down into the two main sources of reordering: the compiler and the processor.

1. Compiler Reordering

When you compile your C code with optimizations enabled (e.g., gcc -O2), the compiler takes significant liberties to restructure your program's machine code.

As the article explains, the compiler might reorder instructions if they are independent. This transformation from source code to machine code is a key source of unexpected behavior.

A Classic Concurrency Bug Example

Consider this common pattern for passing data from a "producer" thread to a "consumer" thread:

// Shared global variables
int value = 0;
int is_ready = 0;

// Producer Thread
void producer() {
    value = 42;     // 1. Prepare data
    is_ready = 1;   // 2. Signal that data is ready
}

// Consumer Thread
void consumer() {
    if (is_ready) { // 3. Check if data is ready
        // 4. Use the data
        printf("The value is %d\n", value); 
    }
}

Logically, this seems correct. The consumer only reads value after is_ready is set. However, since the writes to value and is_ready are independent from the compiler's single-threaded perspective, it is free to reorder them in the producer function:

// Potentially reordered machine code for the producer
is_ready = 1;
value = 42;

If the producer thread is interrupted after setting is_ready but before setting value, the consumer thread could wake up, see is_ready == 1, and print "The value is 0". This is a classic data race caused by compiler reordering.

The following video, though focused on C++, gives an excellent overview of the kinds of optimizations compilers perform and demonstrates this exact bug. The principles are identical in C.

A Quick Word on volatile

You might think the volatile keyword could solve this. It's a common misconception. volatile tells the compiler not to optimize away reads or writes to a variable and prevents the compiler from reordering volatile accesses relative to each other. However, it does not prevent processor reordering. Therefore, volatile is not a synchronization tool for multithreaded programming on modern systems.

The CppCon video makes this point very clearly.

2. Processor Reordering

Even if the compiler generates machine code in the exact order you intended, the CPU itself can execute those instructions out of order. This is a hardware optimization to hide memory latency and keep the processor's execution units busy.

A key mechanism behind this is the store buffer. When a CPU core writes a value, it doesn't go straight to main memory. It's often placed in a small, fast, private buffer on that core. The core can then continue executing other instructions while the write drains from the store buffer to the globally visible L1/L2/L3 caches and main memory.

This has a profound implication: a write on one core may not be immediately visible to other cores.

The Litmus Test for Processor Reordering

The consequences of processor reordering can be demonstrated with a simple "litmus test." Imagine two threads running on two different cores, with two shared variables x and y, both initially 0.

• Thread 1: x = 1; r1 = y;
• Thread 2: y = 1; r2 = x;

What are the possible final values for the local registers r1 and r2?

• If Thread 1 runs completely before Thread 2: x becomes 1, r1 becomes 0. Then y becomes 1, r2 becomes 1. Result: (r1=0, r2=1).
• If Thread 2 runs completely before Thread 1: y becomes 1, r2 becomes 0. Then x becomes 1, r1 becomes 1. Result: (r1=1, r2=0).
• If the operations are interleaved: x=1, then y=1, then r1=y, then r2=x. Result: (r1=1, r2=1).

Is it possible to get the result r1 = 0 and r2 = 0? Sequentially, it seems impossible. If r1 is 0, then Thread 1 must have read y before Thread 2 wrote to it. If r2 is 0, then Thread 2 must have read x before Thread 1 wrote to it. This implies a contradictory ordering.

However, due to processor reordering, the result (r1=0, r2=0) is entirely possible on modern CPUs!

Here's how:

1. Core 1 (Thread 1): Executes x = 1. The value 1 is put into Core 1's private store buffer. It is not yet visible to Core 2.
2. Core 2 (Thread 2): Executes y = 1. The value 1 is put into Core 2's private store buffer. It is not yet visible to Core 1.
3. Core 1 (Thread 1): Executes r1 = y. It reads y from main memory, which is still 0. So, r1 becomes 0.
4. Core 2 (Thread 2): Executes r2 = x. It reads x from main memory, which is still 0. So, r2 becomes 0.

This reordering of a store followed by a load to a different address (StoreLoad reordering) is permitted on many architectures, including the ubiquitous x86/x64, for performance reasons.

The video you just started explains and demonstrates this exact test.

value = 100;
is_ready = 1;

while (!is_ready) {
    // spin
}
printf("%d\n", value);

Conclusion

You've now seen the two powerful but hidden forces that can break concurrent code. While they are essential optimizations that make modern computers fast, they violate our intuitive, sequential understanding of how a program runs.

Key Takeaways:

• Two Sources: Instruction reordering happens at both compile time (by the compiler) and run time (by the processor).
• The "As-If" Rule: These reorderings are permitted as long as they don't change the observable behavior of a single-threaded program. This guarantee does not extend to multithreaded programs.
• Compiler Reordering: The compiler can re-sequence independent instructions to optimize the final machine code.
• Processor Reordering: The CPU uses features like out-of-order execution and store buffers to hide memory latency, which can result in memory operations becoming visible to other cores in an order different from the program order.
• volatile is not the answer: It only constrains the compiler, not the CPU, making it insufficient for thread synchronization.

Preview of the Next Lesson:
So, how do we write correct lock-free code in the face of these reorderings? We need a way to issue explicit commands to both the compiler and the CPU, telling them, "Do not reorder memory operations across this point." These commands are called memory barriers or fences, and in our next lesson, we will learn how to use them to enforce the memory ordering our algorithms require.