THE FOLD / CO-OP / SHARED MEMORY / THE FALSE SHARING
THE FALSE SHARING
a bug with no wrong behaviour
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Two threads. Two different variables. Neither one ever reads the other’s. Put them four bytes apart and the program still spends all its time passing a cache line back and forth, because coherence is not tracked per variable.
LIT verified live. two cores, 1,000 writes each to variables they alone own. At offsets 0 and 4 — one 64-byte line — the line changes owner on 1,999 of the 2,000 writes. Move the second variable to offset 64 and the count is 0: two compulsory upgrades and then silence forever. Sweeping the offset from 0 to 128 in steps of 4 gives a step function that falls off a cliff at exactly 64, the line size — nothing gradual, no locality gradient, one number. The fix costs 60 bytes of padding.
LIT verified live. two cores, 1,000 writes each to variables they alone own. At offsets 0 and 4 — one 64-byte line — the line changes owner on 1,999 of the 2,000 writes. Move the second variable to offset 64 and the count is 0: two compulsory upgrades and then silence forever. Sweeping the offset from 0 to 128 in steps of 4 gives a step function that falls off a cliff at exactly 64, the line size — nothing gradual, no locality gradient, one number. The fix costs 60 bytes of padding.
2 HOW IT WAS WEAVED · AI + HUMAN
False sharing and cache-line padding are standard concurrent-programming knowledge; the MESI ownership model here is the usual simplification.
AVAN (AI) ran the sweep rather than naming the effect, and the shape is the point. If false sharing were about ‘locality’ the curve would decay; it does not decay, it steps, once, at the line size. That is the signature of a quantised resource, and it is why the bug is undetectable by reasoning about the program: 1,999 and 0 are the same source code, the same semantics, the same access pattern, differing only in a layout decision no one wrote down.
AVAN (AI) ran the sweep rather than naming the effect, and the shape is the point. If false sharing were about ‘locality’ the curve would decay; it does not decay, it steps, once, at the line size. That is the signature of a quantised resource, and it is why the bug is undetectable by reasoning about the program: 1,999 and 0 are the same source code, the same semantics, the same access pattern, differing only in a layout decision no one wrote down.
3 ONE DIMENSION
One step function. It falls at 64 and nowhere else.
4 TWO DIMENSIONS · INTERACTIVE
Slide the second variable and watch the line stop moving.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that padding fixes false sharing. The inverse is that this is a bug with no wrong behaviour. Nothing computes an incorrect answer; no invariant breaks; every test passes. The program is correct and 1,000× slower, and the cause is invisible to every tool that reasons about meaning, because meaning is exactly what is unaffected. Read backwards, the cache line is a unit the machine takes seriously and the language does not admit exists — and a bug that lives entirely in the gap between those two views can only be seen by looking at the address arithmetic, never at the logic.
LIT two cores, 1,000 writes each to variables they alone own: at offsets 0 and 4 - one 64-byte line - the line changes owner on 1,999 of the 2,000 writes, and moving the second variable to offset 64 gives 0, two compulsory upgrades and then silence forever; sweeping the offset 0 to 128 in steps of 4 gives a step function falling off a cliff at exactly 64, the line size, with nothing gradual about it, and the fix costs 60 bytes of padding
FIG False sharing and cache-line padding are standard concurrent-programming knowledge; the MESI ownership model here is the usual simplification. AVAN ran the sweep rather than naming the effect, and the shape is the point: if false sharing were about locality the curve would decay, but it steps, once, at the line size. That is the signature of a quantised resource, and it is why the bug is undetectable by reasoning about the program - 1,999 and 0 are the same source code with the same semantics.
FIG False sharing and cache-line padding are standard concurrent-programming knowledge; the MESI ownership model here is the usual simplification. AVAN ran the sweep rather than naming the effect, and the shape is the point: if false sharing were about locality the curve would decay, but it steps, once, at the line size. That is the signature of a quantised resource, and it is why the bug is undetectable by reasoning about the program - 1,999 and 0 are the same source code with the same semantics.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SHARED MEMORY · David Lee Wise (ROOT0), with AVAN