Atomic Operations

What "atomic" actually means

The dictionary definition is "indivisible." In concurrency, an operation is atomic if no thread can ever observe it half-done. A non-atomic 64-bit store on a 32-bit machine, by contrast, can be observed mid-flight: another core might see the lower 32 bits updated and the upper 32 bits stale. Atomicity rules out exactly that.

The C11/C++11 standards formalize a small alphabet of atomic operations:

• Atomic load. Read a value with no torn reads.
• Atomic store. Write a value with no torn writes.
• Exchange. Atomically swap a memory location with a value, returning the old value.
• Compare-and-swap (CAS). Conditional swap based on expected value.
• Fetch-add / fetch-sub / fetch-or / fetch-and / fetch-xor. Atomic read-modify-write that returns the old value.
• Wait/notify. Block until a value changes — added in C++20.

Each of these is one instruction on x86 (with LOCK prefix) or a small LL/SC sequence on ARM/POWER/RISC-V. The standard library wraps them so portable code looks identical regardless of architecture.

x86 LOCK vs ARM LL/SC

Two architectural philosophies dominate.

x86: The LOCK prefix on instructions like ADD, OR, XCHG, CMPXCHG turns a non-atomic instruction into an atomic one. The hardware acquires exclusive cache-line ownership, performs the operation, and releases. XCHG on x86 has implicit LOCK semantics — there's no non-atomic exchange. Intel guarantees that a LOCK-prefixed instruction is atomic with respect to all other LOCK-prefixed instructions on any core, regardless of cache-line alignment (though aligned access is much faster).

ARM (and other RISCs): ARM uses load-linked/store-conditional (LL/SC) — paired instructions LDXR (load exclusive) and STXR (store exclusive). LDXR reads and "reserves" the line; STXR writes only if the reservation is still intact. If anything between the LDXR and STXR could have invalidated the reservation (another core's write, a context switch, an interrupt), STXR fails and you must retry. This is more general — you can compute any function between LDXR and STXR — but more error-prone, since spurious failures are possible. ARMv8.1 added a direct CAS instruction (CASAL) as an addition, recognizing that pure LL/SC scaling on heavy contention was poor.

Memory ordering matters as much as atomicity

Atomicity prevents partial observations of one location. But threads care about the order of operations across multiple locations — a producer wants the consumer to see its data write before its flag write. C++11 expressed this with six memory orders, ordered from weakest to strongest:

• memory_order_relaxed — atomicity only, no ordering. Cheapest, used for counters where you don't need to synchronize-with anything else.
• memory_order_consume — data-dependency ordering. Almost universally implemented as acquire because compilers can't reliably track dependencies.
• memory_order_acquire — used on the load side of synchronization. Subsequent reads/writes can't be reordered before the acquire load.
• memory_order_release — used on the store side. Prior reads/writes can't be reordered after the release store.
• memory_order_acq_rel — both. Used for read-modify-write that participates in synchronization on both sides.
• memory_order_seq_cst — sequentially consistent. Strongest; full barriers; default for std::atomic operations.

On x86, relaxed and acquire/release loads compile to plain MOV — TSO already provides those guarantees. On ARM, weaker orders save real fence cycles. The C++ default of seq_cst is portable but conservative; performance-tuned lock-free code uses acq_rel or relaxed where the algorithm allows.

fetch-add and atomic counters

Atomic counters use fetch_add directly:

std::atomic<uint64_t> counter{0};

uint64_t observe_event() {
  return counter.fetch_add(1, std::memory_order_relaxed);
}

On x86, this compiles to lock xadd — one instruction. On ARM (pre-v8.1), it compiles to a small LL/SC loop:

retry:
  ldxr  x0, [counter]   // load exclusive
  add   x1, x0, #1
  stxr  w2, x1, [counter] // store conditional
  cbnz  w2, retry        // failed? retry

ARMv8.1 has LDADD for direct fetch-add, comparable to x86. Either way, the cost is dominated by cache-coherence traffic, not instruction count.

This is also where the high-contention scalability problem appears. A counter shared across N cores serializes — only one core at a time owns the cache line. At 32 cores, throughput plateaus or goes backwards. Mitigations: per-thread counters with periodic sum, sharded counters across multiple cache lines, or padded array with one counter per core.

Why atomic operations matter

• Counters and statistics. Web servers tally requests with atomic counters. JVM tracks GC events. Linux per-CPU counters are atomic locally but periodically merged.
• Lock-free queues. Michael-Scott queue, MPSC ring buffers, and disruptor patterns are built from atomic loads, stores, and CAS.
• Garbage-collected reference counts. Rust's Arc, C++ shared_ptr, Swift's reference counts — all use atomic increment/decrement.
• Kernel data. Linux atomic_t, futex word, RCU pointer flips. The kernel uses thousands of atomics; their overhead is critical.
• Lock implementations. Mutex acquire is typically a CAS on the lock word; the kernel-mediated wait path is slow, but the fast path is one atomic.
• Sequence numbers. Distributed systems often use a process-local atomic counter as the seqno source.

Common misconceptions

• Always lock-free. The C++ standard allows std::atomic to be implemented with a mutex if hardware doesn't support the size. atomic<T>::is_lock_free() tells you for sure. 64-bit atomics on 32-bit ARM may use a lock internally.
• Atomic implies ordered. Atomicity and ordering are separate properties. memory_order_relaxed gives atomicity with no ordering — a release/acquire pair on a different variable is needed to synchronize a producer/consumer protocol.
• Atomic is slow. Uncontended atomics on cache-resident lines cost 10-30 cycles — single-digit nanoseconds. The slowness is contention, not the operation itself.
• volatile is enough. volatile in C/C++ prevents compiler reordering, but provides no atomicity (a 64-bit volatile read on a 32-bit machine can tear) and no inter-thread ordering. Use atomic.
• Two atomics combine. Two separate atomic operations are atomic individually, not jointly. Reading atomic x and atomic y gives you values that were each instantaneously consistent but may correspond to different points in time.
• Atomic adds always linearize FIFO. Hardware doesn't guarantee fairness. The order in which contending CAS or fetch-add operations succeed is implementation-defined; over-attempting cores may starve others briefly under heavy contention.