Atomic operations

The problem it solves

An atomic operation is one that cannot be observed half-done. There is no moment at which another thread can see the read having happened but not the write, because there is no moment between them at all — the hardware performs the whole read-modify-write as a single indivisible act.

That sounds like a small distinction and it is the entire difference between a counter that works and one that does not. The lost update exists because count++ has an inside; an atomic increment does not have one.

What makes this worth its own page rather than a footnote is that “atomic” is one of the most misused words in the vocabulary. It does not mean fast. It does not mean thread-safe in some general sense. It does not mean the operation cannot be interrupted by the operating system. It means precisely that no other thread can observe an intermediate state — and knowing exactly how much that buys, and exactly where it stops buying, is the difference between using atomics correctly and reaching for them because they sound safe.

The mechanism

On the hardware, an atomic increment is a single instruction that takes the cache line containing the value into exclusive state, performs the read-modify-write while holding it, and releases it. No other core can read or write that line in between, because coherence gives exclusive ownership to exactly one core at a time. On x86 this is lock inc; on ARM it is a load-exclusive/store-exclusive pair that retries if anything intervened.

In the model on this page, atomicity is expressed by making the whole thing one operation rather than three. The scheduler chooses between threads between operations, so an operation that cannot be split is an operation nothing can be scheduled inside. The two-thread program has two operations total, therefore two interleavings, and both give 2.

That is the shape of every atomicity argument: you have not made the bad orderings less likely, you have made the positions they needed unavailable.

What the enumeration shows

Open the page on atomic-increment and read the outcome panel: one outcome, two schedules, no warning triangle anywhere. Then switch to lost-update and watch the space expand to twenty schedules and two outcomes, eighteen of them wrong.

Watching that number change is the lesson, and it is worth being precise about which number moved. The schedule count fell from twenty to two, because there are fewer places to interleave. The outcome count fell from two to one, because none of the remaining schedules can produce a wrong answer. A fix that reduced the first without reducing the second would be a fix that made the bug rarer, and that is exactly what most attempted fixes do.

The lattice on the atomic version is four nodes and four edges — a single diamond. The two paths diverge (either thread may go first) and rejoin at the same final state, which is the visual signature of an ordering that does not matter. Compare it to the lost-update lattice, where the paths diverge and stay apart.

The numbers worth carrying

• Atomic increment: 2 interleavings, 1 outcome. Non-atomic: 20 interleavings, 2 outcomes.
• An uncontended atomic on modern x86 costs roughly 20 nanoseconds, against about 1ns for a plain increment. Twenty times the cost of an operation that was nearly free, which is still nothing compared to a lock.
• An uncontended mutex lock/unlock pair is roughly 20–50ns when it never blocks, and microseconds when it does, because blocking means a context switch. The gap between “atomic” and “lock” is small when uncontended and enormous when not.
• Under heavy contention an atomic degrades badly — every increment needs exclusive ownership of the line, so throughput approaches one increment per coherence round trip, around 80ns, regardless of how many cores are trying.

Where it breaks down

Atomicity is per operation, not per intention. Two atomic operations are two atomic operations, not one. If a thread atomically decrements available and then atomically increments reserved, another thread can observe the state in between, where the item exists in neither. Anything that requires several values to change together needs a lock, a transaction, or a redesign that packs them into one value.

Check-then-act is not fixed by making each half atomic. if (atomicGet(x) == 0) atomicSet(x, 1) is exactly as racy as the non-atomic version, because the race lives between the two calls. This is the single most common way atomics are misused, and it is why compare-and-swap exists — see check-then-act and compare-and-swap.

Contention turns the fix into the bottleneck. A single atomic counter incremented by sixteen cores is a cache line being fought over sixteen ways, and its throughput is worse than a well-designed lock plus batching. False sharing describes the same coherence traffic arriving by accident.

Atomicity is not visibility, except that it usually is. The two are separate guarantees, and most language-level atomic types deliberately provide both by default. Once you start using relaxed memory orderings you have unbundled them, and you are now in the territory of memory barriers, where the operation is still indivisible and the ordering around it is not.

What people get wrong

“Atomic means thread-safe.” It means one operation is indivisible. A data structure built from atomic operations is not automatically correct; it is correct only if every invariant is maintained by a single one of them.

“Atomic means fast.” It is much cheaper than a lock when uncontended and much worse than a per-thread counter when contended. It is a correctness tool with a performance profile, not a performance tool.

“Atomic means it cannot be interrupted.” The thread can absolutely be preempted immediately before or after. What cannot happen is another thread observing the operation partway through.

“I made the field volatile and now increments are atomic.” No. volatile publishes each read and each write, and the read-modify-write sequence between them is untouched. This confusion is common enough to be worth stating twice.

In production

Every language ships these under slightly different names: java.util.concurrent.atomic.AtomicLong, std::atomic<T> in C++, sync/atomic in Go, Interlocked in .NET, AtomicUsize in Rust. All provide at minimum load, store, exchange, fetch-and-add and compare-and-swap.

The practical guidance is short. Use an atomic when one value must be updated indivisibly and nothing else needs to change with it. Use a lock when two or more things must change together, or when the critical section does anything non-trivial. And when contention is the problem rather than correctness, stop sharing the value: per-thread counters summed on read (LongAdder) beat a single atomic by an order of magnitude at high thread counts, at the price of a total that is only exact when nobody is writing.

The other thing worth internalising is that atomics are the building block, not the goal. Lock-free queues, reference counts, sequence locks and modern mutex implementations are all built from compare-and-swap on top of exactly this primitive.

The follow-up questions

“What does atomic actually mean?” — No other thread can observe an intermediate state. Say that, not “it cannot be interrupted”.

“You have an atomic counter and an atomic flag, and they must agree. Is that safe?” — No. Two atomics are two operations. This is the question that separates people who understand the guarantee from people who like the word.

“When would you use a lock instead?” — When more than one thing changes together, or when the critical section is more than a single operation.

“Sixteen threads incrementing one atomic counter. What happens?” — The cache line ping-pongs and throughput collapses to roughly one increment per coherence round trip. Then propose striping, and say what it costs: the total is approximate while writes are in flight.