Topic 05

Atomics and Memory Models

Concurrency

Underneath every lock is a single instruction that the processor promises to execute indivisibly, even with 64 cores watching the same memory. Underneath that promise is a stranger fact. Neither the compiler nor the processor performs a program's memory operations in the order the code wrote them, and another core can observe the difference.

The atomic instruction has a price, and the contract that says which reorderings a program is allowed to see has a name: the memory model. Python programmers meet this layer mostly through their runtime, and engineers in Java, Go, C#, C++ or Rust meet it directly. Either way, it is where bugs that appear on one machine and not another come from.

Compare-and-Swap

The processor offers an instruction that reads a memory location, compares it with an expected value and writes a new value only if they match, all as one indivisible step. It is called compare-and-swap. Its simpler sibling, fetch-and-add, adds a number to a location and returns the old value, also in one step. An atomic increment is the lost update of this chapter's second topic made impossible in hardware: there is no gap between the read and the write for anyone to land in.

An increment built from compare-and-swap (compare_and_swap is hypothetical: Python does not expose the instruction)

def increment(cell):
    while True:
        old = cell.value
        if compare_and_swap(cell, expected=old, new=old + 1):
            return          # nobody wrote in between: done
        # somebody else changed the value first: read again and retry

The loop above shows how software builds on the instruction. It reads the current value, computes the new one and asks the processor to store it only if the cell still holds the value it read. If another thread changed the cell in between, the swap fails, nothing is written, and the loop reads the fresh value and tries again. No update is ever lost; at worst some are retried. The function is written with a made-up compare_and_swap because Python code has no direct way to issue the instruction.

What an Atomic Costs

Uncontended, an atomic operation costs from a few to a few tens of nanoseconds, because the core must first take exclusive ownership of the cache line, the 64-byte unit of Chapter 4, that holds the value. Contended by many cores, the line moves from core to core on every operation, around 100 nanoseconds a move. One shared atomic counter therefore makes every core that touches it take turns, which is a serial section in Amdahl's sense, built out of hardware.

The unit of contention is the line, not the variable. Two unrelated counters that happen to sit in the same 64-byte line contend exactly as if they were one: each core's write drags the whole line away from the other. This is the false sharing that Chapter 4 named, and it is invisible in the source code, where the two counters have nothing to do with each other.

False sharing: two counters, one line, one queue

Reordering by the Compiler and the CPU

A compiler may keep a value in a register instead of re-reading it from memory, or move a store past a later load, because within one thread nobody can tell the difference. A processor buffers its stores and lets later loads overtake them, part of the out-of-order machinery of Chapter 3. Both changes are invisible to the thread that runs the code, which always sees its own operations in order.

Another core can see them. Suppose core 1 writes some data and then sets a "ready" flag, and core 2 waits for the flag and then reads the data. On a weakly ordered processor such as ARM, the data store can sit in core 1's store buffer while the flag reaches memory first, and on any processor the compiler may swap the two stores. Core 2 then sees the flag set, reads the data and gets the old value. Nothing in either thread's code is wrong on its own.

The flag arrives before the data

The Memory Model and Happens-Before

A memory model is the contract between the program, the language and the hardware about which orders may be observed. Its central rule is happens-before. If thread A releases a lock, or writes an atomic variable with release ordering, and thread B later acquires the same lock, or reads that write with acquire ordering, then everything A did before the release is visible to B after the acquire. Code that publishes data through such a pair is correct on every machine; code that relies on anything else is correct by accident.

The hardware differs in how often the accident is caught. The x86 processors in most servers reorder very little: the only reordering they allow is a later load overtaking an earlier store. The ARM processors in phones, many laptops and a growing share of cloud servers reorder much more. Code that is correct by accident on one breaks on the other. Java, C and C++, Go and Rust each publish a memory model, and the ordering keywords in those languages are how a program states which orders it needs.

Lock-Free by Idea

A lock-free data structure uses compare-and-swap loops instead of locks, so that a thread switched out in the middle of an operation never blocks the others, and some thread always makes progress. That guarantee is the point, and it matters in places such as kernels and real-time systems where a stalled lock holder is unacceptable.

The price is subtlety. A value can change and change back between a read and its compare-and-swap, so the swap succeeds on a structure that is no longer the one it read, which is called the ABA problem. Freeing memory that another thread may still be reading is hard without a garbage collector. Lock-free code is for specialists and for the standard libraries they write.

Ordering Bugs and Hot Counters

Python code meets this layer through its runtime. The interpreter, the free-threaded build of the last topic and every C extension must get ordering right, and when one of them does not, the bug looks like a lost update on one machine and nothing at all on another. In Java, Go, C#, C++ and Rust the layer is on the page.

Two consequences show up in production. One atomic counter shared by 64 threads is slower than 64 per-thread counters summed when someone reads them, because the shared one is a single cache line passed around in a queue. And a hand-rolled ready flag without the right ordering can pass every test on x86 and fail first on an ARM server or laptop.

Misconceptions

"The CPU runs my instructions in the order I wrote them." It makes them appear in order to the thread running them, while executing them, and making them visible to other cores, out of order. The compiler has often rearranged them before the processor sees them.
"Code that works on x86 is correct." x86 permits few reorderings, so missing ordering usually goes unpunished there. The same code on an ARM server or an ARM laptop can see the flag before the data.
"The volatile keyword makes a variable thread-safe." In C and C++ it gives neither atomicity nor ordering between threads. In Java it gives visibility and ordering, but an increment of a volatile field is still three steps and still loses updates.
"Lock-free code is faster than code with locks." Lock-free guarantees progress, not speed. Under contention a compare-and-swap loop retries and moves the same cache line, and an uncontended lock costs one atomic operation anyway.
"An atomic counter scales with cores." Every increment needs exclusive ownership of one cache line, so at 64 cores the counter is a serial section. Per-core counters summed on read scale where it cannot.

Why It Matters

Use locks and the standard library's concurrent structures before raw atomics. They encode the ordering rules correctly.
Publish data between threads only through a lock, an atomic with release and acquire ordering, or a thread-safe queue, never through a plain flag. Only those create a happens-before edge.
Shard hot counters per thread or per core and sum them on read. One contended cache line is a serial section.
Run concurrency tests on the most weakly ordered hardware you ship to. An ARM machine finds ordering bugs that x86 hides.

RelatedSpeculation and out-of-order execution the same machinery seen from the performance side (Chapter 3)Read-copy-update a kernel technique where readers take no lock and writers publish new versionsMultiversion concurrency control versioning instead of locking, one layer up (PostgreSQL Deep Dive)

Knowledge Check

Thread A writes data and then sets a plain flag. Thread B waits for the flag, then reads the data. No lock or atomic ordering is used. Where can B see the old data?

Only on ARM, since x86 never reorders any memory operation at all
Only on x86, since ARM executes memory operations strictly in order
On both, and far more often on ARM, which reorders much more than x86
Nowhere, since a thread always sees the operations of others in order

A counter is incremented atomically by 1 thread, and later by 64 threads on 64 cores. What happens to the cost per increment?

It stays at a few nanoseconds, since the instruction is the same
It rises to about 100 ns, as the one cache line moves every time
It falls, since 64 cores share the work of each increment
It rises to microseconds, since each core must enter the kernel

Two threads increment two separate counters, a and b, with no sharing between them. Performance collapses as if they shared one counter. What is the likely layout?

The counters are in different processes, so each write crosses the kernel
The counters are Python integers, so the interpreter lock serializes them
The counters are far apart in memory, so each one misses the cache on every write
The counters sit in the same 64-byte cache line, so each write drags it away

What does happens-before guarantee when thread A releases a lock and thread B then acquires it?

That B sees everything A wrote before its release
That B will acquire the lock sooner than any other waiter
That A's writes after the release are visible to B too
That both threads now run on the same core, in order

Why is "lock-free" a progress guarantee rather than a speed guarantee?

Because lock-free structures are always slower, trading speed for safety
Because lock-free code still takes locks, only far fewer of them per operation
Because some thread always finishes, while contended retries still cost time
Because progress is measured per thread, and each thread finishes in bounded time

You got correct