Compare-and-Swap
Compare-and-swap atomically updates a memory location only if it still holds an expected value, enabling lock-free updates through optimistic retry loops.
Definition
CAS is a hardware primitive that compares a memory word against an expected value and, if equal, swaps in a new value, all atomically. Algorithms build on retry loops: read, compute, attempt CAS, restart on contention. It underlies atomic counters, lock-free stacks and queues, and optimistic concurrency in memory.
Context and scope
Exposed as atomic instructions and language atomics. The building block for lock-free structures, also the mechanism behind database-free optimistic refills like version stamps.
Common misconceptions
- CAS removes contention — it removes locks; contention becomes retries, which cost CPU under heavy write concurrency
- CAS failure means another thread interfered maliciously — it means the value changed; designing for spurious failure keeps code correct
- CAS composes across multiple words — a single CAS covers one word; multi-word invariants need locks, versioned single words, or transactional memory
Anti-patterns
- Wrapping CAS in a loop without a contention backoff and burning CPU in retry storms
- Assuming a successful CAS on a pointer publishes an object whose fields were written non-atomically
- Using CAS on a single word to guard multi-field consistency and shipping torn composite states
Related concepts
Related examples
Authoritative source
What it is
The operation asks: does this memory still hold the value I saw? If yes, replace it with my new value; if not, tell me. Chaining that question into loops converts synchronization into optimistic speculation.
How it works
The instruction takes an address, expected, and new value. Success implies the update happened atomically — with the memory ordering the instruction variant provides. Loop-based algorithms re-read on failure, recompute, and retry; performance degrades gracefully under contention rather than queueing.
When to use it
Counters, flags, simple publication, and the inner loop of lock-free containers. Prefer language atomics over inline assembly: they encode ordering semantics and portability correctly.
Pitfalls
The ABA problem: the value reverted to the expected value while meaning something different — versioned pointers or hazard schemes address it. CAS loops without bounds starve under sustained contention; backoff or fallback to locking smooths the tail. Publishing composite data through a single pointer requires release semantics and immutable targets.