Instruction Reordering: When Your Code Runs Out of Order
Modern processors and compilers routinely execute your code in a different order than you wrote it. This isn’t a bug—it’s a performance optimization that usually works invisibly. But in multithreaded code, especially lock-free data structures, instruction reordering becomes a correctness concern that requires explicit memory ordering constraints.
Why Instructions Get Reordered
Both compilers and CPUs reorder instructions to improve performance, and they do so independently at different stages.
Compilers reorder operations during optimization. If two statements don’t depend on each other, the compiler may swap them to reduce register pressure, enable better instruction scheduling, or eliminate redundant memory accesses. A write followed by an unrelated read might become a read followed by a write if it helps keep values in registers longer.
CPUs reorder at runtime through out-of-order execution. Even after the compiler has generated machine code, the processor’s scheduler looks ahead in the instruction stream and executes operations as soon as their inputs are ready, regardless of program order. Store buffers allow writes to be delayed while later reads proceed immediately. The memory subsystem itself may complete writes in a different order than they were issued.
The fundamental rule both follow: reordering must preserve single-threaded semantics. If you run your program on one thread, all observable behavior—register values, memory state, I/O operations—must match what the original source code specified. This as-if rule gives optimizers enormous freedom while maintaining correctness for sequential code.
The Multithreading Problem
The as-if guarantee breaks down across threads. Consider this classic example:
// Thread 1
data = 42;
ready = true;
// Thread 2
if (ready) {
use(data);
}
Thread 2 expects that if it sees ready set to true, then data must already be 42. But reordering can break this assumption. The compiler or CPU might reorder Thread 1’s operations, writing ready before data. Thread 2 could then see the ready flag but stale data.
This isn’t theoretical. On weakly-ordered architectures like ARM, stores can be observed by other cores in a different order than they were issued. On x86, which has stronger ordering guarantees, the store buffer can still make a thread’s own writes visible to itself before they’re visible to others, causing subtle bugs.
Memory Ordering Constraints
Languages and ISAs provide memory ordering primitives to control reordering. These fall on a spectrum from strict to relaxed.
Sequential consistency is the strongest guarantee: all operations appear to execute in program order, and all threads see the same global order. This matches programmer intuition but constrains optimization. You rarely need it, and it’s expensive to enforce.
Acquire-release semantics provide a middle ground. An acquire load ensures that no subsequent memory operations can be reordered before it. A release store ensures that no prior memory operations can be reordered after it. Together, they create a happens-before relationship: everything before the release in one thread is visible after the acquire in another thread.
This is enough for most synchronization patterns. The data-ready example becomes:
// Thread 1
data = 42;
ready.store(true, memory_order_release);
// Thread 2
if (ready.load(memory_order_acquire)) {
use(data); // guaranteed to see data = 42
}
Relaxed ordering allows maximum reordering. Loads and stores happen atomically—you won’t see torn values—but there’s no synchronization and no ordering guarantee between operations. Relaxed atomics are useful for statistics counters or progress indicators where exact ordering doesn’t matter.
Hardware Mechanisms
Enforcing memory ordering on modern hardware requires explicit instructions. On x86, most loads and stores already have acquire-release semantics, but full barriers use mfence to drain store buffers and ensure global visibility. On ARM, dmb (data memory barrier) instructions prevent reordering across the barrier point, and acquire/release operations map to special load/store instructions with ordering semantics.
These barriers stall the pipeline or flush buffers, creating visible performance costs. This is why lock-free programming is difficult: you need enough ordering to guarantee correctness but not so much that you lose performance gains.
Compiler Barriers vs Hardware Barriers
It’s important to distinguish what prevents compiler reordering from what prevents hardware reordering. A compiler barrier—like a volatile access in some contexts or an asm volatile statement—only prevents the compiler from moving operations across that point. The CPU remains free to reorder at runtime.
True memory barriers affect both: the compiler won’t reorder around them, and they compile to hardware instructions that enforce ordering. In C++11 and later, std::atomic operations with explicit memory orderings handle both compiler and hardware concerns correctly for your target architecture.
When to Care
Most code never needs to think about instruction reordering. Locks provide necessary synchronization automatically, with acquire semantics on lock and release semantics on unlock. High-level concurrent data structures handle ordering internally.
You need explicit memory ordering when writing lock-free algorithms, implementing synchronization primitives, interfacing with hardware (where device registers have implicit ordering requirements), or porting low-level code across architectures with different memory models. In these cases, understanding reordering isn’t optional—it’s the difference between code that works and code that fails intermittently under load.
The modern memory model exposes just enough control to write correct concurrent code without forcing sequential execution. But it requires thinking carefully about which orderings your algorithm actually needs, not just reaching for the strongest guarantee by default.