The question this answers
How does compare-and-swap turn a multi-step update into something safe without a lock, and what does the retry cost?
Every worker finishing a request offers its latency to a shared maxLatency high-water mark, which must end up holding the largest value any worker ever offered.
One atomic maxLatency word, read and conditionally written by every worker.
maxLatency equals the maximum of every value ever offered — a larger value is never overwritten by a smaller one, and no offered larger value is dropped.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The primitive: write only if nothing moved
Compare-and-swap takes three things: a location, the value you expect it to hold, and the value you want to put there. It writes only if the location still holds the expected value, and it tells you whether it wrote. That single conditional is enough to build almost every lock-free structure, because it lets a thread say "commit my computation only if the world I computed from is still the world that exists".
The consequence is that CAS on its own is never the whole algorithm. A failed CAS means somebody else won, so you must decide what to do about it: recompute from the new value and try again, give up, or fall back to a lock. The loop around the CAS is where the actual logic lives, and reviewing lock-free code means reading the loop, not the CAS.
Two API details matter in C++. compare_exchange_strong fails only when the value genuinely differed; compare_exchange_weak may also fail *spuriously*, which is permitted so the compiler can emit a bare LL/SC pair on architectures that have one. Weak is correct only inside a retry loop — which is exactly where you already are. Both write the value actually found back into your expected variable on failure, so the loop re-reads for free.
1#include <atomic>2std::atomic<uint64_t> maxLatency{0};3 4void offer(uint64_t sample) {5 uint64_t seen = maxLatency.load(std::memory_order_relaxed);6 while (sample > seen) {7 // On failure, compare_exchange_weak writes the CURRENT value into8 // 'seen', so the next loop iteration compares against fresh state.9 if (maxLatency.compare_exchange_weak(seen, sample,10 std::memory_order_release,11 std::memory_order_relaxed)) {12 return; // we won; our sample is the new maximum13 }14 // lost the race: 'seen' now holds whatever the winner wrote.15 // The while condition re-tests whether we still have anything to offer.16 }17 // sample <= seen: somebody already recorded something larger. Done.18}Why read-then-store is not the same thing
The tempting version of this function is two lines: read the max, and if your sample is bigger, store it. Both operations are atomic. The pair is not, and the schedule below is what that costs.
What CAS changes is that the write carries its own precondition. In the same schedule, A's store becomes a CAS that expects 100, finds 180, and fails — so A never destroys B's value. A then re-reads 180, discovers 150 is no longer worth offering, and exits the loop having done nothing, which is correct.
This is the same shape as optimistic concurrency control at the database and API layers: read a version, compute, and commit conditional on the version being unchanged. See Optimistic Concurrency Control and, for the HTTP contract, Optimistic Concurrency: Versions and If-Match. CAS is that pattern compressed into one instruction on one word.
| # | Worker A (sample 150) | Worker B (sample 180) | State |
|---|---|---|---|
| 1 | atomic load maxLatency -> 100 | · | maxLatency=100 A.seen=100 |
| 2 | · | atomic load maxLatency -> 100 | maxLatency=100 A.seen=100 B.seen=100 |
| 3 | · | 180 > 100, atomic store maxLatency = 180 | maxLatency=180 |
| 4 | 150 > 100 (A's stale read), atomic store maxLatency = 150 | · | maxLatency=150 ✕ The maximum offered was 180 and the location now holds 150. A larger value was overwritten by a smaller one from a stale read. |
| 5 | [CAS version instead] compare_exchange(expected=100, desired=150) -> fails, expected now 180 | · | maxLatency=180 A.seen=180 |
The cost the loop hides
The retry loop is unbounded. Under low contention it runs once and CAS is roughly the price of an atomic RMW. Under high contention, threads spend their time recomputing from values that are stale by the time they attempt, and the useful work per CAS attempt falls. Nothing deadlocks — some thread always wins, which is precisely the lock-free progress guarantee in Lock-Free Is a Progress Guarantee — but the thread that keeps losing gets no bound on how long it waits. That is the gap Wait-Free vs Lock-Free: Whose Progress Is Guaranteed is about.
Do not read the curve below as "CAS is slower than a lock" or "lock-free does not scale". It is one modelled shape for one workload — a very short critical region on one hot line — and the honest summary is that both a CAS loop and a mutex degrade under contention for the same underlying reason: one cache line, many cores wanting exclusive ownership of it. Which one degrades less is a measurement, not a rule.
The structural fix is almost never a better CAS. It is to stop having one hot location: shard the counter, accumulate per thread, or batch so that each CAS commits more work. A CAS loop whose body is expensive to recompute is the worst case, because every lost race throws away real computation.
Key points
- CAS writes only if the location still holds the value you read, and reports whether it wrote. That conditional is the whole primitive.
- The retry loop, not the CAS, is the algorithm: on failure you must re-read and recompute, because the value you computed from is gone.
- Atomic load followed by atomic store is two atomic operations. CAS is one operation that carries its own precondition.
compare_exchange_weakmay fail spuriously and is correct only inside a loop;strongfails only on a genuine mismatch.- The loop is unbounded: some thread always progresses, but no individual thread is guaranteed to.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Read the current value of the location into a local
expected. - • Compute the new value from
expected— this is ordinary, unsynchronized local work. - • Attempt the CAS: write
desiredonly if the location still equalsexpected. - • On success you are done, and the return value tells you that you were the thread that committed.
- • On failure the implementation writes the value actually found back into
expected, and you loop: recompute, re-attempt, or decide you no longer need to write at all.
- • A reads 100; B reads 100; B CAS(100 -> 180) succeeds; A CAS(100 -> 150) fails and re-reads 180; A re-tests 150 > 180 and exits. Invariant holds; A did no harm.
- • A reads 100; B reads 100; A CAS(100 -> 150) succeeds; B CAS(100 -> 180) fails and re-reads 150; B re-tests 180 > 150 and CAS(150 -> 180) succeeds. Invariant holds; B retried once.
- • Naive version: A reads 100; B reads 100; B stores 180; A stores 150 — the maximum offered was 180 and the location holds 150. The invariant is broken with no error raised.
- • Three threads, all offering larger values: each round, one commits and two fail. A thread whose recomputation is slow can lose every round while the system as a whole makes progress — starvation without deadlock.
- • A reads value X; B changes it to Y and back to X; A's CAS succeeds because the value matches, even though the world changed. See The ABA Problem: The Value Came Back.
- • Promises: the compare and the write happen indivisibly — no thread can slip a write between them.
- • Promises: a successful CAS means the location held exactly
expectedat the instant of the write. - • Promises: system-wide progress — a failed CAS means some other thread succeeded, so the structure as a whole always advances.
- • Does NOT promise: that
expectedmatching means nothing changed. The value can have left and returned; that is precisely the ABA problem. - • Does NOT promise: a bounded number of retries for any particular thread. Starvation is permitted.
- • Does NOT promise: ordering of other memory, unless you specify it. The success and failure orderings are separate arguments in C++ and both must be justified.
- • Does NOT promise: better throughput than a mutex. It promises a different failure mode, not a smaller number.
- • Every attempt requires exclusive ownership of the line holding the location, so N threads attempting concurrently serialise on that line regardless of how much of the loop body is parallel.
- • Retries amplify contention: a losing thread immediately re-attempts, adding traffic that makes the next thread more likely to lose. Backoff (spin a little, then yield) is the standard damper and its parameters are workload-specific.
- • An expensive loop body is the pathological case — each lost race discards real work. If recomputation is costly, a lock that lets one thread finish is often the better engineering answer. See What Contention Actually Costs.
- • Livelock-shaped throughput collapse — every thread is running, retrying, and committing almost nothing. Progress is technically guaranteed; usefully it has stopped. See Livelock.
- • Starvation — one slow thread loses every round indefinitely while faster threads take turns winning.
- • ABA — the CAS succeeds on a value that returned, and the algorithm draws a false conclusion. See The ABA Problem: The Value Came Back.
- • Lost update through the naive read-then-store version, which is the bug CAS exists to prevent.
- • Spurious-failure mishandling — using
compare_exchange_weakoutside a loop, so a legitimate spurious failure is treated as "somebody else won". - • Recomputation drift — recomputing from the new value using stale *other* inputs captured before the first attempt, so the committed value is internally inconsistent.
- • Single-location updates whose new value depends on the old one in a way fetch-add cannot express: maxima, minima, bitmask edits, state-machine transitions.
- • Claiming ownership exactly once — CAS a status word from PENDING to CLAIMED and let the return value decide which worker runs the job.
- • Building the primitives in A Lock-Free Stack, and What the Teaching Version Omits and lock-free queues, where a lock would defeat the reason for the structure.
- • Low-contention paths where the loop almost always runs once and a lock's bookkeeping is pure overhead.
- • High contention with an expensive loop body — you burn CPU recomputing values that are dead on arrival.
- • Invariants spanning more than one location, where CAS on one of them is theatre. See Atomics Are Not Magic.
- • Any structure where a popped or replaced value can be recycled, unless you have thought about ABA and memory reclamation.
- • Code that will be maintained by people who have not read this lesson: the loop looks like a retry-on-error and reads as optional.
- • Instrument the loop: count attempts and successes and export the ratio. A retry rate climbing with load is the signal, and it is invisible in latency until it is severe.
- • Watch throughput against thread count. A curve that flattens and then declines is the contended-location shape, not a CPU limit — cross-check with CPU utilisation, which will look healthy. See CPU Saturation: When Cores Become the Queue.
- • Profile time attributed to the CAS instruction itself; contention shows up as stall time on that instruction rather than in your loop body. Self Time, Total Time, and Where the CPU Went covers reading that.
- • Compare against a mutex version under your real workload before claiming either is faster. Microbenchmark or End-to-End: Why p99 Did Not Move exists because this specific comparison is the one people get wrong in a microbenchmark.
- • The correctness argument moves from "the lock is held here" to "every value this loop reads is re-read after failure and nothing stale leaks into the committed value" — much harder to verify by reading.
- • Two memory orderings per CAS in C++, each of which needs a justification a reviewer can check.
- • Retry accounting and backoff become tuning parameters with no universal value, so they need to be measured per workload.
- • The failure mode is a throughput cliff rather than an exception, so it needs a metric someone actually looks at.
- • A mutex around read-compute-write. Simpler to read, extends to multi-variable invariants for free, and often faster when the region is short. See Mutexes: What They Protect and What They Do Not.
- • fetch-add or fetch-or, when the update is expressible without a comparison. Always prefer the operation that does not need a loop.
- • A single owning thread fed by a queue — no CAS, no lock, and the invariant is enforced by there being one writer. See The Actor Model.
- • Push the conditional update to a system that already does optimistic concurrency: a database
UPDATE ... WHERE version = ?or an If-Match request. See Conditional Requests: ETags, 304 and 412.
compare_exchange in a loop — retries, and the pointer that lied
do {
old = counter.load(); # 1 read
next = old + 1; # compute off to the side
} while (!counter.compare_exchange(old, next)); # swap only if unchanged| # | T1 — pop() via CAS | T2 — another thread | State |
|---|---|---|---|
| 1 | old ← head (= A) | · | head=A stack=A→B→C |
| 2 | · | pop() → A | head=B stack=B→C |
| 3 | · | pop() → B | head=C stack=C |
| 4 | · | push(A) | head=A stack=A→C |
| 5 | CAS(head, A, B) → SUCCESS | · | head=B stack=B→ freed ✕ head now points at B, which was popped and freed. Node C has vanished from the stack and T1 returned a node it never observed being on top. |
| 6 | return A to the caller | · | head=B stack=corrupt |
Optimistic concurrency lab
Conflict probability grows with the number of writers touching the same item, each conflict costs a full retry, and retries consume the same cores the successful work needs. Real systems add their own effects — backoff, hot keys, transaction size — but the turnover is real and it is why an optimistic scheme that benchmarked beautifully at low load can collapse at high load rather than merely slow down.
What people believe, and what is true
A successful CAS proves nothing changed between my read and my write.
It proves the value matched. The location can have been changed and changed back, and any state reachable through it can be entirely different. That is The ABA Problem: The Value Came Back.
CAS is lock-free, so it cannot block.
No thread blocks, but an individual thread can retry indefinitely. Lock-free guarantees that *some* thread progresses, not that yours does.
The retry loop is just error handling.
It is the algorithm. Everything the loop body reads must be re-read after a failure, or the committed value mixes generations.
Go deeper
Overview
CAS means "write this only if the value is still what I saw". If it is not, you are told, and you decide what to do.
Practical
Write the loop as: load, test whether you still need to write, attempt, and on failure loop back to the test — not back to the load, because the failed CAS already reloaded for you. Always use weak inside a loop.
Advanced
Separate success and failure orderings deliberately. A failed CAS publishes nothing, so relaxed is usually right for failure; success ordering must be strong enough to publish whatever the new value points at, which is the Safe Publication: Handing Over a Finished Object question.
Internals
On x86-64 this is lock cmpxchg, which never fails spuriously. On ARM it is a load-exclusive / store-exclusive pair whose reservation can be lost to a context switch or an unrelated store to the same granule — which is why the standard permits spurious failure at all. The microarchitectural reason belongs to Computer Architecture.