Compare-and-swap

The problem it solves

Compare-and-swap is one instruction with three arguments: an address, the value you expect to find there, and the value you want to put there. It writes only if the current value still matches what you expected, and it tells you whether it did. All of that happens indivisibly.

That one primitive is enough to build every lock-free structure there is, and it is what modern mutexes are themselves built from. Its importance comes from solving the problem check-then-act describes, at the hardware level: the check and the act are the same operation, so there is no window between them for the world to change in.

The consequence that makes it interesting rather than merely useful is what happens when it fails. A thread that loses the race is not blocked, not queued, not descheduled — it is simply told “no”, and it goes round again. Nothing it does can prevent any other thread from making progress, which is the formal property that distinguishes lock-free algorithms from lock-based ones.

The mechanism

The canonical use is a retry loop:

loop:
  seen = load(counter)
  next = seen + 1
  if CAS(counter, seen, next) succeeds: done
  else: goto loop

Read the value, compute the new one from it, and attempt to install it on the condition that nothing has changed. If another thread got in first, the CAS fails, and the loop starts again from a fresh read — this time with the other thread’s work included.

The correctness argument is worth stating carefully, because it is not “the loop keeps trying until it works”. It is that a successful CAS proves nothing intervened between the read and the write. The value being what you expected is the evidence. This is why the retry is safe rather than hopeful: an update can only be installed on top of a value it actually saw.

The failure mode is not blocking but livelock-adjacent waste: under heavy contention many threads spin, and all but one of them discard their work each round. The system as a whole always progresses — someone always wins — but individual threads can retry many times, which is why CAS loops are excellent at low contention and often worse than a lock at high contention.

What the enumeration shows

The default program is two threads running the loop above. All 142 interleavings end at 2, and no thread ever blocks. Step through one where a CAS fails and watch the won local go false and the program counter jump back to the load — that jump is the loop, and the state panel shows the thread re-reading a value that now includes the other thread’s increment.

Then switch to aba-problem, which is where CAS stops being a magic wand. See the ABA problem for the full treatment; the short version is that CAS compares values, not histories, and a value that left and came back is indistinguishable from one that never moved. Eleven of 120 interleavings corrupt a lock-free stack that way.

The third variant, aba-tagged, is the fix every real implementation ships: pack a counter into the same word as the pointer, so returning to the same pointer never means returning to the same word.

The numbers worth carrying

• An uncontended CAS costs roughly the same as an atomic increment: ~20ns, versus ~1ns for a plain store.
• Under contention, each failed attempt costs a full coherence round trip — around 80ns — and is discarded. With n threads hammering one location, expect on the order of n/2 retries per success.
• Lock-free means the system always progresses; wait-free means every individual thread progresses within a bounded number of steps. A CAS loop is lock-free and not wait-free: one unlucky thread can in principle retry indefinitely while others succeed.
• Crossover in practice: CAS loops beat mutexes below roughly 4–8 contending threads on a short critical section, and lose above it. Measure rather than assume; the crossover moves with the length of the operation.

Where it breaks down

ABA. The value is what you expected and the world still changed. Detailed on its own page, and the reason production lock-free code uses tagged pointers, hazard pointers or epoch-based reclamation rather than bare CAS.

Only one word. CAS operates on a single machine word. Updating two pointers atomically requires double-width CAS (available on x86 as cmpxchg16b, not everywhere), or packing both into one word, or a different algorithm. Multi-word CAS exists in the literature and is not a primitive you get from hardware.

Contention makes it worse, not just slower. Every failed attempt still acquired the cache line exclusively. Under heavy contention CAS loops generate maximal coherence traffic while accomplishing minimal work, which is the pathological case the false sharing page measures from a different angle.

Memory reclamation is the hard part. Writing a lock-free stack is an afternoon. Working out when it is safe to free a node another thread might still be reading is the actual problem, and it is why most people should use a library rather than write one.

What people get wrong

“Lock-free means faster.” It means no thread can be blocked by another’s suspension. Under contention a good mutex frequently wins, because a blocked thread stops generating coherence traffic while a spinning one does not.

“Lock-free means wait-free.” Different guarantees. Lock-free: the system progresses. Wait-free: every thread progresses in bounded steps. Almost everything called lock-free is not wait-free.

“The retry loop might never terminate.” It might, for one specific thread, in theory. It cannot fail to terminate for the system, because a CAS only fails when somebody else succeeded.

“CAS makes my data structure safe.” It makes one word’s update safe. Whether the structure is correct depends on whether every invariant lives in that word, and on whether you can safely reclaim memory.

In production

compareAndSet on Java’s atomics, compare_exchange_weak/_strong in C++, CompareAndSwap in Go’s sync/atomic, compare_exchange in Rust, Interlocked.CompareExchange in .NET. The weak variant in C++ is allowed to fail spuriously — it maps directly onto ARM’s load-exclusive/store-exclusive pair, which loses its reservation on an unrelated event — so it must always be used inside a loop, and inside a loop it is the faster choice.

Where you will meet CAS without writing it: every uncontended mutex acquisition is a CAS on the lock word, ConcurrentHashMap uses it for bin updates, reference counting uses it for the count, and LongAdder uses it per-cell. When people say “the fast path is uncontended”, the fast path is one successful CAS.

The pragmatic guidance: reach for an atomic operation before a CAS loop, and a lock before a hand-written lock-free structure. Use CAS directly when you need read-modify-write on one value with logic that no ready-made atomic provides, and read ABA before you build anything with pointers.

The follow-up questions

“Write an atomic increment using CAS.” — The loop above. The part interviewers watch for is re-reading inside the loop rather than reusing the stale seen.

“What happens when the CAS fails?” — You reload and retry. Nothing blocks, and someone made progress — say that, because it is the definition of lock-free.

“Is lock-free always faster than a mutex?” — No, and be able to say why: spinning generates coherence traffic that a blocked thread does not.

“What is the problem with CAS on a pointer?” — ABA. If that lands, the next question is how you would free the node, which is the genuinely hard part.