Atomic Operations
CPUs provide indivisible read-modify-write instructions — fetch-and-add, compare-and-swap, load-linked/store-conditional — that make a lock-free counter possible and every lock implementable; the subtleties are the ABA problem and the memory-ordering flags that say what else becomes visible when an atomic does.
The problem
counter++ costs more than the increment. What if the CPU could do the load, the add and the store as one indivisible step — and how do you build anything more complicated than a counter out of that?Read-modify-write, done by the hardware
The race in Race Conditions exists because load, modify and store are separate memory operations another core can slip between. An atomic read-modify-write instruction closes the gap: the CPU acquires the cache line holding the word in exclusive state, performs the whole operation, and only then lets any other core touch the line. On x86 that is the lock prefix (lock add, lock xadd, lock cmpxchg); since the Pentium Pro it locks the cache line, not the whole memory bus, so uncontended atomics cost about 5–20 ns instead of stalling the machine. ARMv8.1 added equivalent single instructions (LDADD, CAS) under the LSE extension.
Three primitives cover nearly everything. Fetch-and-add returns the old value and adds: the lock-free counter, ticket locks, ring-buffer slot claiming. Compare-and-swap (CAS) — "if the word still equals expected, write desired; tell me whether you did" — is the universal one: any single-word update can be expressed as "read, compute, CAS, retry on failure". Load-linked / store-conditional (LL/SC) is the RISC formulation used by older ARM, POWER and RISC-V: ldxr marks the address, stxr succeeds only if nothing wrote it in between; a CAS is an LL/SC loop, and LL/SC additionally sidesteps the ABA problem below because it detects *any* intervening write, not just a changed value.
What makes these worth the trouble is what they avoid: no syscall, no sleeping, no possibility of the holder being preempted while everyone waits. A thread that is descheduled mid-CAS-loop delays nobody; the others simply succeed. That property — some thread always makes progress — is what lock-free means, and it is why the futex fast path (Mutexes) and every scheduler run queue are built on atomics.
1std::atomic<uint64_t> hits{0};2hits.fetch_add(1, std::memory_order_relaxed); // lock xadd; no lock, no syscall3 4// any single-word update: read, compute, CAS, retry5uint64_t old = maxSeen.load();6while (v > old && !maxSeen.compare_exchange_weak(old, v)) {7 // CAS failed: 'old' now holds the current value; loop re-evaluates the condition8}The ABA problem
CAS checks that a word has the *value* you expect, not that nothing happened. Take a lock-free stack whose top pointer is updated by CAS. Thread 1 reads top = A and reads A.next = B, intending CAS(top, A, B). It is preempted. Thread 2 pops A, pops B, frees B, pushes A again — top is A once more. Thread 1 resumes; its CAS sees A, succeeds, and sets top = B, a freed node. The value matched; the world had changed. This is ABA, and it is the reason "just use CAS" is not a design.
Remedies: pack a version counter next to the pointer so every modification changes the word even when the pointer returns to an old value (a 64-bit pointer plus a 64-bit tag needs a double-width CAS — cmpxchg16b on x86-64 — or steals bits from an aligned pointer); use LL/SC, which fails on any intervening store; or ensure a node cannot be reused while any thread might still reference it, with hazard pointers, epoch-based reclamation, or a garbage collector — which is why lock-free structures are easier in Java and Go than in C++. Most engineers should use a proven library (moodycamel::ConcurrentQueue, crossbeam, java.util.concurrent) rather than write one.
1top -> A -> B -> C2T1: reads top=A, next=B; preempted before CAS(top, A, B)3T2: pop A; pop B; free(B); push A # top -> A -> C, and B is freed4T1: CAS(top, A, B) succeeds: value is A # top -> B (dangling)Memory ordering in one careful paragraph
An atomic guarantees that *its own* word is updated indivisibly. It says nothing, by default, about the *other* memory the thread wrote before it — and compilers and CPUs reorder ordinary loads and stores around it unless told otherwise (A Taxonomy of Concurrency Bugs). Memory-order flags are that instruction. Relaxed promises only atomicity: right for a statistics counter nobody reads in relation to other data. Release on a store promises that every write the thread made *before* it is visible to any thread that performs an acquire load and observes that store; acquire promises that no read or write after it moves before it. A release-store paired with an acquire-load that sees it is the "synchronizes-with" edge that makes "write the data, then set the flag; see the flag, then read the data" correct. Sequentially consistent (the C++ default) adds a single global order over all such operations, which is the model most people assume and costs a full fence on stores on x86 (xchg or mfence) and ldar/stlr plus barriers on ARM. Unlocking a mutex is a release, locking it is an acquire — which is why data protected by a lock does not need any of this spelled out — and why a "quick unlocked read" of that data has no ordering guarantee at all.
x86’s strong model (TSO: only store→load reordering is possible) means acquire and release cost nothing extra there; that is precisely why ordering bugs written on x86 laptops surface for the first time on ARM servers and Apple Silicon, whose models are weaker and reorder more. Sanitizers help less here than for data races; reasoning about the pairing does the work.
1// producer // consumer2data = compute(); while (!ready.load(std::memory_order_acquire)) {}3ready.store(true, std::memory_order_release); use(data); // guaranteed to see compute()'s result4 5stats.fetch_add(1, std::memory_order_relaxed); // no one reads stats in relation to other dataAcross languages
C++ has std::atomic<T> with per-operation ordering and std::atomic_ref for existing objects; Rust mirrors it exactly; Go’s sync/atomic is sequentially consistent by design; Java’s AtomicInteger, VarHandle and volatile map onto the same concepts under the Java Memory Model. JavaScript exposes the same instructions on SharedArrayBuffer through the Atomics object: Atomics.add(i32, idx, 1) is fetch-and-add, Atomics.compareExchange(i32, idx, expected, desired) is CAS, and all Atomics operations are sequentially consistent; Atomics.wait/notify are the futex on top (Mutexes).
CPython rarely needs explicit atomics for a different reason than "the GIL makes everything safe". The GIL serialises *bytecodes*, so a single bytecode that does the whole read-modify-write is atomic — list.append, dict[k] = v, itertools.count().__next__ — while multi-bytecode statements like n += 1 are not (Race Conditions). The idiom is to use structures whose operations are single C-level calls (queue.Queue, collections.deque, itertools.count) or a lock. Free-threaded CPython (3.13+) keeps per-object locks inside those C-level operations so the same idioms stay safe. There is no user-level Atomics module because Python objects are not raw words; when you need shared-memory numerics between processes, multiprocessing.Value gives you a lock-wrapped C value.
The cache-coherence bill
Atomics are cheap only when uncontended. Every atomic RMW needs the cache line in exclusive (Modified) state in the executing core’s cache; under the MESI protocol that means invalidating every other core’s copy. Two cores incrementing the same counter bounce the line between them on every operation, ~50–100 ns per transfer across a socket, so a "lock-free" shared counter hit by 16 cores is *slower* than 16 per-core counters summed on read — which is how the kernel’s per-CPU counters, Java’s LongAdder and every serious metrics library work. False sharing is the same tax paid by accident: two unrelated atomics in one 64-byte line thrash as if they were one. alignas(64) and padding are the fix.
The honest summary: atomics remove the *kernel* from the fast path and remove the *preemption* hazard, but they do not remove the *hardware* cost of contention. Locks and atomics contend on the same cache lines; the way to scale is to contend less, not to contend faster.
- Uncontended atomic: ~5–20 ns. Contended across cores: the cache line ping-pongs at ~50–100 ns per hop.
- Shard hot counters per core or per thread; combine on read.
- Pad independent atomics to separate cache lines.
Key points
- Fetch-and-add, compare-and-swap and load-linked/store-conditional are hardware read-modify-writes: the cache line is held exclusively for the whole operation, no lock, no syscall.
- Any single-word update is "read, compute, CAS, retry". Lock-free means a preempted thread never blocks the others.
- ABA: CAS checks a value, not history. Fix with version tags (double-width CAS), LL/SC, or safe memory reclamation — or use a proven library.
- Relaxed = atomicity only; release/acquire pairs publish everything written before the store to whoever sees it; seq_cst adds a global order. Mutex unlock/lock is release/acquire.
- x86 hides ordering bugs; ARM exposes them. Test on the weaker model.
- Contended atomics ping-pong cache lines at ~50–100 ns a hop; shard hot counters and pad against false sharing.
Why does this exist?
Mechanisms are answers to constraints. Open each question before reading the answer.
▸Why does the CPU offer atomics at all instead of leaving it to the OS?
Because a lock is itself built from one: without an indivisible test-and-set or CAS there is no way for two cores to agree on who owns a lock word. Atomics are the floor everything else stands on.
▸Why is a lock-free counter sometimes slower than a lock?
Contention is paid in cache-line transfers either way. A lock-free counter hammered by many cores bounces the line on every increment; a lock at least batches the work of one holder. The win of lock-free is progress under preemption, not raw speed under contention.
▸Why have relaxed ordering if it is so easy to get wrong?
Because a fenced atomic costs a full barrier on every operation and a statistics counter nobody correlates with other memory needs none of that. Relaxed is the honest, cheap option for the cases where only the count matters.
Compare-and-swap
do {
old = atomic_load(p);
} while (!compare_exchange(p, &old, old + 1));How it fails
What the failure looks like from inside real software.
- A lock-free stack corrupts memory once a week: ABA after a node is freed and re-pushed.
- Flag-then-data publication works on x86 CI and returns stale data on ARM production: missing release/acquire pairing.
- A "fast" atomic hit counter becomes the hottest line in the profile at 32 cores; per-core sharding fixes it.
- Two independent atomics in one struct thrash each other’s cache line (false sharing); padding doubles throughput.
- Python code assumes the GIL makes
n += 1atomic; totals are wrong under threads. - A CAS loop with no backoff under heavy contention livelocks a hot path — every thread fails and retries in lockstep.