Shared State & Races

The Atomicity Illusion

Some operations look indivisible in source and are not. counter++, list.append(x), dict[k] = dict[k] + 1, if not present then insert — each is one expression and several steps. This lesson is about learning what your language actually promises, which is almost always less than the syntax suggests and occasionally more.

▶ Run the lab

The question this answers

The question

Which operations does my language actually promise are indivisible, and which merely look that way?

The work

Three operations that every engineer writes without thinking: counter += 1 on a shared integer, results.append(x) on a shared list, and if key not in cache: cache[key] = compute().

What is shared

One integer, one list and one dictionary, each reachable from several tasks. All three are ordinary objects with no synchronization around them.

The invariant — what must stay true under every interleaving

counter equals the number of completed increments; results contains exactly one entry per completed task; cache[key] is computed at most once and every caller receives the same object.

Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.

WorkCan it overlap?Can it parallelise?What is shared?What ordering?What synchronization?Where is contention?What can deadlock?What can race?What is gained?What complexity?

One source line, several steps — the evidence

The fastest way to stop believing that x += 1 is atomic is to look at what the runtime actually executes. Below is the disassembly of a module-level increment on CPython 3.12 and the equivalent for a list append. The append is one bytecode after its arguments are on the stack; the increment is four. A thread switch may occur between bytecodes, which is exactly the distinction that makes one of these safe and the other not.

This is also where the most persistent piece of folklore in Python gets settled. The interpreter lock serialises *bytecode execution*; it does not serialise *statements*. list.append happens to be atomic on CPython because the append itself is a single bytecode implemented in C that does not release the lock partway. counter += 1 is not atomic because the load, the add and the store are separate bytecodes with switch points between them. Neither fact is a design guarantee you should lean on across versions or implementations — see the caveats.

The same reasoning applies everywhere, with different units. On preemptive threads the unit is the machine instruction and *nothing* multi-instruction is atomic. In a single-threaded event loop the unit is the synchronous run-to-completion block, which is much larger — so counter += 1 genuinely is indivisible there, and counter = await f() + 1 is emphatically not.

>>> import dis
>>> dis.dis(compile("counter += 1", "<s>", "exec"))
  0           RESUME                   0
  1           LOAD_NAME                0 (counter)      <-- shared READ
              LOAD_CONST               0 (1)
              BINARY_OP               13 (+=)           <-- private
              STORE_NAME               0 (counter)      <-- shared WRITE
              RETURN_CONST             1 (None)
              # a thread switch is permitted between ANY two of these.
              # LOAD_NAME ... STORE_NAME is read-modify-write: lost updates.

>>> dis.dis(compile("results.append(x)", "<s>", "exec"))
  0           RESUME                   0
  1           LOAD_NAME                0 (results)
              LOAD_METHOD              1 (append)
              LOAD_NAME                2 (x)
              CALL                     1                <-- the append itself
              POP_TOP
              RETURN_CONST             1 (None)
              # the CALL runs list.append in C. It does not release the
              # interpreter lock partway, so no element is lost.
              # This is an implementation property, not a language promise.

evidence that the difference is real, CPython 3.12, 8 threads x 100_000 ops:
    counter += 1        expected 800000   observed 231447   <-- 71% lost
    results.append(x)   expected 800000   observed 800000   <-- none lost
    (numbers are ILLUSTRATIVE of the shape; the exact loss rate varies
     with the switch interval, core count and load on every run.)
CPython 3.12 — `dis` output for two statements that look equally simple

What each language actually promises

The honest answer to "is this atomic?" is always "in which language, on which runtime, at which version". The comparison below is the set of promises you can actually rely on, separated from the behaviours that happen to hold today.

One rule cuts across all four and is worth memorising: atomicity of an operation is not atomicity of a sequence. Every language in this table has some genuinely atomic operations, and in every one of them a check-then-act built from two atomic operations is not atomic. That is the same point Finding the Critical Section makes about thread-safe collections, arrived at from the language side.

What is genuinely indivisible, and what only looks it — Increment a shared counter, append to a shared list, and insert into a map only if absent.
C++LANGUAGE-SPECIFIC
1int counter = 0;
2counter++; // NOT atomic. Read-modify-write; also a data
3 // race if two threads do it => undefined behaviour.
4
5std::atomic<int> counter{0};
6counter++; // ATOMIC. Compiles to a single lock-prefixed
7 // read-modify-write instruction on x86-64.
8counter.fetch_add(1); // same thing, explicit.
9
10std::vector<int> v;
11v.push_back(x); // NOT atomic, and may reallocate the buffer
12 // while another thread holds a pointer into it.
13
14std::map<K,V> m;
15if (!m.count(k)) m[k] = f(); // NOT atomic even with a thread-safe map:
16 // two operations, one gap. Use try_emplace
17 // under a lock, or std::call_once for init.

Nothing is atomic unless it is std::atomic or under a lock. The compiler will also happily reorder plain accesses, so "it looked atomic in the assembly I read once" is not an argument.

JavaScriptNODE.JS
1let counter = 0
2counter++ // indivisible WITHIN one synchronous block,
3 // because nothing else runs. Not a language
4 // guarantee about atomics — a consequence of
5 // run-to-completion scheduling.
6
7counter = (await load()) + 1 // NOT indivisible. The await is a switch point
8 // and the gap is a network round trip.
9
10arr.push(x) // safe within one isolate; nothing interleaves.
11
12const buf = new Int32Array(new SharedArrayBuffer(4))
13buf[0]++ // NOT atomic across workers: real shared memory.
14Atomics.add(buf, 0, 1) // atomic. The only correct form here.

Run-to-completion gives you free atomicity for synchronous blocks and takes it away the instant an await appears. Across workers with a SharedArrayBuffer you are back to full memory-model rules and Atomics is mandatory.

TypeScriptNODE.JS
1// Identical runtime semantics to JavaScript. The type system does not
2// model atomicity and cannot warn you about the gap:
3let inflight = 0
4async function handle(): Promise<void> {
5 if (inflight >= MAX) throw new Error('busy') // check
6 inflight++ // still same tick: fine
7 try { await work() } // <-- gap; other tasks run
8 finally { inflight-- } // safe: same tick as resume
9}
10// The counter arithmetic is atomic. The check-then-act across the whole
11// function is NOT, because MAX is compared before any await and inflight
12// is only incremented after. Reordering those two lines matters; putting
13// an await between them breaks it entirely.

The types tell you nothing about concurrency. What saves you here is the runtime's run-to-completion property, and what breaks you is the placement of await relative to the check and the act.

PythonCPYTHON
1counter += 1 # NOT atomic: 4 bytecodes, switch points between.
2lst.append(x) # atomic on CPython today: one C-level call.
3d[k] = v # atomic store on CPython today.
4d[k] += 1 # NOT atomic: read, add, store.
5if k not in d: d[k] = f() # NOT atomic: two operations, one gap.
6
7# The guaranteed-correct forms, which work on every implementation:
8from threading import Lock
9lock = Lock()
10with lock:
11 counter += 1
12
13import itertools
14counter = itertools.count() # thread-safe increment via next(counter)
15d.setdefault(k, v) # single call; no gap between check and insert
16# (setdefault still evaluates v eagerly - use a lock or functools.cache
17# when computing v is expensive.)

The "atomic" entries are properties of the current CPython implementation, not of the Python language. PyPy, Jython and free-threaded CPython 3.13+ do not necessarily agree, so code that relies on them is code that relies on an implementation detail.

What actually differs
  • C++ promises nothing unless you ask: only std::atomic and locks are indivisible, and everything else is subject to compiler reordering as well as scheduling.
  • JavaScript and TypeScript get atomicity of synchronous blocks for free from run-to-completion, and lose it entirely at every await — the gap moves from nanoseconds to milliseconds.
  • CPython's atomic-looking operations are implementation properties of the current build, not language guarantees; the free-threaded build changes them.
  • In all four, an atomic operation composed with another atomic operation is not atomic. Check-then-act is the universal counterexample.
  • The portable answer everywhere is the same: name the invariant, and if it spans more than one operation, take a lock or use a single primitive that performs the whole thing.

Atomic operations, non-atomic sequence

The schedule below uses list.append, which really is atomic on CPython, inside a membership check, which really is atomic on CPython — and produces a duplicate anyway. This is the cleanest demonstration available that "each operation is atomic" and "the code is correct" are unrelated claims.

It is also the exact shape of the most common real bug in this family: the memoised cache. if key not in cache: cache[key] = expensive() runs expensive() twice under concurrency, which is merely wasteful if the function is pure and is a genuine incident if it opens a connection, allocates a licence, or charges a card. See Initialization Races and Single-Flight Coalescing for the two standard answers.

Two atomic operations, one gap. CPython 3.12 semantics.ILLUSTRATIVE
Invariant · clients["eu-west"] is constructed at most once, and every caller receives the same object
#Worker A — ensure "eu-west" client existsWorker B — ensure "eu-west" client existsState
1"eu-west" not in clients → True [atomic]·clients={}
2·"eu-west" not in clients → True [atomic]clients={}
✕ Both workers have decided to construct. The invariant is already lost, with no write yet performed and no unsynchronized access anywhere.
3connect() → opens TCP connection #1·clients={} conns=1
4clients["eu-west"] = client1 [atomic]·clients={eu-west: c1} conns=1
5·connect() → opens TCP connection #2clients={eu-west: c1} conns=2
6·clients["eu-west"] = client2 [atomic]clients={eu-west: c2} conns=2
✕ Constructed twice. c1 is now unreachable from the map but still holds an open socket — a leaked connection with no owner and no code path that will ever close it.
7uses client1 for the rest of this request·clients={eu-west: c2} conns=2
Every individual operation in this trace is atomic on CPython. The object was constructed twice, one connection leaked with no reference anywhere to close it, and the two workers hold different clients while the map claims there is one. At startup with sixteen workers this is sixteen connections where the pool was sized for one — and the leak is permanent for the process lifetime.

Key points

  • Syntax is not a guarantee. x += 1 is one token and three shared-memory steps in every mainstream language.
  • Atomicity is a property of one operation on one location. It never composes: two atomic operations with a gap are not atomic.
  • CPython's interpreter lock serialises *bytecodes*, not statements. list.append is atomic today as an implementation detail; counter += 1 is not, at any version.
  • JavaScript and TypeScript get atomicity for free within a synchronous block and lose it at every await — where the gap is milliseconds, not nanoseconds.
  • C++ promises nothing without std::atomic or a lock, and a data race there is undefined behaviour rather than a wrong number.
  • The memoised-cache shape — if not present then compute and insert — is the atomicity illusion's most expensive form, because the duplicated work has side effects.
  • The portable fix is always the same: if the invariant spans two operations, use one operation that does the whole thing, or take a lock.

The loop, answered

Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.

How it works
  • The compiler or interpreter lowers each source statement into several primitive steps: a load of a shared location, some private computation, a store back.
  • The runtime chooses a granularity at which it will not interrupt: a machine instruction on threads, a bytecode on CPython, a synchronous run-to-completion block in an event loop.
  • Anything smaller than that granularity is indivisible; anything larger is not, and the source syntax gives no indication of which side of the line a statement falls on.
  • A library operation implemented in native code may be indivisible because it never yields — which is a property of that implementation at that version, not a promise in the language specification.
  • Composing two indivisible operations produces a divisible sequence, because the runtime's non-interruption promise covers each one separately and nothing in between.
Interleavings that matter
  • counter += 1 from two threads: A loads 0, B loads 0, A stores 1, B stores 1. One increment lost. On CPython this fires constantly — measured loss rates above 50% at eight threads are ordinary.
  • results.append(x) from eight threads on CPython: no interleaving loses an element, because the append is one uninterrupted C call. The same code on a free-threaded build has no such protection.
  • if k not in d: d[k] = f() from two tasks: both membership tests return True, f() runs twice, two objects are constructed and one is orphaned along with whatever resources it holds.
  • inflight++ before an await and inflight-- after: correct on a single-threaded runtime, because both arithmetic statements execute within a single uninterrupted block.
  • A check placed before an await and its act placed after: broken on the same runtime, because the gap is now the width of the awaited operation.
What it guarantees — and does not
  • C++ guarantees indivisibility only for std::atomic operations and for regions under a lock. Everything else is subject to reordering as well as interleaving.
  • CPython guarantees that a single bytecode does not interleave with another thread's bytecode on the standard build. It does not guarantee which operations map to one bytecode, and that mapping changes between versions.
  • A single-threaded event loop guarantees that a synchronous block runs to completion. It guarantees nothing across an await, a yield, or a callback boundary.
  • A thread-safe collection guarantees each of its methods is atomic. It explicitly does not guarantee that your sequence of calls is — which is why putIfAbsent, setdefault and compute exist as single operations.
  • An atomic increment guarantees the counter is exact. It guarantees nothing about any other variable that is supposed to agree with it.
Where contention appears
  • Making a counter atomic moves the contention onto a single cache line: every increment invalidates the line in every other core's cache, so throughput can fall as cores are added. See False Sharing: Different Variables, Same Cache Line and What a Shared Write Costs.
  • CPython's interpreter lock is itself a contention point — CPU-bound threads serialise on it regardless of how atomic your operations are. That is a throughput property, not a correctness one; see Python: Threads, Processes and the GIL.
  • The if absent then compute shape has a contention profile that is invisible until startup: N workers all miss the cache simultaneously and all perform the expensive work at once. See Thundering Herd.
How it fails
  • Lost update — the read-modify-write case, silent and load-proportional.
  • Duplicate initialisation — the check-then-act case, which leaks whatever the duplicate construction allocated.
  • Torn read or write, where a value wider than the platform's atomic unit is observed half-updated. Rare in managed languages; real for 64-bit values on 32-bit targets and for structs in C++.
  • Data race, in C and C++, with undefined behaviour rather than a wrong value. See Data Race Is Not Race Condition.
  • Version-dependent correctness: code that relies on an operation being atomic on CPython 3.11 and breaks on a free-threaded 3.13 build, with no source change and no warning.
When it helps
  • Knowing what is genuinely atomic lets you delete locks that are not needed — a single atomic counter needs no mutex, and a run-to-completion block needs no lock at all.
  • It resolves the most common review argument in Python and JavaScript teams with evidence rather than opinion: run dis, count the bytecodes, look for the await.
  • It tells you when the cheap fix is available: many "add a lock" problems are actually "use setdefault / putIfAbsent / fetch_add" problems.
When it hurts
  • Relying on implementation-detail atomicity is a time bomb. list.append being atomic is true of CPython today and is not something the language promises.
  • The knowledge invites cleverness — lock-free code written because an operation "is atomic anyway" is where the subtlest memory-model bugs come from. See Atomics Are Not Magic.
  • Over-applied, it produces atomic variables everywhere, which is slower than a lock under contention and does nothing for multi-variable invariants.
How you would know
  • Disassemble. dis.dis in Python, -S or Compiler Explorer for C++, and for JavaScript simply look for await between the check and the act. This is a two-minute check with a definitive answer.
  • Run the operation N times from K tasks and assert exactly N×K. Approximate assertions hide exactly the bug you are looking for.
  • Count side effects, not values: log connection opens, object constructions and external calls. Duplicate initialisation shows up there long before it shows up in a counter.
  • Test on the runtime you deploy on, at the version you deploy. An atomicity assumption that holds on CPython 3.11 and fails on a free-threaded build will not be caught by any static tool.
Complexity it introduces
  • Every reliance on an implementation-level atomicity guarantee is an undocumented dependency on a runtime version, and it will not announce itself when that version changes.
  • The rules differ per language in a codebase that spans several, so the same reviewer must hold three different models — and the Python one changes between builds.
  • The safe alternatives (a lock, a single compound operation) are cheap to write and cheap to read, which is why leaning on subtle atomicity is usually a bad trade even when it is correct.
Simpler alternatives
  • Use the single compound operation the library already provides: setdefault, putIfAbsent, compute, fetch_add, Atomics.add, INCR. One call, no gap, and it is the reason those methods exist.
  • Use a lock. Under low contention it costs a few tens of nanoseconds uncontended and removes the entire question. See Mutexes: What They Protect and What They Do Not.
  • Use a proper once-initialiser for the memoised-cache shape: std::call_once, functools.cache, a module-level singleton evaluated at import. See Initialization Races.
  • Do not share the value at all — accumulate per task and combine at the end. Correct on every runtime and every version. See Parallel Reduce.

counter++ with and without atomicity

counter++ with and without atomicity
The same program on both sides: N threads, one shared counter, one increment each. On the left counter++ is read, add, write. On the right it is a single indivisible instruction. Every schedule of both is enumerated.
20 schedules enumerated on the left, 2 on the right
counter++ — read, add, write
r ← counter
r ← r + 1
counter ← r
schedules
20
lose an update
18
end at 2
2
worst case
1
final counter = 118 · 18 of 20 schedules
final counter = 22 · 2 of 20 schedules
atomic fetch_add — one indivisible step
fetch_add(counter, 1)   # no schedule can cut inside this
schedules
2
lose an update
0
end at 2
2
worst case
2
final counter = 22 · 2 of 2 schedules — the order still varies, the outcome does not
The threads still interleave. Atomicity does not remove the schedules; it removes the points at which a schedule can cut.
The non-atomic version, run 200 times under a random scheduler
runs that produced the right answer59 · 29.5% — a green test suite
runs that lost an update141 · 70.5%
With 2 threads there are 20 schedules of read/add/write and 18 of them — 90.0% — end with a counter smaller than 2. The worst is 1: every thread read 0, every thread computed 1, and the last write erased the rest. And yet 59 of the 200 sampled runs above produced exactly 2. That is why the non-atomic version passes tests. A test does not explore the schedule space, it samples it, and the sampling is biased by whatever the machine happened to be doing. 29.5% green is not 29.5% correct — the invariant is "after k completed increments, counter === k", and it is false in 18 legal schedules whether or not today's run found one. The right-hand column does not test better, it removes the schedules: an atomic read-modify-write has no interior for the scheduler to cut into. That buys correctness for one variable only — atomics compose badly, and two atomic operations in a row are not one atomic operation.
SIMPLIFIEDSchedule counts are exact for this model of the program. counter++ is modelled as three indivisible steps; a real compiler may split it further, and a real CPU may fuse it into one atomic instruction — which is exactly the right-hand column.

Two increments, twenty schedules: find the one that loses an update

Two increments, twenty schedules
Both tasks run counter++ on the same variable. Drive the schedule yourself: read, add, write are three separate steps, and the scheduler may cut between any two of them.
6/6 steps
counter
2
increments completed
2
rA / rB
1 / 2
invariant
holds
Invariant · after k completed increments, counter === k. No update is lost.
#Task A — counter++Task B — counter++State
1rA ← counter·counter=0 rA=0 rB=0
2rA ← rA + 1·counter=0 rA=1 rB=0
3counter ← rA·counter=1 rA=1 rB=0
4·rB ← countercounter=1 rA=1 rB=1
5·rB ← rB + 1counter=1 rA=1 rB=2
6·counter ← rBcounter=2 rA=1 rB=2
counter = 2, and both callers are right. This schedule happens to be safe because one task finished entirely before the other started. Safe once is not safe: press "Enumerate all" to see how many of the possible schedules do not. Testing samples this space; it does not cover it.
SIMPLIFIEDcounter++ modelled as three indivisible steps. Real compilers and CPUs can split it further, or fuse it into one atomic instruction.

compare_exchange in a loop — retries, and the pointer that lied

compare_exchange in a loop
Read the value, compute a new one, swap it in only if nobody changed it meanwhile — otherwise start over. The loop is lock-free: somebody always makes progress. It is not free: everybody else did the work twice.
do {
    old = counter.load();          # 1 read
    next = old + 1;                # compute off to the side
} while (!counter.compare_exchange(old, next));   # swap only if unchanged
successes
8
CAS attempts
36
wasted retries
28
attempts per success
4.5
Total CAS attempts to complete N increments
1 thread1 · 1 succeed, 0 wasted · 1.0× the work per increment
2 threads3 · 2 succeed, 1 wasted · 1.5× the work per increment
4 threads10 · 4 succeed, 6 wasted · 2.5× the work per increment
8 threads36 · 8 succeed, 28 wasted · 4.5× the work per increment
16 threads136 · 16 succeed, 120 wasted · 8.5× the work per increment
32 threads528 · 32 succeed, 496 wasted · 16.5× the work per increment
CAS succeeds on a stale pointer
Invariant · head points at a live node, and the stack contains exactly the nodes pushed and not yet popped.
#T1 — pop() via CAST2 — another threadState
1old ← head (= A)·head=A stack=A→B→C
2·pop() → Ahead=B stack=B→C
3·pop() → Bhead=C stack=C
4·push(A)head=A stack=A→C
5CAS(head, A, B) → SUCCESS·head=B stack=B→ freed
✕ head now points at B, which was popped and freed. Node C has vanished from the stack and T1 returned a node it never observed being on top.
6return A to the caller·head=B stack=corrupt
At 8 threads the loop costs 36 attempts for 8 increments — 4.5 attempts each, and the total grows as N²/2 while the useful work grows as N. Half the machine is now computing values that will be thrown away, and every failed attempt still pays for exclusive ownership of the cache line. Turn the guard on and watch the same schedule end differently. Without it, T1 asks "is head still A?" — the only question CAS can ask — and A is indeed back on top. But it is on top of a different stack: B was popped and freed while T1 was looking away, and the CAS happily installs a pointer to reclaimed memory. This is the ABA problem, and it is not a race in the usual sense: nothing was concurrent at the moment of the CAS, the world simply changed and changed back. Lock-free is a progress guarantee — some thread always advances — not a speed guarantee. Under this much contention a plain mutex often wins, because it lets the losers sleep instead of burning cores computing values nobody will keep.
SIMULATEDWorst-case contention: every thread attempts every round and exactly one wins. Real hardware backs off, and cache-line ownership changes the constant — the quadratic shape does not.

What people believe, and what is true

Claim

The GIL makes Python thread-safe.

Reality

It serialises bytecode execution, which prevents torn values. counter += 1 is four bytecodes and loses updates at a rate you can measure in seconds.

Claim

counter++ is one instruction, so it is atomic.

Reality

On x86-64 it is typically three: a load, an add and a store. Only lock-prefixed forms — what std::atomic emits — are indivisible.

Claim

My runtime is single-threaded, so atomicity is not my problem.

Reality

Atomicity within a synchronous block is free; across an await it is gone. The single-threaded runtime moved the boundary, it did not remove it.

Claim

I used a concurrent map, so if absent then put is safe.

Reality

Each operation is atomic and the pair is not. That is precisely why concurrent maps ship a separate putIfAbsent — it exists because the composition is broken.

Go deeper

Overview

Operations that look like one step are usually several. The runtime can interrupt between them, and then two tasks interfere.

Practical

Ask what the runtime's non-interruption unit is: a machine instruction, a bytecode, or a synchronous block. Anything larger than that unit is not atomic, however short the source line.

Advanced

Distinguish language guarantees from implementation properties. std::atomic is a guarantee; list.append being atomic is a CPython implementation detail that free-threaded builds change. Build on the first, never the second.

Internals

On x86-64, atomicity for a read-modify-write comes from the lock prefix, which holds the cache line exclusively for the duration of the operation. Weaker architectures use load-linked/store-conditional pairs that fail the store if the line was touched — the hardware form of Compare-and-Swap and the Retry Loop. In both cases atomicity is per cache line, which is why two unrelated atomic counters in the same line contend; see False Sharing: Different Variables, Same Cache Line.

Apply it