Three of the five rows in the shape below have been the same on every desktop CPU for thirty years, which is why “cache coherence” feels like one technology rather than three implementations of a specification. The other two rows are where the architectures genuinely differ, and those two rows are exactly what decides whether a lock-free algorithm you wrote on one of them is correct on another.
The two questions are the two promises from the atomic concept and the ordering concept, taken one level up:
On x86-64 the answer to both is one bit in an instruction prefix. That is the whole design decision, and it is a decision with a price that this course measured: because lock implies a full barrier, every atomic operation on x86-64 also pays for ordering whether or not the program needed it — which is why an uncontended fetch_add costs 2.54× a plain store on this machine with nothing to contend against.
AArch64 answers the first question with instructions that carry a mode and the second with instructions that carry a different mode. RISC-V answers the first with an instruction pair that may have to be retried and the second with a fence whose operands say which edges you want. Three genuinely different designs for the same two questions, and the interesting part is not that they differ — it is that two of them let you pay for only one of the answers.
That is the retraction this concept is built around, and the phrase to dwell on is by accident. The x86-64 algorithm is not wrong. It is not even fragile. It is correct for a reason its author did not know they were relying on, and they cannot know they were relying on it because on that machine there is no experiment that distinguishes “I asked for ordering” from “I got it free”.
The privilege course found this shape for traps and it turns out to be the same shape for coherence, which is worth noticing because it is the second time in this collection that five questions have produced five parts:
Rows 1, 2 and 3 are why the word “coherence” feels like one thing. The unit of sharing is a cache line everywhere, because a cache tracks lines and not variables. The state machine is MESI everywhere, because MESI is the minimum state set that lets a core know whether it may read a line without asking. And every cache watches for changes — a snoop — because that is the cheapest way to notice that somebody else just wrote the line you hold. Change none of those three and you have not changed the architecture; you have changed the vendor.
Rows 4 and 5 are where the design decisions live, and they differ in kind rather than in spelling:
x86-64
the ordered atomic a `lock` PREFIX. On x86 it implies a full
barrier, which is why an uncontended atomic still
costs several times a plain store -- section 3.
the order STRONG: loads and stores are not reordered
with other loads and stores, so an ordinary
fence is REDUNDANT here and the same source
needs one elsewhere.
what is hardware the LINE and the atomic instruction. The
PROTOCOL is microcode, not an instruction
anyone can execute.
AArch64
the tagged accesses an INSTRUCTION: LDAR, STLR, LDAXR/STLXR. The
acquire and the release are things you WRITE,
which is a different design from a prefix.
the cost an acquire load costs what a plain load costs
plus the wait; the barrier is not a separate
instruction you sprinkle, it is a MODE the
access itself has. On x86 the same guarantee is
attached to every locked instruction whether you
wanted it or not.
the order WEAK by default. Two cores may observe stores
in different orders. THIS is the real reason
the fence in section 4 is not redundant in
general -- it is redundant HERE, and the source
has to say so with an intrinsic.
RISC-V
the order WEAK, and the fences are FENCE instructions
whose OPERANDS say which edges you want:
FENCE rw,rw orders reads before writes,
FENCE w,r does the other pair.
A single FENCE orders everything.
the atomics LR/SC. The load-reserved does NOT lock the
line and the store-exclusive only succeeds if
nothing else wrote in between, so a CONTENDED
atomic is a RETRY LOOP BY CONSTRUCTION rather
than by accident. The opposite trade from x86's:
no unconditional line acquisition, and unbounded
retries under contention.
the cost an LR/SC pair is two instructions where x86
spends one. The win is that the uncontended
case touches nothing it does not need to.
Three different trades, and each is a coherent position rather than an oversight:
LR/SC does not take the line, so an uncontended pair touches almost nothing; under contention the retries are unbounded and the algorithm has to be written to tolerate them, which is a much larger burden on the programmer and a much smaller one on the uncontended path.Here is the concrete version of the accident, stated as a diff you could actually make:
That is not a hypothetical program shape; it is the message-passing loop from the ordering concept with the fence removed, and it is the shape of most of the code in every lock-free queue, hazard pointer scheme and seqlock anyone has written. On x86-64 the author gets the ordering for free from the atomic store, and on the other two machines they get it from the store's own mode or from a fence — and neither of those is implicit.
Two consequences follow, and the second is the one that bites.
The first is about the source. A program that is correct on x86-64 by accident is a program that is wrong on AArch64, and it is wrong in a way that will reproduce once in a million times — the same profile as the race in the sharing concept, which is not a coincidence. Weak ordering does not make a program wrong immediately, it makes it wrong occasionally, and occasionally is the hardest thing to test for.
The second is about the tests. Port that algorithm to a weakly-ordered machine and it is wrong, and the tests that passed on the first machine will not find it. Not “may not” — will not, and the reason is structural: the tests exercise the machine they were written on, and the machine they were written on cannot exhibit the bug. The only real defences are to write the ordering explicitly so that the weak target gets it, and to run the algorithm on a weak target, which is why emulators, simulators and litmus tests exist, and why “it passed on my laptop” is a statement about one architecture.
the difference a fair queue is one line of assembly on RISC-V
and a data structure on x86.
On RISC-V a contended atomic is a retry loop by construction: LR reserves nothing, SC fails if anyone wrote in between, and you loop. That makes a ticket lock — fetch a number, spin until it is yours, do the work, bump the number — something the hardware already does for you. On x86 the retry loop does not exist at that level, so a fair queue needs backoff, parking, or a lock-free structure with its own proof. The same requirement, on two machines, is one instruction pair on one and a data structure on the other, and that difference is a direct consequence of whether the atomic operation is allowed to fail.
Read the E state back into this, because it is the one place where x86-64 has an extra cost that the others do not. E exists so that a core that knows it is the only reader can answer a read without invalidating anybody. It is an optimisation and its price is a state the other two do not carry, which means a line can be in a state that is neither the sharer's nor the modifier's and both caches have to be able to answer “is that mine” about it. Every one of the three designs pays something the other two do not, and the shape with five rows is where those payments are written down.
Take the one line of code this course measured most carefully and translate it. The bodies were inline assembly, which is exactly the situation where the answer is not portable and where a reader most needs the shape:
Three observations, and each one is a lesson rather than a fact about an ISA:
On x86-64 the one-instruction form is a liability in portable source. You have written an x86 instruction into a program that may be compiled for something else, and no compiler can know you meant “order my stores.” If the code is going to be compiled for more than one target, the atomic has to be a library type with per-target implementations, and the implementation is the whole subject of this concept.
On AArch64 and RISC-V the uncontended case gets cheaper and the contended case gets harder. Neither takes the line unconditionally, so a counter that is mostly uncontended is genuinely cheaper than the x86 form — and a counter that is contended will spin. A fetch_add that never fails is a different primitive from one that may fail, and code written for the first does not port to the second without a retry loop somewhere.
On RISC-V the ordering is a separate thing with a price list.FENCE rw,rw and FENCE w,r are cheaper than a bare FENCE because they order fewer edges. That is the one design on this list where the hardware lets you ask for exactly the guarantee you need, and it is also the one that puts the most responsibility on the person writing the code.
And the portable conclusion, which is the thing to remember from all three: the unit of sharing and the protocol are not yours to choose, and the atomic update and the ordering are. If you are writing a compiler backend, rows 1 to 3 mean your target's line size is a fact you must look up rather than a parameter you invent. If you are writing a library, rows 4 and 5 mean the ordering you request is part of your API and part of your cost model, and both are target-dependent.
std::atomic, for atomic_add, for a compiler intrinsic, and for anything inside a lock you wrote yourself. For each hit, answer: which of the five rows does this depend on, and would it still be correct if row 5 were absent on this target?(Expect the answer “no” for most of them, and expect that most of them are correct anyway — because you are compiling for one architecture and the architecture supplies the guarantee. The exercise is not to fix them; it is to be able to state which guarantee each one is silently borrowing.)atomic<int> store, relaxed and seq_cst, for every target you can build for.(Expect x86-64 to emit the same xchg for both, because the prefix already implies the barrier and the compiler has nothing to add. Expect the weakly-ordered targets to emit visibly different code for the two. That difference is the entire content of R5 in about eight lines of disassembly, and it is the thing you would have to generate correctly in a backend.)Backwards, the NUMA concept established the machine's boundary: one memory domain, so nothing here is a distance measurement. This concept is what makes the boundary irrelevant. Rows 1 to 3 of the shape are identical on all three architectures and are all about a cache line, which is a thing inside one socket. The topology question — how many memory controllers, how many nodes — is a sixth question that none of the three answers, and the machine you would need for it is the machine this course does not have. Forward, the harness concept is where the course's central claim — that B/C is a shape and not a value — is turned into a rule, and it is the concept that has to carry this one honestly: this section's contents are quoted, so the harness asserts that it says so.
Outward, the nearest neighbour in the collection is the privilege course's three-architectures concept, and reading the two together is the point. That one found the same five-part shape for exceptions and privilege — a table, a reason code, a rule for who handles it, a way back, a way to prove the event came from user mode — and found the same asymmetry: the first three parts are the same everywhere and the last two are where the vendors differ. Two unrelated subsystems, one shape, the same asymmetry. That is a stronger result than either course could claim alone, and it is the argument for teaching the shape rather than the vendor's vocabulary.
The other outward link is the one a compiler author needs. The ISA course's decoder gives you the bytes of an instruction and nothing about what they may do to memory; F3 in front of an ADD is one byte and one extra guarantee, and this concept is the layer that says what the guarantee is and what it costs. That byte is the entire difference between 2.64 ticks per operation and 1.04, and a backend that emits it unconditionally has made a performance decision as well as a semantic one.