Concurrency, Parallelism, and Systems Performance

Concurrency, parallelism, and the ceiling on both

Concurrency is a structure. It means that a program deals with several tasks whose lifetimes overlap. Parallelism is an execution property. It means that several tasks run at the same instant on different hardware. A single core runs concurrent code and no parallel code. A vectorized loop runs parallel code and no concurrent code.

Amdahl's law bounds parallel speedup. If a fraction p of the work runs in parallel and the rest runs serially, then the speedup on N processors is 1 divided by ((1 minus p) plus p over N). With p equal to 0.95 and infinite processors, the ceiling is twenty. With p equal to 0.99 the ceiling is one hundred. A 1 percent serial section caps a 1,000 core machine at 91 times speedup.

Amdahl's law is optimistic, because it assumes that coordination is free. The Universal Scalability Law, or USL, adds the missing term. Relative capacity at N workers equals N divided by (1 plus alpha times (N minus 1) plus beta times N times (N minus 1)). Alpha is the contention coefficient, which models serialization. Beta is the coherence coefficient, which models the cost of keeping workers consistent with each other.

The beta term is the one that matters, and it is quadratic. Contention alone flattens the curve. Coherence bends it back down, so that adding workers makes the system slower in absolute terms. Every engineer who added replicas to a database and then watched throughput fall knows the beta term.

  throughput
     ^
  40 |                                    ...... Amdahl, p = 0.975
     |                            .......
  30 |                     ......
     |               ......             ______ USL, alpha=.02, beta=.0001
  20 |          .....            ______/      \______
     |      ....          ______/                    \_____
  10 |   ...        _____/                                  \____
     | ..    ______/
   0 +-----------------------------------------------------------> workers
     0     8     16    24    32    40    48    56    64    72    80

  Amdahl says the curve flattens. USL says it turns over.
  Peak is at N = sqrt((1 - alpha) / beta). Here that is 99 workers.
  Fit alpha and beta from three load points and you can predict the peak.

Fit the two coefficients from measured throughput at several load levels, and the model predicts the peak before you reach it. The exercise takes an afternoon and it prevents the common failure of buying a larger machine for a workload that already passed its peak.

Memory models: what other threads see

A memory model defines which values a read can return when other threads write concurrently. The strongest model is sequential consistency, where every thread sees one global order of all operations and that order is consistent with each thread's program order. No production processor implements it, because it forbids too many optimizations.

x86-64 implements total store order, or TSO. Stores from one core reach all other cores in program order. Loads can pass earlier stores to different addresses, because the store sits in a store buffer while the load proceeds. That single reordering is the only one that x86-64 allows, which makes it a strong model.

AArch64 and RISC-V implement weak models. Loads and stores reorder freely unless a barrier forbids it. Code that works on x86-64 and fails on Arm almost always fails because it relied on TSO without saying so. The failures are rare and they appear under load, which makes them expensive to find.

The C++11 memory model, which Rust, C, and several other languages adopted, gives portable ordering through five levels.

The practical rule is short. Use acquire on the load that reads a flag, and release on the store that sets it. Every write before the release then becomes visible to every read after the acquire. Use relaxed for counters whose value nobody uses to order anything. Use seq_cst only when the algorithm needs a single global order, because it costs a full barrier on every architecture.

// Publish a fully built object to another thread, correctly.
std::atomic<Config *> g_config{nullptr};

void publish() {
    Config *c = new Config();
    c->timeout_ms = 500;                 // (1) plain write
    c->retries    = 3;                   // (2) plain write
    g_config.store(c, std::memory_order_release);   // (3) release
}

void consume() {
    Config *c = g_config.load(std::memory_order_acquire);   // (4) acquire
    if (c) {
        use(c->timeout_ms);   // sees (1): the release/acquire pair orders it
    }
}

Without the release and acquire pair, the compiler or the processor can move writes (1) and (2) after the store (3). Another thread then reads a pointer to an object whose fields hold garbage. The bug appears once in ten million runs and it is invisible in a debugger.

Atomics and what contention costs

An atomic read-modify-write operation must own the cache line exclusively. The core issues a request for ownership, every other core invalidates its copy, and the line arrives in Modified state. Then the operation runs. The cost is therefore the cost of a cache line transfer, and it scales with the distance between the cores that share the line.

An uncontended atomic increment costs about 5 to 20 nanoseconds, because the line is already in the local L1. Two threads on sibling hyperthreads cost about the same, because they share L1. Two threads on different cores of the same socket cost 40 to 100 nanoseconds. Two threads on different sockets cost 200 to 500 nanoseconds.

Two rows of Table 4.2 carry most of the design advice. The uncontended mutex costs 18 nanoseconds because pthread_mutex_lock takes an atomic compare and exchange and returns without entering the kernel. A futex, which is the Linux primitive underneath, enters the kernel only when a thread must wait. That is why "locks are slow" is wrong as a general claim. Locks are fast until they contend.

The last row is the strongest advice in the chapter. A per-CPU counter costs one nanosecond because no line ever moves between cores. Any counter that only needs to be correct when read, and not at every instant, must be per-CPU or sharded. Request counters, byte counters, and error counters all qualify. A shared atomic counter on a 64 core machine is a scalability bug that a profiler shows as time inside the increment.

The read side of a reader-writer lock has the same disease. A classic reader-writer lock increments a shared reader count, so every reader writes the same line, and readers contend with each other despite sharing no data. Read-copy-update, or RCU, fixes this by making the read side free: readers do nothing but read, and writers publish a new version and wait for existing readers to finish. The Linux kernel depends on RCU throughout, and the userspace liburcu library provides it to applications.

Locks and the failure modes that they create

A spinlock burns CPU while it waits. It wins when the critical section is shorter than a context switch, which is under about 1 microsecond. It loses badly when the lock holder gets preempted, because the waiters then spin for a full scheduler time slice while the holder does not run. Never use a spinlock in user space on a machine where the thread count exceeds the core count.

An adaptive mutex spins briefly and then sleeps. This is what pthread_mutex_t does on Linux and what std::sync::Mutex does in Rust through parking_lot style implementations. The brief spin captures the common case of a short critical section, and the sleep avoids burning a core on a long one.

Three failure modes appear in production and each one has a name.

Lock convoying happens when a thread releases a lock and immediately tries to take it again. The woken waiter has not yet run, so the releaser wins the race and the waiter sleeps again. Throughput collapses because every acquisition costs a wake-up that achieves nothing. Fix it by holding the lock for the whole batch rather than per item.

Priority inversion happens when a low priority thread holds a lock that a high priority thread needs, and a medium priority thread preempts the low priority one. The high priority thread now waits on the medium priority one. The Mars Pathfinder rover reset itself repeatedly in 1997 for exactly this reason. Priority inheritance futexes fix it by raising the holder's priority to that of the highest waiter.

Deadlock happens when two threads take two locks in opposite orders. The fix is a global lock order, and the enforcement is a tool. Run the test suite under ThreadSanitizer, which detects both data races and lock order inversions. Run it in continuous integration, because a lock order violation that happens once per million executions will reach production otherwise.

Lock-free structures and the reclamation problem

A lock-free algorithm guarantees that some thread makes progress in a bounded number of steps, whatever the others do. A wait-free algorithm guarantees that every thread makes progress. Lock-free is achievable for many structures. Wait-free usually costs more than it returns.

The classic lock-free stack, due to Treiber, is four lines.

/* Treiber stack push. Correct, and it carries the ABA problem. */
void push(_Atomic(node_t *) *head, node_t *n) {
    node_t *old = atomic_load_explicit(head, memory_order_relaxed);
    do {
        n->next = old;
    } while (!atomic_compare_exchange_weak_explicit(
                 head, &old, n,
                 memory_order_release, memory_order_relaxed));
}

The pop operation is where the difficulty lives. Thread A reads head, which points to node X, and prepares to swing head to X's successor. Thread A stalls. Thread B pops X, pops the next node, frees both, allocates a new node at X's old address, and pushes it. Thread A resumes, compares head against X, finds equality, and installs a stale successor pointer. The structure is now corrupt. This is the ABA problem, and it exists because a pointer comparison cannot tell that the value changed and came back.

Two families of solution exist. A tagged pointer packs a version counter next to the pointer and compares both with a double-width compare and exchange, so that a reused address carries a different tag. The technique works and it limits the pointer to fewer bits.

The general solution is safe memory reclamation, which answers the question "when can I free this node?". Hazard pointers have each thread publish the pointers that it currently reads, and a reclaimer frees a node only when no hazard pointer names it. Epoch based reclamation has threads enter and leave an epoch, and it frees the nodes of epoch E once every thread passed epoch E plus two. Epoch reclamation is faster and it stalls forever if one thread enters an epoch and never leaves, which is what happens when a thread blocks inside a read section.

Ring buffers avoid most of this. A single producer, single consumer ring buffer needs no atomic read-modify-write at all, only a release store and an acquire load of two indexes. The LMAX Disruptor generalized the design with padded sequence counters, batch claiming, and pre-allocated slots, and it reached tens of millions of messages per second on 2011 hardware. Any structure that fits the single producer or single consumer pattern must use a ring buffer rather than a general queue.

Async runtimes and the shape of a modern server

A thread per connection is simple and it costs memory. Each thread holds a stack, which defaults to 8 megabytes of virtual address space and commits pages as it uses them. Ten thousand threads cost real memory and, more importantly, cost the scheduler. Every wake-up runs the scheduler, and the run queue grows.

An event loop replaces threads with state machines. One thread waits on many descriptors, and each ready descriptor runs a short callback. The model removes the per-connection stack and the context switch. It introduces a new problem: any callback that blocks stops every connection on that loop.

Three answers exist, and modern runtimes use all three.

Stackless coroutines compile an async function into a state machine. Rust async and C++20 coroutines work this way. The generated state holds only the live variables across each suspension point, which is a few hundred bytes rather than a megabyte. The cost is the function coloring problem: an async function can only be called from another async function, so the property spreads through the call graph.

Stackful coroutines give each task a small, growable stack. Go goroutines start at 8 kilobytes and grow by copying. Java virtual threads, which reached general availability in JDK 21, mount a task onto a carrier thread and unmount it when the task blocks. Both hide the async property, so ordinary blocking code runs concurrently with no color.

Work stealing distributes tasks across cores. Each worker has its own double ended queue. A worker pushes and pops at one end, which needs no synchronization in the common case. An idle worker steals from the other end of another worker's queue. The design keeps locality for the common case and balances load automatically.

  THREAD PER CONNECTION          EVENT LOOP + CALLBACKS
  +---------+  8 MiB stack       +-------------------------+
  | thread  |---> conn 1         | one thread              |
  +---------+                    |  epoll_wait -> ready set|
  +---------+                    |  run callback per fd    |
  | thread  |---> conn 2         +-------------------------+
  +---------+                    state: heap objects, few hundred bytes
  10k conns = 10k threads        10k conns = 1 thread
  kernel schedules everything    any blocking call stops all

  STACKFUL COROUTINES (Go, Java virtual threads)
  +-----------------------------------------------+
  |  M OS threads  x  N tasks,  work-stealing      |
  |  task stack: 8 KiB, grows by copying           |
  |  blocking call unmounts the task, not the CPU  |
  +-----------------------------------------------+
  10k conns = 10k tasks on 16 OS threads

Queueing theory, and why the tail is what matters

Little's law states that the average number of items in a system equals the arrival rate times the average time in the system. Written as L equals lambda times W, it holds for any stable system with no assumptions about the arrival distribution. It is the most useful formula in performance engineering.

Use it in three directions. Take a target of 10,000 requests per second and a measured 20 millisecond latency. The system then holds 200 requests at any instant, so the connection pool and the thread pool must both exceed 200. Given a pool of 50 connections and a 20 millisecond latency, throughput caps at 2,500 requests per second whatever the hardware does. Given a queue depth of 200 and a service rate of 10,000 per second, the wait is 20 milliseconds.

Utilization drives latency non-linearly. For a simple queue, the average wait is the service time times rho divided by one minus rho, where rho is utilization. At 50 percent utilization the wait equals the service time. At 90 percent it is nine times. At 99 percent it is ninety-nine times. Latency does not degrade gracefully near saturation, it explodes.

The table is the reason that capacity planning targets 60 to 70 percent utilization rather than 95. The last 30 percent of capacity costs a factor of ten in latency, and no code change recovers it.

Tail latency amplifies across a fan-out. A request that queries one hundred services in parallel finishes when the slowest one finishes. If each service has a p99 of 100 milliseconds, the probability that all one hundred respond faster than that is 0.99 to the power 100, which is 0.366. So 63 percent of user requests hit at least one p99 response. The user-visible p50 equals the backend p99.

Three techniques cut the tail. Hedged requests send a second copy of the request after the p95 deadline passes and take the first answer, which costs 5 percent more load and removes most of the tail. Tied requests send to two replicas and let each cancel the other once one starts. Request reissue with a budget caps the extra load. Chapter 11 puts these in a service mesh and Chapter 16 puts numbers on them.

The GPU execution model

A GPU is a throughput machine. It runs thousands of threads and hides memory latency by switching between them rather than by caching. The programming model is single instruction multiple threads, or SIMT.

Threads group into warps of 32 on NVIDIA hardware and wavefronts of 32 or 64 on AMD. A warp executes one instruction for all 32 lanes at once. When the lanes take different branches, the hardware runs both paths and masks the inactive lanes. That is warp divergence, and a fully divergent branch inside a warp costs a factor of 32.

Streaming multiprocessors, or SMs, hold the warps. Occupancy is the ratio of resident warps to the hardware maximum, and it is what hides memory latency. A kernel that uses too many registers per thread or too much shared memory per block limits the resident warps and loses the latency hiding. Aim for enough occupancy to cover the memory latency and no more, because past that point more registers per thread help more than more warps.

Memory coalescing decides the bandwidth. When the 32 lanes of a warp read 32 consecutive 4 byte words, the hardware issues one 128 byte transaction. When they read 32 scattered words, it issues up to 32 transactions and delivers 4 useful bytes out of every 32 byte sector. The bandwidth difference is a factor of eight or more, and it is the same array-of-structures problem that Chapter 1 described for the CPU.

The gap between NVLink at 1.8 terabytes per second and PCIe at 64 gigabytes per second is a factor of 28, and it decides how a large model splits across devices. Chapter 13 works through that decision for tensor parallelism and pipeline parallelism.

Synchronization on a GPU differs from a CPU. Threads in a block synchronize with a barrier that costs tens of cycles. Blocks do not synchronize with each other inside a kernel launch, which is why a reduction over a large array uses two kernel launches or a cooperative groups grid barrier. Atomics on global memory work and they serialize, so a histogram that has every thread increment a global bin runs at the speed of one bin. The fix is a per-block histogram in shared memory followed by one global merge.

Sources and further reading

Neil Gunther, "Guerrilla Capacity Planning", for the Universal Scalability Law and for fitting it. Paul McKenney, "Is Parallel Programming Hard, And, If So, What Can You Do About It?", which is free and is the best treatment of memory ordering and RCU. Maurice Herlihy and Nir Shavit, "The Art of Multiprocessor Programming", second edition, for lock-free structures and their proofs. Jeff Dean and Luiz Barroso, "The Tail at Scale", Communications of the ACM, 2013, for hedged requests. The NVIDIA CUDA C++ Programming Guide for the SIMT model.