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.
New to lock-free programming? Start here
Adding one to a number is three steps for a processor: read it, add, write it back. Two threads doing that at the same time can both read the same value, both add one to it, and both write the same answer -- so two increments produce one. Nothing was corrupted and no instruction misbehaved. The second write simply landed on a value its writer had never seen.
An operation is atomic when no other thread can observe it half-done. The usual fix is a lock: one thread at a time, everybody else waits. It works, and it means a thread that stops while holding the lock stops everyone.
Compare and swap is the other answer, and it is a single instruction: write this new value, but only if the current value is still the one I read. If somebody changed it, the write does not happen and you are told so, and you go round again with what is there now. Nobody waits for anybody, and nobody can be blocked by a thread that stalls.
Two things at once
A program you write reads top to bottom, one step after the last. Once two of them run at the same time, that stops being true of the pair: their steps interleave, in an order nobody chose and nothing wrote down.
The hard part is that the order is not random so much as unconstrained. Any interleaving the hardware permits is one you have to treat as possible, even if no test you ever run happens to produce it: nothing promises that a scheduler will eventually choose it, and nothing promises it will not, on someone else's machine, months later, on the run you were not watching. So the machines in this topic are not about making the right order happen. They are about which orders are possible, which of those are wrong, and what it costs to rule them out.
The machine for this idea on its own is Race, if you would rather press it than read about it.
Machines here that come first: Race.
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, and the patent says 1973
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, and one primary document narrows that without settling it: IBM’s patent US 3,886,525 has a priority date of 29 June 1973 and its text describes “the new instruction called Compare and Swap”. So the instruction existed by mid-1973 and the manual we can read is a year later than the earliest evidence, not the arrival. Settling which EDITION first carried it 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 fourth edition does leave a fingerprint of the two we cannot read: its copyright line is “1970, 1972, 1973, 1974”, one year per edition, so the missing editions are a 1972 and a 1973 and the patent’s June 1973 priority falls between them. That is a narrower bracket, not an answer. 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.
- IBM, Shared data controlled by a plurality of users, US Patent 3,886,525, priority 29 June 1973. Read here. Its description names “the new instruction called Compare and Swap”, which is the earliest primary evidence this page has for the instruction and is a year before the manual the pill is dated from.
- Logical Art, the studio this belongs to.