Compare and Swap
Two programs read the same counter, both add one, and the counter goes up by one. Nothing was corrupted and no rule was broken; the second write simply landed on a value its writer had never seen. IBM's answer, added to System/370 as an optional feature and documented by 1974, was an instruction that will not write unless the value is still the one you were shown.
An update disappears, and an instruction that refuses instead
1 Two programs, one counter, and an update that disappears
Two programs, each meaning to add one to the same counter eight times. Each reads the counter, adds one, and writes it back. The turns below interleave the way a real machine's would, except that here the order is fixed so the result is the same every time you load the page.
2 Read it, change it, and swap only if it never moved
Now the write is a compare and swap. The program hands the machine the value it read, and the value it wants. The machine changes the counter only if it still holds what the program was shown, and says which of those two things happened.
3 The swap that fails, and the retry that follows it
The same two programs, the same schedule, with compare and swap instead of a bare write. A refused swap is not a lost increment: the machine hands back what it found, and the program tries again from there.
4 What the retries cost as the contention rises
Nothing is lost, so what is the price? Every refused swap is work the program did and threw away. Widen the number of programs sharing the counter and count the attempts each increment costs.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| without the instruction an update disappears | yes | 16 increments intended, the counter reads 8 |
| and the count of lost updates is exactly the shortfall | yes | 8 write(s) landed on a value the writer had not read, shortfall 8 |
| with compare and swap nothing is lost | yes | 16 intended, the counter reads 16 |
| a swap succeeds exactly when the value had not moved, and fails exactly when it had | yes | 16 succeeded with the value they were shown, 15 failed with a value that had changed under them |
| no increment is lost, and the price is the attempts that failed | yes | 16 increment(s) landed in 31 attempt(s), 15 of them refused |
| one program alone never fails a swap | yes | 1 program: 8 swap(s) for 8 increment(s) |
| and the cost per increment rises with the number of programs | yes | 1: 1.00, 2: 1.94, 4: 3.81, 8: 7.56 swaps per increment |
What is real here, and what is not
Nothing on this page races, and nothing on it is atomic
JavaScript here runs on one thread, so there is no concurrency to protect against and no instruction that needs to be indivisible. What is modelled is a schedule: an explicit list of turns saying which program acts next. The turns are arranged so that both programs read before either writes, which is the interleaving that loses an update. On a real machine that ordering happens sometimes. Here it happens always, which is the only way to show it reliably, and it is why every number is identical on every load.
The date is 1974 because that is the earliest manual we can read that has it
The usual claim, repeated widely, is that compare and swap arrived with System/370 in 1970. IBM's own first edition of the Principles of Operation, June 1970, is a thirty-two page document titled Modifications to System/360, and listing the new instructions is exactly what it is for. It names SET CLOCK, STORE CLOCK, LOAD CONTROL and STORE CONTROL. It does not contain COMPARE AND SWAP. By the fourth edition, September 1974, the instruction appears thirty-five times, as part of an optional conditional-swapping feature that raises an operation exception when it is not installed. So it was added to the architecture rather than born with it.
Editions two and three are the source debt, and we could not read them
The instruction entered somewhere between June 1970 and September 1974. Settling which edition would need GA22-7000-1, -2 or -3, and none of the three is on bitsavers or archive.org, which between them mirror only the first, fourth, sixth, seventh and tenth. The System/370 Reference Summary card lists every machine instruction and would answer it in one line, but the earliest surviving edition of that is November 1976. The December 1975 System Summary does not mention the instruction at all. The bracket is closed at the top by a primary source and open at the bottom for want of paper.
The condition codes are the manual's, not ours
A compare and swap that always succeeded would still make this page's counter come out right, because nothing here is really competing for it. So the two outcomes are taken from the archived fourth edition rather than from the engine: equal operands means the second is replaced by the third, unequal means the first is replaced by the second. That second half is the part worth noticing. A refused swap does not simply fail, it hands the program the value it found, which is what makes the retry loop cheap.
The retry loop finishes work the schedule ran out of turns for
The fixed schedule gives each program a set number of turns. When those are spent and some increments have not landed, the model keeps retrying until they do. Those late attempts are counted as retries and the totals on the page include them. A real program would simply loop; splitting it this way is what lets the interleaved part be deterministic and still finish.
ABA is not modelled, and it is the reason real code needs more than this
The counter here only ever counts up, so a value that looks unchanged really is unchanged. On a real machine a location can go from A to B and back to A between a program's read and its swap, and the swap will succeed on a value that moved twice. Guarding against that needs a counter that changes on every write, and COMPARE DOUBLE AND SWAP in the same feature is what lets a program move the value and its counter as one. The two are not alternatives: the double-width compare is how the counter travels. IBM's own free-pool example in the same manual keeps a list header and a count side by side and swaps the pair. Nothing on this page will show you that failure.
The cost curve is a property of this schedule, not of any real processor
Attempts per increment rise roughly with the number of competing programs here because the schedule makes every program read before any of them writes, which is the worst case rather than the average one. A real machine's contention depends on timing, cache line ownership and how long each program holds the value. The shape is right, the numbers are this model's.
Sources
- IBM System/370 Principles of Operation, fourth edition, September 1974, revised 1 September 1975 (GA22-7000-4). The conditional-swapping feature and the condition codes for COMPARE AND SWAP.
- IBM System/370 Principles of Operation, first edition, June 1970 (GA22-7000-0). Thirty-two pages of modifications to System/360, listing the instructions the new architecture added. Compare and swap is not among them.
- Logical Art, the studio this belongs to.