Orderingmemory orderingreorderingcompilerstore bufferload queue

Why Your Loads and Stores Happen Out of Order

Two independent agents reorder your memory operations before any other core sees them: the compiler, which rewrites the code, and the CPU, which executes and retires it out of order. Neither is malfunctioning, and on one core neither is detectable.

Follow the mechanism

Software view, hardware view

The gap between what you wrote and what the machine does is where this whole domain lives.

The question
Who reorders my memory operations, which reorderings are actually permitted, and why can I never see it happening on a single thread?
What you wrote
I wrote `data = 42;` on one line and `ready = true;` on the next. The first happens, then the second. Another thread that sees `ready == true` will obviously see `data == 42`.
What the hardware does
The compiler may emit those two stores in either order, because on a single thread nothing distinguishes them. The CPU may then retire them in program order but let them become *visible* in the opposite order, because each drains from the store buffer independently.
This is the mechanism behind essentially every weak-memory bug. The publish pattern above — fill in a structure, then set a flag — is one of the most common idioms in systems code, and written without synchronisation it is broken on every mainstream architecture, including x86-64.
Source→Compiler→Instructions→Front End→Execution→Registers→Caches→Memory→I/O→Behavior

Four reorderings, and who permits which

ISA-SPECIFICA summary of documented architectural permissions, not of any particular chip. Implementations may be stricter than the architecture allows; never rely on that, because the next stepping need not be.

There are exactly four ways two memory operations can be reordered relative to each other, named for the program order of the pair: Load→Load, Load→Store, Store→Store and Store→Load. A memory model is, at heart, a statement about which of these four a machine is allowed to make visible to other observers.

x86-64 is unusually strict. Its model is essentially Total Store Order: it permits only Store→Load reordering — a later load may appear to execute before an earlier store. The other three are forbidden. This single permitted reordering is exactly the store-buffer effect from Sequential Consistency: The Model You Already Have, and it is why so much sloppy concurrent code appears to work on desktop and server hardware.

AArch64 and POWER permit all four. A store to data and a later store to ready can become visible to another core in the opposite order, with no fence and no atomic involved. This is not an obscure corner: it is ordinary behaviour on the phone in your pocket and on a large fraction of cloud instances. Code that assumed x86 semantics does not degrade gracefully here — it produces a torn or uninitialised read.

Which reorderings each model permits. "Yes" means another core may observe the operations in the opposite order.
ReorderingSequential consistencyx86-64 (TSO-like)AArch64POWER
Load → LoadNoNoYesYes
Load → StoreNoNoYesYes
Store → StoreNoNoYesYes
Store → LoadNoYesYesYes

The compiler got there first

Focusing on the CPU misses half the problem. By the time the processor sees your code it has already been rewritten by an optimiser working under the as-if rule: any transformation is legal provided the observable behaviour of a single-threaded program is unchanged. Two stores to different objects are freely reorderable under that rule. So are a load hoisted out of a loop, a redundant load eliminated entirely, and a store sunk past a branch.

That last one deserves emphasis, because it defeats the most common home-made fix. A spin loop reading a plain bool may be compiled to load the flag once, into a register, and then loop forever on the register — the load has been hoisted out of the loop as an invariant, which is entirely correct for a single-threaded program. No amount of CPU-level fencing helps, because the load is no longer being performed.

This is why the fix has to be expressed in the language, not in assembly intuition. An atomic access, or a lock, tells the compiler that this location is concurrently accessed and constrains what it may do — and separately causes it to emit whatever CPU fences the target requires. One mechanism, both problems. Reaching for inline assembly or a hand-rolled fence addresses the CPU and leaves the compiler free to undo you.

The publish pattern, and what each layer is entitled to do to it
SOURCE                          WHAT THE COMPILER MAY EMIT
------                          --------------------------
data  = 42;                     store ready = true      <-- reordered:
ready = true;                   store data  = 42            two independent
                                                            stores, single-thread
                                                            behaviour unchanged

CONSUMER SOURCE                 WHAT THE COMPILER MAY EMIT
---------------                 --------------------------
while (!ready) { }              load r = ready          <-- hoisted out of
use(data);                      L: if (!r) goto L           the loop; the flag
                                use(data)                   is never re-read

AND THEN, INDEPENDENTLY, THE CPU
--------------------------------
even with both stores emitted in program order, on AArch64 the
store to 'ready' may become visible to another core before the
store to 'data' drains, because nothing orders them

Why a single thread never notices

Both the compiler and the CPU are required to preserve the appearance of program order for the thread performing the operations. If you store to a location and then load it, you will read your own store — the CPU forwards it out of the store buffer without waiting for it to drain. Data dependencies through registers are respected. Single-threaded programs are therefore completely insulated from all of this, which is precisely why the intuition survives long enough to become a bug.

The guarantee evaporates the moment a *second* observer exists. Another core has its own cache and its own view, and nothing in the single-thread guarantee says anything about when your stores become visible to it. The reordering was always happening; you simply had no instrument capable of detecting it.

The practical consequence is a testing problem as much as a coding one. Single-threaded tests cannot detect these bugs even in principle. Multi-threaded tests on x86-64 can only detect the Store→Load class. Only weakly-ordered hardware, a thread sanitiser, or formal reasoning will find the rest — which is why "it passes CI" is such weak evidence for lock-free code.

Broken: plain accesses, no ordering anywhere
1// Producer                  // Consumer
2data  = compute();          while (!ready) { }
3ready = true;               use(data);
4 
5// Compiler may reorder the two stores.
6// Compiler may hoist the 'ready' load out of the loop.
7// CPU may make 'ready' visible before 'data' on AArch64.
8// Broken on every mainstream ISA, including x86-64.
Correct: release on publish, acquire on observe
1// Producer                  // Consumer
2data = compute();           while (!ready.load(acquire)) { }
3ready.store(true, release); use(data);
4 
5// 'release' orders the earlier store to 'data' before
6// the store to 'ready'. 'acquire' orders the load of
7// 'ready' before the later read of 'data'. Together they
8// create the happens-before edge the code always needed.

The fix is not "add a fence" but "declare the synchronisation". A release store paired with an acquire load constrains the compiler *and* causes it to emit the right CPU-level ordering for the target — on x86-64 that is often no extra instruction at all, and on AArch64 it is a specific ordered store and load. One source, correct on both.

Key points

  • There are exactly four reorderings — Load→Load, Load→Store, Store→Store, Store→Load — and a memory model is a statement about which are permitted.
  • x86-64 permits only Store→Load; AArch64 and POWER permit all four, so x86-only testing cannot find most weak-memory bugs.
  • The compiler reorders under the as-if rule before the CPU ever sees the code, and can delete a spin-loop load entirely.
  • Both layers preserve program order as observed by the thread itself, which is why a single thread can never detect any of it.
  • The fix belongs in the language — an atomic or a lock constrains the compiler and emits the right CPU fences together.

Follow the mechanism

The path through the machine, hop by hop — and the conclusions it invites that are wrong.

  1. 1
    Source → compiler: two stores to unrelated objects are reorderable under the as-if rule; the optimiser may emit them in either order or eliminate one.
  2. 2
    Compiler → machine code: a loop-invariant load of a plain flag may be hoisted out of the loop entirely, so the flag is read once into a register.
  3. 3
    Machine code → CPU front end: instructions are fetched and decoded in program order, preserving the illusion at the architectural level.
  4. 4
    CPU → store buffer: each store retires into the buffer and drains toward coherent cache independently, so visibility order need not match retirement order.
  5. 5
    Store buffer → other core: the second core observes whichever store drained first, which on AArch64 may be either one.
What people conclude from this — wrongly
  • • "The CPU reordered my code" — the compiler is at least as likely to be responsible, and only the language-level fix addresses both.
  • • "x86 does not reorder" — it permits Store→Load, which is exactly the reordering behind the store-buffer litmus test and behind most Dekker-style mistakes.
  • • "I added a memory fence in inline assembly, so it is fixed" — the compiler may still hoist, sink or eliminate the surrounding accesses.
  • • "Reordering only matters for lock-free code" — it matters for any shared data touched without synchronisation, which includes plenty of accidentally-shared code.

Consequences, controls and cost

What it causes
  • • The publish pattern — initialise, then set a ready flag — is broken without synchronisation on every mainstream ISA, and is one of the most common idioms in systems code.
  • • A spin loop on a plain flag can hang forever because the load was hoisted, not because the flag was never written.
  • • Bugs surface as "works on our servers, fails on ARM" or "fails only in release builds", because the optimiser and the ISA both changed.
  • • Adding logging or a debugger usually makes the symptom vanish, since both introduce synchronisation and drain buffers.
What you can do
  • • Use language-level atomics or locks for every location touched by more than one thread — this is the only fix that constrains the compiler and the CPU together.
  • • Prefer acquire/release pairs to raw fences: they express *what* is being synchronised, and the compiler picks the cheapest correct encoding per target.
  • • Never use `volatile` for inter-thread synchronisation in C or C++; it constrains optimisation of the access but provides no ordering or atomicity between threads.
  • • Test on weakly-ordered hardware, and run a thread sanitiser in CI — an x86-only test suite is blind to three of the four reorderings.
How to see it
  • • Compile the publish pattern with optimisation on and read the emitted assembly to see whether the stores were reordered or the load hoisted.
  • • Run a message-passing litmus test on AArch64 and count outcomes where `ready` is observed true and `data` is stale.
  • • Compare the disassembly of a release store on x86-64 against AArch64 to see how differently the same source is encoded.
  • • Enable a thread sanitiser and let it report the unsynchronised accesses directly rather than inferring them from symptoms.
What it costs
  • • Ordered atomics cost fences on weakly-ordered targets and inhibit compiler optimisation around them, which can matter in a hot loop.
  • • Relaxed orderings recover that performance but move the correctness burden entirely onto you, with no tooling that reliably checks it.
  • • Testing on multiple architectures costs CI capacity, and is still only evidence rather than proof.

Scope

§224 — what these claims are specific to.

What these claims are specific to
  • ISA-SPECIFICWhich of the four reorderings are permitted is defined per architecture: x86-64 allows Store→Load only; AArch64 and POWER allow all four.
  • PLATFORM-SPECIFICCompiler reordering is governed by the language standard and optimisation level, not the CPU. The same source at -O0 and -O2 can differ in exactly the ways described here.

Misconceptions

Claim
“Memory reordering is a CPU problem.”
Reality
It is two problems that look identical from the outside. The compiler reorders at build time under the as-if rule and can eliminate accesses entirely; the CPU reorders visibility at run time. A fix aimed at only one leaves the other free.
Claim
“`volatile` makes a variable safe to share between threads.”
Reality
In C and C++ it prevents the compiler from optimising away or caching that specific access, and does nothing about atomicity or inter-thread ordering. Java's volatile is a genuine acquire/release, which is a large part of why the confusion persists.
Claim
“If the reordering were real, my program would already have crashed.”
Reality
The window is narrow and the outcome is often benign or self-correcting. These bugs typically manifest as rare corruption under load rather than immediate failure, which is what makes them expensive.

Where the rest of this lives

Concurrency & Parallelism
Happens-before and synchronisation edges

This lesson explains which reorderings hardware and compilers may perform. Which pairs of operations your program has actually ordered, and what that proves about its correctness, is the concurrency domain's subject.

Programming Languages & Runtime Internals
The as-if rule and optimisation latitude

What the optimiser is permitted to do to your code — and why deleting a loop-invariant load is legal — is a language-semantics question rather than a hardware one.

← Sequential Consistency: The Model You Already HaveStore Buffers: Where Your Writes Wait →