Concurrency Primitives Primer

A statement is not an instruction. x++ on a shared counter is three: thread A loads x into a register, adds one, and stores it back. Nothing in the hardware makes those three indivisible, and the scheduler may drop thread B's three anywhere among them.

Both threads start from x = 0 and each mean to add one, so the answer is 2. Drag thread B's block along thread A's timeline, and watch the bottom row — x after every step:

Notice that only the two extreme positions give 2. Everywhere in between, B loads x before A has stored it, both registers hold 0, both store 1, and one increment is simply gone. Nothing threw. Every line ran exactly as written and the counter is wrong.

A block drag reaches only four of the orders a scheduler can pick. There are twenty merges of two three-instruction sequences, and the slider walks all of them: the one under your hand is arrowed on the strip below, beside the ones that end at 2 and the ones that lose an update:

Two. Two of the twenty reach the right answer, and both are the ones where a thread runs to completion before the other starts. That is why races survive testing: losing the update needs no unusual hardware and no unusual load — it is the default outcome, and a test that happens to run the threads apart passes.

The same shape hides inside anything that checks and then acts. Here thread A asks a map whether a key is present and, four instructions later, fetches it — slide thread B's remove through A's instruction stream:

Four of the nine landing points fall between the check and the act, and in those the fetch returns null for a key the code had just proved was there. This is the atomicity bug in its usual disguise: two calls that are each individually atomic, composed into a sequence that is not. ConcurrentHashMap does not save you here; computeIfAbsent does, because it is one call.

The hardware has its own version of the same thing. A lock-prefixed instruction is indivisible only while its operand sits inside one 64-byte cache line — drag the eight-byte atomic across the boundary at byte 60:

Because a split operand spans two lines, the core cannot cover it with one line lock and falls back to locking the bus: about 1,000 cycles, 330 ns at 3 GHz, against 20 ns aligned. Worse, the bus lock stalls every core on the socket, not just yours. Linux ships split_lock_detect to turn it into a signal rather than a slow mystery.

That 3 GHz is the machine every nanosecond on this page is quoted for: one socket, cores on one die behind one L3. Each constant is an order-of-magnitude value derived from a cycle count at that clock — 1 ns an L1 hit, 20 ns an uncontended atomic, 100 ns a line moved between cores, 2 µs a park and a wake — not a benchmark of a named part.

Two fixes exist and they are not the same fix. A mutex makes the whole section exclusive; fetch_add collapses it into one instruction the hardware will not split. Switch between them and drag thread B's block again:

Under either one the offset stops mattering — the entire point of both. They differ in reach: fetch_add handles one machine word, a mutex handles anything, at the price the next section spends. The invariant the plain version breaks: between the load and the store of a read-modify-write, no other thread reads or writes x.

glibc's mutex is one 32-bit word with three states: 0 free, 1 held, 2 held-with-waiters. Locking is a compare-and-swap from 0 to 1 and nothing else — no syscall, no kernel. The kernel appears only when a thread actually has to wait.

Step through a contended acquisition and watch the futex word on the bottom row, and the two steps that enter the kernel:

Notice how little of that is kernel. Thread A takes and releases the lock without one syscall; only thread B, which lost, pays for futex_wait. And note step 4: B has to move the word from 1 to 2 first, because otherwise A's unlock has no way to know anyone is waiting and would skip the futex_wake altogether.

That asymmetry is the whole performance story. An uncontended lock and unlock is two atomics, about 40 ns; one that parks costs a syscall, a context switch and a wakeup, about 2 µs. Raise the fraction that contends:

Watch how fast the mean leaves the floor. At 10% contention the average pair already costs 240 ns — six times the uncontended one — even though nine acquisitions in ten still never enter the kernel. A lock is not slow; waiting is slow.

Which is why real implementations spin before they sleep. Set a spin budget, then move how long the holder actually keeps the lock:

Below the budget the waiter never sleeps and the wait is exactly the hold time. Above it, it has burned the whole budget, gone to sleep, and then waited out the holder anyway — and the futex_wake it needs cannot be sent until the lock is actually free, so it acquires 1.5 µs after the release rather than at it. glibc's PTHREAD_MUTEX_ADAPTIVE_NP bounds the spin for exactly this reason, and it is why a userspace spinlock is usually wrong: the holder can be descheduled mid-section, and then you spin for a whole time slice.

A semaphore is the same word with a count instead of a flag. Permits decide how many of eight workers may be inside at once:

At one permit it is a mutex, with one difference that bites: a semaphore has no owner, so any thread may post it, and a sem_post from a thread that never waited is legal. That makes it right for a bounded queue and wrong for mutual exclusion, where the ownership check is exactly what catches the double unlock.

A condition variable adds the missing piece — sleep until someone says the state changed — and the trap is that being woken says nothing about the predicate. Switch the guard between if and while, then step the sequence:

Under if, the waiter leaves cond_wait on a wakeup meant for somebody else, finds the predicate still false, and acts anyway. POSIX permits this explicitly: spurious wakeups are allowed, and pthread_cond_signal may wake more than one waiter. The while is not defensive style, it is the stated contract.

Two locks and two threads is where mutual exclusion turns on itself. Choose the order thread B takes its locks in, then step the four acquisitions:

Under one order there is never a cycle: whoever gets lock 1 finishes and releases both. Invert B and the fourth step closes the loop — each thread holds what the other needs, and neither will ever yield. Nothing detects it and nothing times out; the process simply stops. A global lock order prevents it, and it is mechanically checkable: sort by address, or give every lock a static rank.

The last lock is the one people reach for by reflex. An rwlock buys you the critical section back and charges one cache-line transfer for it: its counter is contended, and a read touches it three times where a mutex touches its own word twice:

Notice how much the critical section has to be worth. At a 500 ns section the rwlock does 3.1 M/s against the mutex's 1.4 M/s, and keeps winning up to an 80% write mix. Drop it to 100 ns and it never wins at any mix: that extra trip across the counter's line costs 100 ns — the whole section it was protecting.

compare_exchange is the general read-modify-write: publish a new value only if memory still holds the one you read. When it does not, you have not lost data — you have lost a race, and you go round again.

Raise how often another core gets there first, and compare what each attempt read against what was actually in memory when the swap executed:

Notice that the loop is not wrong when it fails — failing is the mechanism. But everything computed between the load and the swap is thrown away each time, which is why a CAS loop has to be short and free of side effects. A loop that allocates, or logs, or takes another lock does that work once per attempt.

fetch_add looks like the same thing and is not: its retry happens inside the core rather than in your loop. Pile cores onto one counter:

They do not deliver the same throughput, and one fact explains both rows. The cache line is the serial resource: it is in one core at a time, and moving it takes 100 ns. fetch_add spends one trip of it per increment, so it holds 10 M increments a second whatever the core count. The loop spends one per attempt: at eight cores seven attempts in eight are thrown away, each having paid for a trip of its own, and the same line delivers 1.3 M successful increments a second — an eighth. Prefer the instruction with the loop built in.

That line is 64 bytes wide and it does not care that your two counters are different variables. Drag core 1's counter down into core 0's line:

Because both writes now land in one line, the line ping-pongs between the cores on every increment, and a 20 ns atomic becomes a 100 ns one — 5× for two variables that never touch. This is false sharing, it is invisible in the source, and padding to a line is what alignas(64) and Java's @Contended exist for.

Lock-free code has one failure mode that no amount of atomicity prevents. Slide the other thread's pop, pop, push into the window between our read and our CAS:

Watch the CAS succeed. The pointer we compared is bit-for-bit the one we read, so the hardware has nothing to object to — but the node it names was freed and re-pushed in between, and head now points into memory the allocator has already handed out. This is ABA. The fixes are a tagged pointer — a version counter in the spare bits, bumped on every push — or a reclamation scheme such as hazard pointers or epochs.

With those in hand the price list is short. One atomic instruction buys one trip of the line, and the only thing changing below is how many cores want that line:

At one core an atomic is 20 ns against a plain load's 1 ns — twenty times the price, and still cheap. At eight cores the CAS loop is 800 ns, and its bar is cut into the eight trips it pays for, only the last of which lands. The rule that falls out: atomics are cheap per instruction and expensive per contended line, so the optimisation is to spread the line, not to remove the atomic.

A store does not go to memory. It goes into a per-core store buffer and retires immediately, which is what makes it cost 0.3 ns instead of the tens of nanoseconds a cache miss would. It also means another core sees your writes when the buffer drains, not when you issued them.

The producer writes data = 42, then flag = 1. Move when each of the two stores leaves the buffer, and read the bottom row:

Put the flag out before the data and the other core sees a set flag over stale data: a consumer that trusted the flag reads 0 and calls it 42. Nothing here is a compiler bug or a hardware bug — both stores are to unrelated addresses, and nothing in the single-threaded meaning of that code orders them.

Restraining exactly that is what memory_order is for: a release store may not be reordered ahead of the writes before it. Choose an ordering, then scrub when the consumer reads:

Under relaxed there is a window — at cycle 2 the flag is visible and the data is not. Under acquire/release there is no such window, not because the store got faster but because the compiler may no longer emit them out of order and the core may no longer drain them out of order. The bug is a window, and ordering closes it.

Ordering pairs. A release on its own guarantees nothing; the reader has to take the other end. Until both ends are in, every read the consumer makes is stale — the slider installs one half at a time:

Notice that nothing happens until both halves are in place. A release store read by a relaxed load is still a data race, and the three writes before the release stay stale. Once the acquire load reads the value that release wrote, every write the producer made before it is visible to everything the consumer does after it. That is the whole of happens-before, and it is transitive.

One reordering survives acquire/release on every machine ever built. Both cores store, then load the other's variable — step the four outcomes with the fence off, then on:

Both cores can read 0, an outcome no interleaving of the two programs produces. Each store is still sitting in its own store buffer when the other core's load goes out. Only a full fence — mfence, or the lock-prefixed store that seq_cst compiles to — drains the buffer first, and that is precisely why seq_cst costs something on x86 while acquire and release do not.

Which is the part that does not travel. Switch architecture and walk the three orderings:

x86 forbids three of the four reorderings for free, so relaxed code is accidentally almost correct and seq_cst is the only order you actually pay for — a 20 ns xchg against a 0.3 ns store. ARMv8 allows all four, so acquire/release costs ldar and stlr, and seq_cst costs nothing on top of that, because that pair is already sequentially consistent. The trap is the first column: code that has only ever run on x86 has never had its ordering tested.

At 2 ns nothing beats a single atomic, and everything else is paying for a lock around one instruction. Only by 252 ns is the rwlock ahead — later than most guess. And the mutex never has the shortest bar at all: spinning takes the lock the instant it is free and parking cannot. What it has is the inner one. At 3.2 µs the spinlock burns 3.2 µs of a whole core, seven cores over, where the adaptive mutex burns its 1 µs budget and sleeps. Latency is what you feel; the inner bar is what you pay.

int want = 0;
if (!cas(&m, &want, 1))  // 0 -> 1
    lock_slow(&m);  // futex_wait
/* ... critical section ... */
if (xchg(&m, 0) == 2)  // waiters?
    futex_wake(&m, 1);

That one word is also what caps the whole machine. Raise the core count on a workload that spends 5% of each operation inside the lock:

Notice that the curve comes back down. Past 31 cores the extra core moves the line more than it contributes: 64 cores deliver 7.8× where 31 delivered 9.0×. Amdahl only flattens; the coherency term is what makes more hardware worse.

• A cond_wait guarded by if. The loop is the contract.
• relaxed between threads. It orders nothing at all.
• Two hot counters in one struct. One line, a 5× tax.
• A spinlock in userspace. The holder can be descheduled inside it.
• Locks taken in reading order. Fix a global order first.