Compare-and-Swap (CAS)

How CAS works

The semantics fit in a few lines of pseudocode:

function CAS(addr, expected, new):
  atomic {
    if *addr == expected:
      *addr = new
      return true
    else:
      return false
  }

The atomic block is the entire point — between the comparison and the write, no other thread can observe or modify *addr. CAS reports success or failure so callers can react: success means "I did the update"; failure means "someone got there first, retry."

The instruction has been around since IBM System/370 in 1973. Intel introduced CMPXCHG on the 80486 in 1989, with the LOCK prefix for multi-CPU bus locking. ARM took a different route initially with load-linked/store-conditional pairs (LDREX/STREX) but added a true CAS in ARMv8.1 (CASAL) when atomic-heavy workloads became common.

The CAS loop pattern

Almost every use of CAS lives inside a retry loop. The pattern: read a value, compute a new value based on it, CAS to commit. If CAS fails, someone else updated the location — reread and retry.

function atomic_increment(counter):
  loop:
    old = *counter
    new = old + 1
    if CAS(counter, old, new): return new
    // else retry

This is optimistic concurrency control at the hardware level. You assume no contention, do the work, and only pay if your assumption fails. Under low contention, the loop almost never retries. Under high contention, it may retry many times — but progress is guaranteed: at least one thread always succeeds, so the system never deadlocks.

Treiber's lock-free stack

R. Kent Treiber's 1986 IBM technical report introduced one of the first lock-free data structures, a stack built on CAS:

struct Node { value: T; next: *Node }
top: *Node = null

function push(value):
  n = new Node(value, null)
  loop:
    n.next = top
    if CAS(&top, n.next, n): return

function pop():
  loop:
    old = top
    if old == null: return null
    if CAS(&top, old, old.next): return old.value

One CAS per operation. No locks, no waiting. Under low contention, both push and pop run in tens of nanoseconds. Treiber's stack is a teaching reference — almost every textbook on concurrent data structures starts here. It also has a famous flaw: the ABA problem.

The ABA problem

Consider a Treiber stack with top = A, A.next = B. Thread T1 reads old = A and is preempted before its CAS. Meanwhile T2 pops A (now top = B), pops B (top = null), then pushes a fresh A (top = A again). T1 resumes and runs CAS(&top, A, A.next). The CAS sees the value is A — match! It succeeds, setting top to A.next, which is the freed B. The stack is now corrupt.

The general lesson: equal pointer values do not imply unchanged structure. CAS only checks bits.

Mitigations:

• Tagged pointers. Pack a 16- or 32-bit version counter alongside the pointer. Every push/pop increments the counter. CAS the entire word — old A with version 5 won't match new A with version 7.
• Hazard pointers. Each thread publishes which pointers it's about to dereference. Reclamation skips any pointer currently a hazard.
• Epoch-based reclamation. Track global epochs; defer freeing until no thread is in an old epoch.
• RCU (read-copy-update). Linux kernel's pattern: defer reclamation until a quiescent state when no reader holds the old pointer.

What CAS costs in hardware

A bus-locked CMPXCHG forces the cache line into the modified state in the executing core's L1 cache, evicting copies from other cores. On modern x86 with cache-coherent NUMA:

• Uncontended (line already modified locally): ~10-30 cycles — comparable to a regular store with a fence.
• Lightly contended (line is in shared state): ~50-100 cycles — invalidate other cores, take exclusive ownership.
• Heavily contended (8+ cores hammering the same line): hundreds of cycles per CAS, and the CAS loop retries multiple times — effective throughput collapses.
• Cross-socket (different NUMA node owns the line): 200-500 cycles — the line traverses the inter-socket link.

This is why hot atomic counters are a notorious scalability anti-pattern. Sharded counters, per-thread accumulators with periodic flush, and lock combiners all aim to remove the single point of contention.

Why CAS matters

• Lock-free programming. Treiber stack, Michael-Scott queue, Harris linked list, Cliff Click's lock-free hash map — all built from CAS loops.
• Atomic counters. std::atomic<int>::fetch_add, Java's AtomicLong.incrementAndGet, Go's atomic.AddInt64 — under the hood, a CAS loop or a hardware fetch-add (which is essentially CAS internally).
• Kernel concurrency. Linux uses CAS for futexes, RCU pointer swaps, and per-CPU counter flushes. Without CAS, the kernel's scalability would collapse on many-core machines.
• JVM AtomicX classes. The entire java.util.concurrent.atomic package is a thin layer over hardware CAS, exposed for application use.
• Garbage collectors. Concurrent and parallel GCs use CAS to coordinate marking, claim work units, and update pointers without stopping the world.
• Database concurrency. Optimistic concurrency control protocols use CAS-like version-check-then-write, sometimes implemented as a hardware CAS on a row's version counter.

Common misconceptions

• Free of contention. CAS is fast uncontended but expensive contended — under heavy contention a well-tuned mutex with backoff can outperform a naive CAS loop.
• Obsoletes locks. Only for single-word operations. Multi-word atomicity still needs locks, transactional memory, or careful protocol design.
• Lock-free is wait-free. Different progress guarantees. Lock-free: at least one thread makes progress system-wide. Wait-free: every thread makes progress in bounded steps. CAS loops are lock-free but generally not wait-free — a thread can in principle retry indefinitely.
• CAS implies memory ordering. Hardware CAS implementations differ. x86 CMPXCHG is sequentially consistent. ARMv8 CAS comes in relaxed (CAS), acquire (CASA), release (CASL), and full (CASAL) variants — pick the right one or use C++11's memory_order_seq_cst.
• ABA only matters for memory reclamation. ABA can also corrupt counters and version-checked optimistic protocols, anywhere equal-bits doesn't mean unchanged-history.
• CAS is always a single instruction. On older ARM, CAS is emulated via LDXR/STXR pair — two instructions and a possible spurious failure (the store-conditional can fail even without contention).