Everything in the last two concepts was two threads fighting. This is the only place in the course where the hardware imposes a cost that has nothing to do with another thread. The machine is the same machine, the cores are the same two cores, and the number of threads that could conceivably contend for the line is zero — and the locked instruction still costs more than twice what the unlocked one does.
That result is worth a concept on its own for two reasons. First, it is the single most useful thing a programmer can know about atomics: the cost of an uncontended atomic is not a rounding error, and it is not zero, and it is charged to a thread that had no reason to pay it. A code generator that turns every increment into a locked read-modify-write has made a decision with a price, and the price is roughly one and a half extra ticks per operation before a single line is contended.
Second, it forced this course to retract an explanation it had already written. Here is the retraction, verbatim from the artifact, and it is the sharpest of the six because the number was right and the reason was wrong — which is much harder to notice than either being wrong:
R4. "An uncontended lock is expensive because of coherence."
RETRACTED TO THE WRONG REASON. It is expensive, and the
measurement in section 3 separates the two, but the cost is NOT
coherence -- there is no other thread and nothing to be coherent
with. It is the barrier the prefix implies, paid by a thread
that had no reason to pay it. See R5.
Read that carefully. Retracted to the wrong reason is a distinct category from retracted, and it is the category a measurement is most likely to hide. A wrong number announces itself eventually — the run disagrees, or the ratio comes out at zero, or the program takes a different path. A wrong reason attached to a right number is perfectly stable, survives re-runs indefinitely, and is believed by everyone who reads it, including the person who wrote it. You cannot detect this class of error by measuring more carefully. You can only detect it by asking what else could have produced the number.
Same two cores, same bodies, same iteration count. One thing differs between the two tables: whether the two threads write the same line.
Two design decisions in that shape are worth naming, because either one quietly turns the experiment into a different one.
Both configurations use the same measure() machinery but two different worker functions, and they are kept as separate functions rather than as a flag on one function. “The two threads are on different cores” and “the two threads are on the same line” are two different experiments, and the output has to be able to say which is which — which is exactly the confusion R6 is about. A single worker with a boolean would have produced a table where the two axes are interleaved in the reader's head.
Both arms still pin and both arms still verify. The threads in configuration 1 are two separate threads with nothing between them, because the alternative — measuring one thread — would not produce the same kind of number and would introduce a comparison across two different estimators. The pin is checked after the join in both, because a thread that migrated into the same core as its partner would turn “nothing is shared” into “the line is contended by a core that also shares the L1 with it”, which is configuration 2 wearing configuration 1's label.
And the CAS loop is in the table for a reason that is easy to miss: a compare-and-swap is the general form and a fetch-and-add is the special case that cannot fail. Comparing them in both configurations is not a formality. It is the only way to see which part of the instruction's cost is the arithmetic and which part is the retry structure, and the answer is that you cannot separate them until the line stops being shared.
$ ./smpbench | sed -n '/two threads, TWO SEPARATE/,/uncontended cost/p'
two threads, TWO SEPARATE lines -- nothing shared at all:
plain store 1.04 ticks/op <- the floor
lock xadd 2.64 ticks/op 2.54x the plain store
lock cmpxchg loop 2.99 ticks/op 2.88x the plain store
the SAME bodies, both threads on ONE line:
plain store 1.08 ticks/op 1.04x the floor
lock xadd 22.03 ticks/op 21.20x the floor
lock cmpxchg loop 22.31 ticks/op 21.47x the floor
THE MOST IMPORTANT NUMBER IN THIS SECTION, and it is a subtraction:
lock xadd, one line 22.03
lock xadd, own line 2.64
the cost of CONTENTION 19.39 ticks = 7.33x the uncontended cost
Look at the first table, which is the one people do not expect. A lock prefix with nothing to be locked against costs 2.54× a plain store, on a machine with no other thread running.
It is not a coherence cost. There is no coherence traffic and nothing to be coherent with — both threads own separate lines in separate caches and neither cares about the other. It is the instruction's own guarantee. On x86 the guarantee is a full memory barrier: loads before it cannot move after it, stores before it cannot be delayed past it, and both are ordered against every other core. You pay for that whether or not anyone is there.
That is R4 in one sentence, and it is also the reason the same instruction costs something different on a different architecture. On AArch64 the acquire and the release are separate instructions and the barrier is a mode the access itself has, so a relaxed atomic increment is nearly free and a lock-prefixed one does not exist. The expensive thing here is not atomicity. It is the ordering that x86 attaches to atomicity whether or not you asked for it.
Now the subtraction, which is the most important number in the section and is not a ratio of anything:
Reporting 22.03 on its own would tell you almost nothing — it is a number on a machine whose core clock you do not know. Reporting the ratio to the floor would tell you the wrong thing, because it folds in a cost that has nothing to do with contention. The subtraction is the only report that isolates the effect, and it is the number a reader should carry away.
And it is stable in a way the floor is not. Across the three recorded runs the contended lock xadd came out at 22.03, 22.27 and 22.24 ticks/op; the plain-store floor moved between 1.04 and 1.39. The ratio to the floor therefore moved too — 21.20×, 16.07× and 21.35× — while the contended cost itself did not move at all. The stable number is the contended one and the noisy number is the floor, which is the opposite of what people expect and is the whole argument for reporting the difference. It also means the uncontended ratio is the least trustworthy figure in this section: it reads 2.54×, 1.91× and 2.54× across the three runs, and what moved was the denominator.
A contended atomic is not twice an uncontended one because the
hardware is twice as busy. It is expensive because ONE core OWNS
the line and the other must take it, and the ownership has to move
back and forth, and each move is a round trip neither side can
overlap with its own work. This is why a contended counter is a
queue and not a fast counter, and why the fix is never a better CPU.
That last sentence is the engineering conclusion and it is worth stating as a rule: a contended atomic increment is a queue with a very small service time and no queueing discipline, and the only ways to make it faster are to give each thread its own counter or to batch the updates. Sharding the counter is not an optimisation, it is the algorithm. No amount of clock rate changes the ownership round trip.
The CAS loop against the xadd, in both configurations, is four numbers and one finding:
$ ./smpbench | sed -n '/the CAS loop, against/,/Read those two ratios/p'
the CAS loop, against the xadd, on the same two configurations:
separate lines 2.99 against 2.64 1.13x
one shared line 22.31 against 22.03 1.01x
Read the two ratios against each other rather than separately, because the difference between them is the finding. On separate lines the retry structure is visible and it costs something: 1.13×. On a shared line the two instructions become indistinguishable: 1.01×, which is the same as saying the retry structure is free once the line is moving anyway. The transfer dominates everything the instruction does around it.
That is the general shape of a contended measurement, and the artifact states it as such:
That is the general shape of a contended measurement: the LOWER
bound on what you are timing is not the thing you meant to time, and
the only honest report is the two numbers side by side. A draft of
this section said the CAS loop 'costs more on a shared line because
the retry rate is the contention'. It does not. It costs the SAME,
and the sentence was a story about a number that contradicted it.
Note what kind of error that was. The draft sentence is not a wrong number and not a wrong mechanism exactly — the retry rate is a form of contention. It is a mechanism that sounds right, is true in general, and predicts a difference in the one place where the measurement found none. Had the CAS loop come out 10% more expensive on the shared line, the sentence would have looked vindicated and the check would have passed.
The defence is the awkward one: a story that explains a number you already have is the least reliable kind of explanation, because it costs nothing to generate and it is never falsified by the number that inspired it. It is falsified only by the next measurement, which is why the artifact prints the two configurations side by side and lets them argue, and why the harness asserts the sentence that says the sentence was wrong.
long on its own 64-byte line, sum them at the end. (Expect the result to land near the uncontended 2.64 rather than near 22.03, and expect the summed total to be exactly right. This is the fix the previous concept recommends, expressed as a change of code rather than as padding on a struct, and it is the single most useful thing to carry out of this concept: a contended atomic is a queue; the fix is to stop queueing.)ldar/stlr pair. (Expect the relaxed arm to be close to a plain store and the acquire/release arm to be different from it — on a weakly-ordered machine the ordering is something you write down, so it has to cost something, and it does not cost 1.5 ticks for free. If your machine happens to be x86-64 only, read R5 and the three-architectures concept instead, and treat it as the same argument without the experiment.)Backwards, the sharing concept measured row G — the same body without the lock — and found the two indistinguishable, because seven interleaved arms on a busy guest add more noise than the lock costs. This concept is the other half of that sentence: with nothing else in the run, the lock costs 2.54×. Together they produce the rule “the cost of a lock is a property of the noise floor of whichever table you measured it in,” and the discipline that follows from it, which is to measure a small effect in a table that contains only that effect.
Forward, the ordering concept is where the other promise of the prefix gets its own section, and where this course states the largest limit in its own vocabulary: a duration is not a guarantee, and no timing measurement on any machine can establish that an ordering is correct. The 2.54× in this concept is a cost paid for ordering; the next concept says the price can be measured and the guarantee cannot, and explains why those are different kinds of question.
Outward, two connections worth making explicitly. The execution course's instrument concept is why the subtraction is trusted more than the ratio in this section — it is the same argument that a TSC tick is time rather than cycles, applied to a ratio whose denominator moves. And the privilege course's harness is where the “report the subtraction, not the ratio” rule is generalised: rule 1 there says structural claims are asserted exactly and timing claims only as orderings, and the contention check here is an instance of it — the harness asserts that contention costs far more than the prefix itself, not what contention costs.
One outward-facing consequence, because this is the concept a compiler author will use. On x86-64 fetch_add in C11 memory_order_relaxed and memory_order_seq_cst compile to the same instruction, because the prefix already implies a full barrier and the compiler has nothing to add. On AArch64 they compile to two different instruction pairs. That is R5: a lock-free algorithm written on x86-64 is correct partly by accident, and this concept is where the accident becomes visible as a line item in a timing table.