Rule 5 of this course's artifact, learned the way all six of its rules were learned — by breaking it:
Three things, and the reason they have to be separated is not pedantry. Each one has a different fix, and the fixes are not even the same kind of thing:
Calling all three “contention” gets you a plausible answer to a question you did not ask, and then you optimise the wrong thing. In this table the cheapest sharing row costs about a twelfth of the dearest, and one of the three — the SMT row — turns out to cost nothing measurable at all. That is a factor-of-twelve spread, and the artifact's rule calls it sixty because the memory course's own figure for the same family of effects was 61.9×. Either way the spread is the argument: three effects an order of magnitude apart do not belong under one word.
There is a fourth trap here that is not about the word at all, and it is the one that ruined the first version of this table. It is in the sentence “exactly one thing changed per row”, and it deserves its own paragraph because almost every microbenchmark in the world violates it.
One program, four placements, seven rows, and the property that makes the table an experiment rather than three benchmarks:
Rows A, B and C use the IDENTICAL instruction on the IDENTICAL
machine. Only the memory address changes. That is what makes them
a controlled experiment rather than three benchmarks -- and the
first version of this table did not have that property: row A used a
plain store and row B used a locked one, so B/A measured the cost of
the instruction AND the cost of sharing, and the two could not be
told apart. The number looked fine. It meant nothing.
Read that again slowly, because it is the whole lesson: the number looked fine. A plain store against a locked read-modify-write on a shared long is a difference of thirteen times, and any reader would have written “sharing costs 13×” and moved on. In fact that ratio was two ratios multiplied together — the price of the lock prefix and the price of the sharing — and there was no way to separate them, because the version that would have separated them had already been deleted.
The fix was to make rows A, B and C the same body with different addresses:
And here is the alignment trap, which cost this course two of its own rows. The declaration that gives each worker a private line was, in the first version:
/* WRONG -- and silent */
static long g_line[MAXCPUS] __attribute__((aligned(64)));
/* RIGHT */
static long g_line[MAXCPUS][16] __attribute__((aligned(64)));
An attribute on a one-dimensional array is a statement about the array; a statement about the elements needs a two-dimensional one. The first version aligns the start of g_line to 64 bytes and then leaves every element eight bytes from its neighbour. Every “one private line each” row was a false-sharing row wearing a different label — and worse than that, it cost more than the genuinely shared row did, because two threads bouncing a line beats one line being hammered by both. The sixteen-long second dimension gives a 128-byte stride and guarantees that consecutive workers are on different lines.
Three details of the model are worth separating from the numbers, because they are the difference between an experiment and a demo:
$ ./smpbench | sed -n '/pinning to cpu2/,/and the one that matters/p'
pinning to cpu2 and cpu4 (different cores), and to cpu2 and cpu3 (siblings)
A one private line each, 2 cores 3.66 ticks/op
B ONE shared line, 2 cores 47.76 ticks/op
C 8 bytes apart, one line, 2 cores 39.98 ticks/op
D one private line each, 2 SMT sibs 3.93 ticks/op
E one private line each, 1 core 6.73 ticks/op
F each opaque-loads the peer's line 2.33 ticks/op
G one private line each, 2 cores 3.00 ticks/op
B / A one shared line, true sharing 13.05x
C / A 8 bytes apart, false sharing 10.92x
D / A SMT siblings 1.07x
E / A both threads on one core 1.84x
F / A peer's line, no lock at all 0.64x
G / A plain store, nothing shared 0.82x
and the one that matters: B / C = 1.19x
B is 13.05× the floor. C is 10.92×. B/C is 1.19.
True sharing means both threads are updating the same long, so the value genuinely is shared and the algorithm genuinely depends on it. False sharing means they are updating two longs eight bytes apart, and not one value is read by anybody but its owner — the program is a textbook data-race-free parallel program, and it still costs 10.92×.
Expected: B much larger. B contains all of C's cost plus a serialising dependency on the same word. Measured: they are the same to within a fifth. Therefore the cost of true sharing is not in the data. It is in the cache line, and every byte of B is a byte that padding could have bought back.
And the number does move. Across the three recorded runs B/C came out 0.97, 1.03 and 1.19. The shape held every time; the value did not. That is why the harness asserts a shape with a band and not a ratio — and it is the subject of the last concept.
The first draft said SMT costs a modest penalty here, because the shared L1 serialises. Measured, D is 1.07× A. Two SMT siblings running a body that shares nothing cost the same as two cores running it, so the shared L1 is not what SMT charges you for.
What SMT does charge you for is the shared issue ports, and a latency-bound body like this one does not saturate them. So the conclusion the artifact is willing to print is much narrower than the one it started with:
SMT is not free, and THIS EXPERIMENT DOES NOT SHOW
WHAT IT COSTS.
Row E is the one that does show a cost, and it is the only row here where the two workers were asked to be on the same core rather than merely landing there: 1.84×. E is what D becomes on a machine with SMT switched off. Two threads that find each other on one core pay for it; two threads that are placed there deliberately pay more — because the scheduler no longer has anywhere to move them.
F is a ping-pong. Each worker stores to its own line and then opaque-loads the line the other one owns: two lines, two owners, a transfer every iteration. Written naively it should be the slowest row in the table. Measured it is 0.64× A — below the no-sharing floor — and the reason is the store buffer.
A store does not invalidate the other core's copy WHEN IT
EXECUTES. It goes into the store buffer and the other core's
copy stays valid until the store RETIRES. Two threads in a
tight loop with no synchronisation therefore do not take turns:
each runs ahead, each load often finds the peer's line still
valid and shared, and the transfers that do happen are spread
out rather than serialised.
This is why a data race is hard to find, and it is worth more
than the number it produced: THE FAST PATH AND THE SLOW PATH
LOOK THE SAME ON AVERAGE. A program with a race usually runs
at full speed and gives the wrong answer once in a million
times, which is exactly the profile of a heisenbug.
Two things follow, and the second is worth more than the row.
The first is a limit on the evidence: the artifact cannot count the transfers, because there is no PMU on this machine. What it can say is that F is not dramatically above A, and that a measurement which does not reproduce the expected shape is reporting something. F is below A partly because it has no lock and A does, and it is partly noise — which is exactly why the honest claim is a bound and not a number.
The second is the sentence that makes this row worth a page of your time: the fast path and the slow path look the same on average. A racy program runs at full speed and gives the wrong answer once in a million times. That is not a bug you will find by looking for slowness, and it is the reason the tools that find races are checkers and sanitizers rather than profilers.
G is row A with the lock removed. In this table they are indistinguishable — 0.82× — and the next concept shows the same two bodies costing 2.54× when nothing else is in the run. That is not a contradiction, and the artifact's explanation is the most useful thing in this table:
Seven interleaved arms on a busy guest add more between-run noise than the lock costs — the estimator's own measured spread on this run was 82.5%. So the lock's cost is not in the noise of this table, and the two sections are separate for exactly that reason.
The engineering consequence of a B/C of 1.19, 1.03 or 0.97 is a single declaration. A per-thread counter in a shared struct gets its own line:
That last one deserves the emphasis it gets in the artifact, because it is the same bug as the one in the execution course, in a different costume: a benchmark function that was not 64-byte aligned measured a different quantity than it claimed to. There the code did not start where the compiler said it would; here the data does not land where the attribute says it will. Both are cases of a declaration that promises alignment and delivers it at the wrong granularity, and both are silent.
And notice what the corrected version costs. It has made the struct sixteen times bigger and has reduced the number of counters that fit in a cache line from eight to one. Padding is not free and it is not always right — it is the right answer when threads write these fields concurrently and the wrong answer when they do not, which is why the fix belongs in a struct named for the job rather than in the general-purpose one.
One more worked case, because the seven rows are not the only experiment here. The manifest's completion criterion is to take the 128-byte stride out of the private-line rows and watch the placement group of the harness fail by name. Doing that means row A stops being the floor and becomes row C: A, D and E stop being within a small factor of each other, and B/A and C/A stop both being far above it. The check is written on the shape, which is why the shape catches the edit — a harness asserting “A is 3.66 ticks/op” would just have gone quietly red.
cd courses/smp/assets/samples && ./build_samples.sh then ./smpbench. Expect B and C to be within a small factor of each other and both to be more than three times A. If B/C comes out large — say five or more — the course is wrong or your machine is not the machine: check that the stride is 128 bytes, that the two cores are different core_ids, and that the pinned CPUs reported themselves correctly. If B/C comes out at or below 1, you have reproduced the run where C was marginally dearer than B, which is the same finding.)g_line[MAXCPUS][16] to g_line[MAXCPUS][1]. Rebuild. (Expect row A, D, E and G to stop being a cluster and to sit near row C, and the harness's placement group to fail on the shape checks. Then put the stride back. The point of the exercise is not the speed — it is that the “floor” row is the one you control, and an experiment whose floor you can move is an experiment whose conclusions are about your alignment.)/sys and nowhere else, and to be a cliff rather than a slope. A gradient means your two addresses are not what the source says they are — which is the array-versus-element trap again, one level down.)malloc'd block of per-thread slots. (Expect the compiler to be no help whatsoever. Nothing warns, because nothing is wrong: it is a legal, well-defined program that happens to make every access miss, and the only symptom is a number.)volatile read the compiler could not hoist and a store that is not in a buffer — and read the artifact's two silent bugs in BODY_PING, which are worth more than the row.)Backwards, the topology concept supplied the only thing that makes this table readable: the identity of the pairs. Every row here is a claim about cpu2 and cpu4, or about cpu2 and cpu3, and the pin is verified from inside each worker with sched_getcpu() and a failed repetition is counted rather than dropped. Read that concept first if you intend to trust these rows on a machine that is not this one.
Forward, the atomic concept takes the same two cores and the same two configurations and removes the other thread from the picture, and finds that the locked instruction still costs 2.54× a plain store with nothing to lock against. That is not a contradiction of row G; it is the other half of the sentence about noise floors that ends this one. The ordering concept then separates the two promises the prefix makes — atomicity, which is what this whole concept has been about, and ordering, which is the one thing here that cannot be measured from user mode at all.
Outward, the memory course's sharing concept is where this table's row C was first measured, at 61.9×, and where the term “SMT sibling” was used to throw rows away without being defined. It also has the same finding and a different emphasis: that course proved the effect by its size and inferred the mechanism from the price of an L3 transfer; this course proves the mechanism by measuring the case where there is no shared data at all and the cost does not go away. Together they are the strongest and the weakest forms of the same argument, and it is worth seeing both. The memory course's harness concept then does for its own two numbers what this course's last concept does for these seven, and it is the place to go if you want the general shape of the argument before the specific one.
And the execution course's instrument is the direct ancestor of the noise floor quoted here: 82.5% on the recorded run, which is why this table asserts orderings and shapes and the next concept measures the lock on its own with nothing else in the run.