The lost update

The problem it solves

Two threads each add one to a counter that starts at zero. Afterwards it holds one.

Nothing crashed, nothing was logged, no exception was swallowed. Both threads ran their code exactly as written, the hardware did what it was told, and one of the two increments simply is not there. If you have ever seen a metric that drifts slowly downward from where it should be, or a view counter that undercounts by a percent that grows with traffic, you have seen this.

The reason it happens is that count++ is not an operation. It is three: read the current value into a register, add one to the register, write the register back. In between any two of those, the other thread may run — and if it does, it reads the same starting value, adds one to the same starting value, and writes back the same result. Two increments, one effect. The update was not corrupted; it was overwritten by an increment that was computed before it happened.

The word people reach for is “race condition”, and the word is where most understanding stops. The useful thing is not the label but the picture: which orderings are safe, which are not, and how many of each there are.

The mechanism

Each thread’s three operations must happen in order relative to each other. Nothing constrains them relative to the other thread’s. So the question “what can happen?” is the question “in how many ways can two sequences of three be shuffled together, keeping each in order?” — and that is a number you can compute: twenty.

Of those twenty, exactly two produce the answer 2. Both are the orderings where one thread finishes entirely before the other begins: load-add-store, then load-add-store. Every other ordering — all eighteen of them — has the second thread’s load happening before the first thread’s store, so both threads read the same value and the second store overwrites the first.

That ratio is the part that reframes the problem. The failure is not an edge case that occurs under unusual timing. It is what happens in ninety percent of the ways the program can run. What makes the bug rare in practice is not that the bad orderings are unlikely in principle, but that a real thread usually gets through three instructions without being interrupted — until the machine is busy, or the scheduler preempts, or you move to a machine with more cores, at which point the rate climbs and nobody can reproduce it locally.

What the enumeration shows

The explorer above enumerates all twenty and marks the two that work. Click the failing outcome and it filters to the eighteen orderings that produce it; step through any one of them and the timeline reads out the ordering in words — T1 load, T1 add, T2 load, T1 store, T2 add, T2 store — with count visible in the state panel going to 1.

Three things are worth doing on this page specifically.

First, watch the lattice. Its nodes are states, not positions, so two paths merge only when the order genuinely did not matter. The early part of the diagram is full of diamonds — those are the orderings where it makes no difference who went first — and then the paths separate and never rejoin, because by then the two threads have read different things and no subsequent ordering can bring them back together.

Second, switch to atomic-increment. The outcome space collapses from two states to one, and the schedule count drops from twenty to two. This is what makes atomicity different from “faster locking”: the losing orderings do not become unlikely, they cease to exist, because there is no longer a point between the read and the write for the other thread to occupy.

Third, switch to lost-update-simple, which folds the add into the store. Six interleavings, four of them wrong. Fewer operations is not fewer races — two shared touches still leave a window, and the window is all that was ever needed.

The numbers worth carrying

• count++ on two threads: 20 interleavings, 18 lose an update.
• Fold the add into the store: 6 interleavings, 4 lose an update.
• Make it atomic: 2 interleavings, 0 lose an update, 1 possible outcome.
• The general shape: n threads each doing k operations gives (nk)! / (k!)^n interleavings. Three threads of three operations is 1,680. The space grows faster than anybody’s ability to reason about it informally, which is the argument for enumerating rather than thinking hard.

The arithmetic that matters in an interview is the first line, and the sentence that goes with it: the failure is the common case, not the edge case.

Where it breaks down

The model above assumes each of the three steps is itself indivisible, which is true for aligned word-sized values on every architecture you are likely to meet, and false for larger values. A 64-bit counter on a 32-bit machine is two stores, so a reader can observe half of one increment — a value that neither thread ever computed. That is word tearing, and it makes the outcome space larger than this page shows.

It also assumes writes become visible when they happen. They do not; a write can sit in the writing core’s store buffer while other cores continue to see the old value, which admits outcomes that no interleaving of the program explains at all. That is the subject of visibility and store buffers, and it is where the interleaving model — the one this entire page is built on — stops being sufficient.

Finally, the counter here is contended by exactly two threads. With more, the number of lost updates per unit time rises roughly with the square of the thread count, because both the chance of overlap and the number of pairs that can overlap increase together.

What people get wrong

“It is a rare timing issue.” Eighteen of twenty. It is rare in observation because uninterrupted execution is common, not because the bad orderings are exotic.

“Adding a sleep or a log line fixed it.” Both change the timing and neither changes the set of possible orderings. The bug is still there and is now harder to reproduce, which is worse.

“count++ is one instruction.” On x86 it can be, with a lock prefix — and that prefix is exactly the difference between the atomic version and this one. Without it, inc [mem] is still read-modify-write and still racy across cores.

“We tested it under load and it was fine.” A test explores the orderings the scheduler happened to produce. It cannot explore the ones it did not, and it cannot tell you which ones it missed. That is the argument for drive mode’s fix-it exercise, where a fix is accepted only when the whole space comes back clean.

“Making it volatile fixes it.” It does not. volatile is about visibility, not atomicity — the read and the write each become properly published, and the gap between them is untouched. This is the single most common wrong answer to this question.

In production

The fix depends on what you are counting. For a single counter, an atomic type is correct and cheap: AtomicLong, std::atomic<int64_t>, sync/atomic, Interlocked.Increment. For anything that updates several fields together, an atomic per field is not enough — the set of updates has to be indivisible, which needs a lock or a transaction.

At high contention a single atomic becomes its own bottleneck, because every increment must take the cache line exclusively and the line ping-pongs between cores. That is the same coherence traffic described on false sharing, and the standard fix is striping: LongAdder in Java keeps per-thread cells and sums them on read, trading exact-at-every-instant for enormously better throughput.

And the version that avoids the problem entirely is to not share the counter: each thread keeps its own and something sums them at the end. This is what map-reduce does, what per-core statistics counters do, and why immutability and actors end up being the cheapest answer more often than people expect.

The follow-up questions

“Why is count++ not atomic?” — Three operations: load, add, store. Say the three and the answer is finished.

“How many ways can two increments interleave, and how many are correct?” — Twenty and two. Being able to produce that number is a much stronger answer than “several”.

“Does volatile fix it?” — No, and say why: visibility versus atomicity. Then say what does.

“Your fix uses an atomic. Now make it a counter per user, updated with a name change in the same operation.” — An atomic per field is not enough once two fields must agree; this is where a lock or a transaction becomes necessary, and knowing the boundary is the point of the question.