Why memory accesses reorder

3.4 Out of order: why other cores see your writes rearranged

Within one thread, memory behaves as written: accesses preserve the behaviour of the abstract program, including changes other threads may make to shared atomic locations. That promise covers only what the thread itself can observe. Another thread, watching the same memory from another core, can see the same stores arrive in a different order, and can see a load that seems to have happened before a store that came ahead of it in the program. Two separate machines rearrange memory accesses, the compiler and the CPU, and both do it for speed.

The compiler

A compiler may transform a program in any way that a single thread could not detect. This is the as-if rule, and within it ordinary optimisations reorder memory freely. The compiler keeps a value in a register instead of loading it again, so a loop that waits on a plain variable another thread sets may never see it change. It moves a load out of a loop because nothing in the loop writes that address. It merges two stores to one address into one. And it reorders stores to different addresses, so data = x; ready = true can come out with ready written first if that schedules better. None of this is visible to the thread that runs the code, and all of it is visible to another thread.

Atomic accesses limit transformations through the memory model, rather than through a blanket ban on removing or combining instructions. But an atomic access on its own does not stop the compiler moving other accesses around it. That takes an ordering, which is what the memory model supplies.

The CPU

The core reorders for two reasons, and both have already appeared. The first is the store buffer. A store waits in the buffer while later loads, to other addresses, go straight to the cache. From another core’s point of view the load happened first: it read memory at a moment when the store was not yet visible. This is store-to-load reordering, and every core with a store buffer does it.

The second is out-of-order execution. Loads run when their addresses are ready, not in program order, so a later load can read its line before an earlier load reads its own. Whether another core can tell depends on the architecture’s rules. x86 hides it. Its cores execute loads out of order but check their work. If a line that a load read early is invalidated by another core before that load retires, the core throws away the load and everything after it and runs them again; this replay is called a memory-ordering machine clear. As a result, loads appear to happen in program order. And stores leave the buffer in program order. So x86 shows other cores exactly one kind of reordering: a store followed by a load of a different address. The model has a name, total store order (TSO), and a precise formal statement, x86-TSO.

AArch64 promises much less. Stores may leave the buffer out of order, and loads may be satisfied out of order. What stays in order is accesses to the same address, and a load whose address was computed from an earlier load’s value. All four pairs of loads and stores to different addresses can be rearranged.

One thing both share. x86 and current AArch64 normal coherent memory are multi-copy atomic: a store does not propagate independently through a succession of observer cores. This does not mean all loads happen at the same instant, or that different variables acquire Rust’s SeqCst total order. Older ARM models and POWER permit additional propagation behaviours.

Worked example: a quote and a ready flag

A strategy thread publishes a quote to a gateway thread through three atomics: a price px, a quantity qty, and a flag ready that holds the quote’s sequence number. The strategy stores px, then qty, then ready. The gateway spins until ready reaches the number it is waiting for, then loads px and qty and sends the order. Every access is Relaxed: atomic, and nothing more.

Three things can hand the gateway the previous quote’s price. The compiler may emit the store to ready before the store to px. On AArch64, the store to ready, whose line the strategy’s core already owns, may leave the buffer while the store to px still waits for its line. And on AArch64 the gateway’s load of px may be served from a stale copy before its load of ready completes. On x86-64 neither hardware effect exists, because stores leave in order and loads appear in order. If the compiler kept the source order, the code works on every x86 box it is ever tested on.

The second case is the one x86 does not hide. Two strategy threads share one position limit and must not both send the last order against it. Each announces itself, then checks the other:

Each store is still in its own core’s buffer when the other core’s load reads the cache, so both loads return 0 and both orders go out. This pattern is called store buffering, and it is the heart of Dekker’s mutual-exclusion algorithm, which it breaks. It reorders on every x86 machine.

What it costs

Reordering is not a defect. It is how the machine earns its speed. The store buffer is what makes a store cost one cycle instead of 100 ns, and out-of-order loads are what let independent misses overlap. Forbidding it has a price in time, and so does leaving it unforbidden, in a different currency: a wrong value, delivered rarely. How rarely depends on the chip, the compiler version, the load on the machine and the timing of two threads to within a few nanoseconds. At 100,000 publishes a second, an event that strikes one publish in ten million happens every 100 seconds, and a test that runs for one second will almost never see it.

Seeing it

A litmus test is the smallest program that can show a reordering: two or three threads and two or three variables, run millions of times while counting the outcomes program order would forbid. With source-order atomic instructions on x86, the hardware message-passing test normally shows no reordering, while the store-buffering test, the two flags, shows both loads returning 0 in a small fraction of rounds; on an AArch64 box both tests can show it. litmus7, from the herdtools suite, runs such tests on real hardware, and Lab 3.1 writes both in Rust. On Intel cores, perf stat -e machine_clears.memory_ordering counts the replays that keep x86’s loads looking ordered, and on a line that two cores are fighting over the count climbs quickly. Each one is a full pipeline flush, tens of cycles and several times the cost of a branch mispredict: the price x86’s own hardware pays for the order it promises.