compare-and-swap (CAS)
/ kass /
Suppose two people both want to update the same shared number, and you need the update to be all-or-nothing — no half-finished mess where their writes tangle. Compare-and-swap is the single hardware instruction that makes this possible. In one indivisible step it checks whether a memory location still holds the value you expected, and only if so does it write your new value. If someone changed it first, your write is refused and you are told so.
Precisely, CAS(address, expected, new) does three things atomically — as one unbreakable operation no other thread can interrupt: it reads the value at address; it compares that value to expected; if they are equal it stores new at address and reports success; if they differ it leaves memory untouched and reports failure (often returning the value it actually found). The whole point is the atomicity: between the read and the write, no other thread can sneak in. This is the bedrock primitive of nearly every lock-free algorithm — you read the current state, compute the new state you want, and use CAS to install it only if nothing changed underneath you. On x86-64 this is the cmpxchg instruction, usually with a lock prefix; in C11 it is atomic_compare_exchange_strong; in C++ std::atomic::compare_exchange_strong.
Two honest cautions. First, CAS compares the raw bits of a value, not its meaning — and that blind spot is the source of the ABA problem, where a value changes away and back to the original and CAS wrongly thinks nothing happened. Second, there are two flavours: compare_exchange_strong, and compare_exchange_weak which is allowed to fail spuriously (report failure even when the values matched) but compiles to faster code on some CPUs — you use the weak form inside a retry loop where a spurious failure just means one more harmless trip around the loop.
/* Atomically increment x without a lock, using a CAS retry loop. */ uint64_t old, neu; do { old = atomic_load(&x); neu = old + 1; } while (!atomic_compare_exchange_weak(&x, &old, neu)); /* On failure, &old is refreshed with the current value, so we just retry. */
CAS installs neu only if x is still old; otherwise it reports failure and updates old, and the loop tries again.
CAS compares bit patterns, not logical identity — equal bits look identical even if the value cycled away and back, which is the ABA problem. Use compare_exchange_weak inside loops, strong for single one-shot checks.