Memory Ordering and Cache Lines

Thread A writes x = 1. Thread B reads x. Does B ever see 1? And if A wrote y just before x, is B guaranteed to see the new y once it sees the new x? Now a second, very different question: two threads each increment their own counter, with no shared variable and no bug anywhere — so why does the loop run ten times slower when the two counters sit next to each other in one struct?

Both questions are answered by the same hardware — cores, 64-byte cache lines, the coherence protocol that keeps them consistent — and that’s exactly why they get mixed up. “The cache line was invalidated and reloaded” appears in the explanation of both, for unrelated reasons. But they are different questions. The first is about correctness: is the value I read right? It has a yes-or-no answer, and the tool is the C++ memory model — std::atomic, memory_order, release/acquire. The second is about performance: assuming every value is already correct, how many cycles did it cost? It has no yes-or-no answer, only a number, and the tools are cache-line layout and instruction scheduling.

This post keeps the two on separate tracks. Part 1 is the correctness axis: where reordering physically comes from and how release/acquire buys back just enough order. Part 2 crosses to the performance axis with false sharing — the point where the two usually get confused, so the difference is spelled out there. Part 3 stays on performance but changes resource, from cache lines to the pipeline’s dependency chains.

1. Correctness: Is the Value I Read Right?

1.1 The Store Buffer: Why Your Own Writes Lie to Everyone Else

Start with a fact that sounds wrong the first time you hear it: when your thread executes x = 1, that write does not go to the cache. It goes into a small, private, per-core structure called the store buffer — think of it as a notebook the core jots the write into before actually filing it away — and the instruction retires immediately. Your thread moves on to the next instruction without waiting.

Why does the hardware do this? Because actually committing a write to a cache line the core doesn’t already own outright is expensive: the coherence protocol (MESI) has to send a Request For Ownership (RFO) to every other core that might be caching that line, wait for them to invalidate their copies, and only then let the write land. That round-trip is tens of nanoseconds. If the pipeline blocked on every store waiting for that, you’d throw away the entire point of having a pipeline. So the store buffer exists purely to decouple “the instruction is done” from “the write is globally visible.” The instruction retires the moment it’s queued in the notebook; the RFO and the actual cache update happen asynchronously, in the background, whenever the line shows up.

Figure: the store buffer is a queue between the execution units and L1D. A store retires once it enters the tail; the store at the head must have the other copies invalidated and collect every ACK before it enters L1D. What waits for ACKs is that store, not the pipeline; the pipeline stalls only when the queue is full.

This creates exactly one gap, and everything about memory ordering in this post is a consequence of it: for some window of time — typically tens of nanoseconds, an eternity at 4+ GHz — a write has already “happened” from thread A’s point of view, but no other core can see it yet, because it’s still sitting in A’s private notebook.

Note the asymmetry carefully: thread A itself never notices this gap. If A writes x and then reads x again three instructions later, the CPU forwards the value straight out of the store buffer (called store-to-load forwarding, which section 3.4 comes back to) — A always sees its own writes in program order. The gap is only visible from outside — from any other core’s perspective, there is a real, physical delay between “A’s store instruction retired” and “the write is visible anywhere else.” That delay is not a bug and not a compiler artifact; it is a direct, unavoidable consequence of buffering writes to survive at 4 GHz.

Everything from here is about that one gap: how it turns into a specific class of bugs (1.2–1.4), and how C++ gives you a vocabulary to close it exactly where you need to, and nowhere else (1.5).

1.2 The Invalidate Queue: the Inbox on the Receiving Side

The store buffer explains why A’s write is delayed. There’s a mirror-image structure on the receiving side that explains why B might keep reading a stale value even after A’s write has left the notebook and the RFO has arrived.

When core B’s cache holds a line, and core A’s RFO shows up asking to invalidate it, B doesn’t have to process that invalidation instantly either. It can drop the message into an invalidate queue — an inbox — and send the acknowledgment back to A immediately, so A isn’t blocked waiting for B. B then works through its inbox whenever it gets around to it. If B executes a load for that address before it has processed the pending invalidate sitting in its inbox, it can still read the old, stale cached value — even though, as far as the protocol is concerned, that line was already invalidated.

So there are now two independent buffering structures, one on each side of every cross-core write: the store buffer delays publishing, the invalidate queue delays noticing. Put together, they are the physical root cause of every kind of memory reordering you’ll ever debug on a multi-core x86 box.

Figure: A’s store retires into its own store buffer instantly, but the RFO that actually claims the cache line is asynchronous. B’s invalidate queue absorbs that RFO without stalling B’s pipeline, which means a load that races ahead of B’s own inbox can still observe the pre-write value. Both buffers exist for the same reason — don’t stall the pipeline for a cross-core round trip — and together they are the entire physical cause of the four reorderings in 1.3.

Put the two buffers back on the whole chip and one store travels as below. The invalidation crosses the on-chip interconnect and goes only to cores whose caches hold the line, which the snoop filter next to L3 keeps track of; the new value is never pushed over, and the reader fetches it when it needs it. The step that goes wrong in the figure is the reader ACKing before it processes the invalidation, so it sees the new ready and still reads the old data: the later load returns something older than the earlier one, a load-load reordering. x86 forbids it (1.3) and ARM allows it, which is why an acquire on ARM takes a real instruction (1.6).

Open in a new window · Static full figure

1.3 Four Reorderings, and the One x86 Keeps

In the general (formal) shared-memory model, there are exactly four ways a load and a store to different addresses can appear reordered to another observer:

x86 uses a model called TSO (Total Store Order), and the one-line summary of it is “forbid three, allow one.” The forbidden three are guaranteed by hardware for free — a plain mov already has that ordering built in, no fence needed. The one that’s allowed, StoreLoad, is exactly the store-buffer gap from 1.1 given a name: your store sits in the notebook while a subsequent load — to a different address — is free to run immediately, so from another core’s point of view your load can appear to have completed before your earlier store did. This is the textbook cause of the classic “I set the flag, then checked another variable, and the other thread saw them in the wrong order” bug — and on x86 it is the only reordering you have to explicitly guard against; every other combination the hardware already forbids on its own.

1.4 A Bug the Hardware Can’t See: the Compiler Got There First

Before blaming the CPU, check the compiler. This loop:

while (ready == false) {}

looks like it polls memory every iteration. Without volatile or std::atomic, the compiler is free to assume nothing outside this thread can change ready, load it into a register exactly once, and rewrite the whole loop as:

if (!ready) { while (true) {} }   // infinite loop — the load never happens again

This has nothing to do with the CPU’s memory model. It’s a pure compiler-level optimization, legal precisely because ordinary (non-atomic, non-volatile) memory carries no promise that another thread might be watching it. volatile stops the compiler from doing this — it forces a real load every iteration — but that’s all it does. volatile ≠ synchronization. It says nothing about ordering relative to other memory operations, and nothing about the store-buffer/invalidate-queue gap from the last two sections. A volatile bool still lets a reader see a stale value for the full duration of that gap; it only guarantees the compiler won’t hide the memory access from you while you wait. Fixing this loop for real needs std::atomic<bool>, which is next.

1.5 Release/Acquire: Buying Back Just Enough Order

std::atomic with the right memory_order closes the gap from 1.1–1.3 exactly where you name it, and nowhere else — that specificity is the whole design intent. C++ exposes six orderings: relaxed, consume (deprecated in practice — compilers treat it as acquire), acquire, release, acq_rel, and seq_cst. The two that matter most in practice are release and acquire, and the cleanest mental model for them is publish/subscribe:

• A release store says: “everything I wrote before this point is now final — go ahead and publish it.”
• An acquire load says: “give me the latest value, and don’t let anything I do after this point get reordered ahead of it.”

When an acquire load observes a value written by a release store on that same atomic variable, the two form a pair, and C++ guarantees a happens-before edge across threads: everything the writer did before the release is guaranteed visible to everything the reader does after the matching acquire. Nothing else needs to be atomic. A minimal example:

struct SPSCFlag {
  std::atomic<bool> ready{false};
  int payload = 0;   // ordinary int — not atomic, and doesn't need to be
};

// producer thread
void publish(SPSCFlag &f, int value) noexcept {
  f.payload = value;                                // 1. plain write
  f.ready.store(true, std::memory_order_release);    // 2. release: "1 is now final"
}

// consumer thread
auto try_consume(SPSCFlag &f) noexcept -> std::optional<int> {
  if (f.ready.load(std::memory_order_acquire)) {     // 3. acquire: paired with 2
    return f.payload;                                // 4. guaranteed to see step 1's value
  }
  return std::nullopt;
}

payload is an ordinary, non-atomic int. It’s safe only because it’s carried across by the release/acquire pair on ready — this is the standard shape of every SPSC (single-producer single-consumer) ring buffer you’ll find in a trading system: one atomic index for synchronization, everything else plain.

Back to the example from the animation in 1.2, now with a release store to ready and an acquire load of it. The hardware has the same two buffers; the only additions are the two ordering constraints in steps 2 and 6, one for the writer and one for the reader.

Open in a new window

1.6 Why x86 Barely Charges for This, and ARM Does

Go back to the “forbid three, allow one” table in 1.3. Acquire and release only need to forbid reorderings that x86-TSO already forbids on every plain mov — LoadLoad, LoadStore, StoreStore. So on x86, a memory_order_acquire load and a memory_order_release store compile down to an ordinary load and an ordinary store; the hardware was already going to honor that ordering. Acquire/release is nearly free on x86 — that’s not a coincidence, it’s the whole reason the C++ model has separate acquire/release orderings instead of just relaxed-or-nothing.

seq_cst, on the other hand, additionally forbids the one reordering x86 does allow — StoreLoad — and that requires a real fence: MFENCE. That’s the one atomic operation on x86 that’s genuinely expensive relative to a plain load/store, and it’s the reason std::atomic’s default memory order (seq_cst, if you don’t specify one) is more costly than it needs to be for code that only needs publish/subscribe semantics.

On a weak-memory architecture like ARM, none of the “forbid three” comes for free — the hardware is allowed to reorder all four combinations unless told otherwise, so acquire/release need real instructions (LDAR/STLR on ARMv8, explicit DMB barriers on ARMv7). This is why the C++ memory model is specified abstractly instead of just “do what x86 does”: the semantics are portable, but the price tag is architecture-dependent, and code that “happens to work” on x86 because acquire/release are nearly free there can be measurably slower — or, if someone reached for volatile instead of atomic out of habit, outright broken — on ARM.

2. False Sharing: When Correctness Was Never the Question

This is where the two axes from the introduction split apart for good, so it’s worth being explicit: everything below can happen with code that is already 100% correct — every read sees the right value, every memory_order is exactly right, there is no bug in the sense of Part 1 at all. This is a pure performance problem, and no amount of atomics or fences fixes it.

2.1 The Unit of Coherence Is 64 Bytes, Not One Variable

The MESI protocol doesn’t invalidate individual variables — it invalidates cache lines, and a line is a fixed 64 bytes on essentially every current x86 core. If two threads each own a completely unrelated int, and those two ints happen to land in the same 64-byte line — say, adjacent fields in a struct — then every write by thread A to its variable invalidates the entire line, including thread B’s variable, forcing B to reload data it never asked to share. This is false sharing: the sharing is an accident of memory layout, not a real logical relationship between the two variables.

2.2 A Different Mechanism From a Stale Read — and Exactly Why

It’s tempting to file this under “the invalidate-queue thing from 1.2” — same MESI messages, same cache lines, same vocabulary. That’s the confusion this whole post is structured to head off. Line them up directly:

That last row is the sharpest test: take two completely unrelated, unsynchronized int counters, each written only by its own thread, no atomics anywhere, no data race by any reasonable definition of the term — and they will still ping-pong if they share a cache line, because the protocol doesn’t know or care that the two variables are logically unrelated; it only knows two different cores keep asking for exclusive ownership of the same 64 bytes. The stale-read mechanism requires an actual cross-thread dependency on a value. False sharing requires nothing but unlucky struct layout — it is entirely a statement about the physical cost of ownership churn, independent of whether any value was ever read incorrectly.

2.3 The Fix, and What It Doesn’t Fix

struct alignas(64) PaddedCounter {
  std::atomic<uint64_t> value{0};
  // padding is implicit: alignas(64) rounds sizeof() up to the next 64-byte boundary
};

PaddedCounter counters[num_threads];   // each counter now owns a whole cache line

alignas(64) (or the portable std::hardware_destructive_interference_size constant) forces each hot variable onto its own line, so writes from different threads no longer collide. But this only fixes false sharing — variables that shouldn’t have been coupled in the first place. If multiple threads are genuinely, logically incrementing the same atomic counter, padding does nothing: that’s true sharing, the line has to move because the data really is shared, and that cost is inherent to the algorithm, not a layout accident.

For true sharing that’s still too hot, the standard mitigation (the pattern behind LMAX Disruptor-style designs) is to stop touching the shared line on every single operation: keep a locally-cached copy of the last-seen cursor/value, batch several operations against the local copy, and only re-synchronize against the real shared line periodically. You trade a bounded amount of staleness for a large reduction in cross-core traffic — conceptually the same “notebook” idea as the store buffer in 1.1, just applied deliberately at the application level instead of automatically by hardware.

2.4 A Third, Unrelated Problem Hiding in the Same Word: L3 and Intel CAT

One more distinction worth having on hand, because it uses the word “shared cache” and gets folded into “false sharing” conversations by accident: L1 and L2 are private per core; L3 is architecturally shared across the whole socket, and that’s normal and fine. A hot L3 isn’t a false-sharing problem — there’s no coherence protocol churn from sharing L3, because sharing L3 was the design. The actual risk is capacity contention: an unrelated process on another core, with no logical connection to your program at all, can run through enough data to evict your working set out of the shared L3 purely by using up space — a “noisy neighbor,” not a coherence problem. That’s what Intel CAT (Cache Allocation Technology), configured via pqos, is for: it partitions L3 into ways and reserves a guaranteed slice for your process, so a noisy neighbor can fill the rest of L3 as much as it wants without evicting your data. Three different problems, three different fixes: a stale read is an ordering problem (Part 1); ping-pong between two cooperating threads is a layout problem (Part 2); a hot shared L3 getting evicted by an unrelated process is a capacity problem CAT solves — none of the three fixes solve either of the other two.

3. Dependency Chains: You’re Racing the Longest Chain, Not the Instruction Count

Same performance axis as Part 2, different resource: instead of “which cache line does this address belong to,” this section is about “which instruction is the CPU’s pipeline actually waiting on.” The two-line summary: a modern core is superscalar and pipelined — it can have several instructions in flight simultaneously — but it can only start an instruction once every one of its inputs is ready. The number of arithmetic operations in your code barely matters. The length of the longest dependency chain is what determines wall-clock time.

3.1 Two Arrangements, Same Op Count, Different Cost

// chained: every multiply/add depends on the one before it
double chained(double a, double b, double c, double d) {
  return ((a * b) + c) + d;   // one dependency chain: mul -> add -> add
}

// independent: the multiply is the only thing on the critical path
double parallel(double a, double b, double c, double d) {
  double sum = c + d;         // runs concurrently with the multiply below
  return (a * b) + sum;       // only 1 multiply + 1 add are actually chained
}

Same three operations, same result. chained forces the CPU to execute mul → add → add strictly in sequence — total latency is the sum of all three. parallel computes c + d and a * b at the same time (they don’t depend on each other), so the critical path is only one multiply plus one add; the CPU finishes roughly a third faster despite doing “the same work.” This is the whole game of instruction-level parallelism: rearrange independent work so the pipeline can overlap it, instead of leaving accidental dependencies that force it to wait.

The two things a pipeline actually stalls on are data hazards (the next instruction needs a value the previous one hasn’t produced yet — everything in this section) and control hazards (a branch whose direction isn’t known yet, which is what speculative and out-of-order execution are there to hide). Fixing data hazards comes down to three priorities: break unnecessary dependency chains, get data into registers instead of re-reading memory, and balance which execution ports different instruction types compete for.

3.2 A Trap in Priority One: Dependencies That Aren’t Real

Some instructions — popcnt, lzcnt, tzcnt are the well-documented examples, on several Intel and AMD generations — treat their destination register as an implicit input, even though the result they compute never actually depends on the register’s previous contents. The hardware doesn’t know that; it just sees “this instruction reads register X,” and a loop that reuses the same destination register every iteration ends up chained across iterations for no logical reason at all:

; false dependency: rax "depends" on its own stale value from last iteration,
; even though popcnt's result has nothing to do with rax's old contents
loop:
    popcnt rax, rbx
    ...
    jmp loop

; fix: zero the destination immediately before — the CPU's zeroing-idiom
; detector recognizes xor-self as "no real dependency" and breaks the chain
loop_fixed:
    xor eax, eax
    popcnt rax, rbx
    ...
    jmp loop_fixed

This is a narrow, specific erratum — not something you’ll spot by reading source, because the false dependency lives in the microarchitecture, not in your code’s logic. It’s realistically a job for a profiler (perf stat counting stalled cycles against expectation) or a compiler that already knows the erratum list, not for eyeballing — the practical takeaway is knowing the pattern exists, so an unexplained stall on a chain that “shouldn’t” be a chain has somewhere to point.

3.3 Priority One, Overused: Register Spills

Breaking dependency chains by hand — the fix in the very first code sample above, and the technique 3.5 pushes further — means creating more independent values in flight at once. Independent values need their own registers. x86-64 has 16 general-purpose architectural registers. Unroll too aggressively, chase independence too far, and you run out: the compiler starts spilling the extra live values to the stack, which means the “fix” for a dependency stall quietly reintroduces memory traffic — the exact kind of cost priority one was trying to eliminate in the first place. It is a genuinely ironic failure mode: the technique for fixing stalls, used past the point the register file can hold, causes its own kind of stall.

3.4 Store-to-Load Forwarding: Back to the Store Buffer

Store-to-load forwarding — mentioned in passing back in 1.1 — is why a store followed immediately by a load to the same address doesn’t have to round-trip through the cache: the CPU forwards the value straight out of the store buffer. It’s a genuine latency win, but it has a strict physical requirement: the load’s address, width, and alignment have to line up exactly with a single buffered store entry. Forwarding matches one specific record — it does not stitch together partial overlaps. A concrete failure case: write 4 bytes, then immediately read 8 bytes starting at the same address. The read isn’t fully satisfied by any single buffered store, forwarding fails, and the load falls back to the slow path — waiting for the write to actually land in cache before it can be read back. The store buffer that made 1.1’s writes cheap is the same structure that makes this shortcut possible, and the same structure whose width/alignment rules make the shortcut fail silently if you’re not careful about it.

3.5 Turning “Break the Dependency Chain” Into a Formula

The chained vs. parallel example generalizes directly to loops: instead of one running accumulator (a single, fully serial dependency chain — one operation every latency cycles), split the accumulation across K independent accumulators and combine them once at the end.

// naive: one accumulator, one fully serial dependency chain
double dot_serial(const double *a, const double *b, size_t n) {
  double acc = 0.0;
  for (size_t i = 0; i < n; ++i) acc += a[i] * b[i];   // each += waits on the last
  return acc;
}

// K independent accumulators, combined once — not every iteration
template <size_t K>
double dot_unrolled(const double *a, const double *b, size_t n) {
  double acc[K] = {};
  size_t i = 0;
  for (; i + K <= n; i += K)
    for (size_t k = 0; k < K; ++k)
      acc[k] += a[i + k] * b[i + k];        // K chains, no cross-iteration dependency
  for (; i < n; ++i) acc[0] += a[i] * b[i];  // remainder
  double total = 0.0;
  for (double v : acc) total += v;
  return total;
}

How large should K be? Exactly large enough to keep the execution ports fed while a single chain’s latency is still in flight: K = latency × throughput, where throughput is how many of that operation the core can issue per cycle. For a fused multiply-add with 4-cycle latency and two FMA-capable ports (a fairly typical modern desktop/server core):

K = 8 is the sweet spot here — enough independent work to hide the full 4-cycle latency behind both ports’ throughput, with no benefit (and, per the register-spill trap above, real risk) in going further. This is a standard technique (the derivation is the same one Agner Fog’s optimization manuals walk through for any latency/throughput pair), and the honest caveat that goes with it: this ceiling assumes the arithmetic units are the bottleneck. In practice, memory bandwidth or the number of load ports feeding data in can cap throughput first — this is exactly the compute-bound vs. memory-bound distinction at the heart of the roofline model — so the formula tells you the arithmetic ceiling, and perf tells you whether you actually reached it.

In Practice

False sharing from Part 2 and the dependency chains of Part 3 each match one card below (B6, B1): what perf shows, how to fix it, how to verify the fix.

B6 False Sharing

• Signal: a line above 5% Tot Hitm in c2c, with different offsets in it written by different threads; inconspicuous on 1 core, it shows up only with several; mostly HITMs within one socket.
• Cause: the cache line (usually 64 bytes) is the smallest unit of coherence. When thread A writes field X, thread B’s copy of the whole line is invalidated and has to be read again from L3 or memory.
• Fix in three steps:
  • first pad generously to push the fighting fields onto different lines. This step only proves the diagnosis; don’t worry about space yet;
  • re-measure with c2c: it only counts if that line’s HITM drops below 1% and throughput comes up. If it doesn’t drop, the diagnosis was wrong: either it is true sharing, or other fields are involved;
  • then reorder by access pattern: fields each thread writes often get a line each, fields many threads only read can share a line, rarely touched fields fill the gaps.
• The thorough fix: move thread-private fields into a per-thread struct.
• Verify: compare c2c before and after; guard the struct size with _Static_assert.
• Mechanism: #2 Part 2, False Sharing; how the line’s state goes back and forth when two cores each write their own variable is in the MESI special, Part 6; alignas(64), which gives an object whole lines of its own, is in #6 1.3.

B1 Serial Accumulator

• Signal: one vaddss/vfmadd dominates annotate (samples often land on the instruction after it, so look one back); IPC ≪ 1 while cache misses stay low. That combination is the key.
• Cause: every += waits for the previous result, so the speed is set by the latency of a floating-point add (4–5 cycles) rather than its throughput (about 0.5 cycles), a gap of 8–10 times.
• Fix: split into several independent accumulators. Four in plain C is about 4 times faster; SSE2 vector accumulation 4–8 times; AVX2 vectors with 4 accumulators 8–15 times.
• How many accumulators: $\text{latency} \div \text{throughput} = 4 \div 0.5 = 8$. Four is usually enough; tight loops use 8.
• The tail: the leftover elements that don’t fill a group need multiple accumulators too, or small inputs fall back to serial.
• Precondition: the operation must be associative (add, multiply, min, max). The result shifts by a rounding error; if it must match bit for bit, this fix is out.
• Verify: the output agrees within rounding error, and IPC at least doubles.
• Mechanism: #9 Loop Optimization 3.2; the accumulator-count formula is in #2 3.5; whether the compiler splits it for you is in Memory Latency and Bandwidth 1.5.1; measured in the perf special, 4.6.