Contention Ceilings and the Limits of Parallel Scaling

A service that scales linearly from two workers to four and then flattens at eight has not run out of CPU. It has run into a serialization point: a mutex, an atomic counter, a connection pool lock, a log append, or a cache line that every worker writes. The ceiling is set by the cost of the serialized section times the rate at which workers must enter it, and no amount of additional parallelism moves it. Adding workers past that point makes throughput slightly worse and latency noticeably worse, since each worker spends more time waiting for the section and the queue in front of it grows.

The distinction between a capacity limit and a contention limit is diagnostic. At a capacity limit, adding workers raises throughput proportionally until the bottleneck resource saturates, and utilization of that resource is high. At a contention limit, throughput is flat while CPU utilization may be low, because workers are blocked rather than busy, and the blocked time is spent in the scheduler or spinning. A profile that shows workers in a lock acquisition path rather than in application code is the signature.

Amdahl’s bound and its measurement

The serial-fraction argument is straightforward. If a fraction s of the work must be done serially, the speedup from p workers is at most 1/(s + (1−s)/p). At s = 0.05, the maximum speedup is 20 no matter how many workers are added; at p = 16 the speedup is 1/(0.05 + 0.95/16) ≈ 9.1, under half the bound. The bound is a property of the algorithm, not of the machine, and it applies to any resource that must be entered exclusively.

The formula’s practical use is as a fitting tool rather than a prediction. Measure throughput at several worker counts, fit the curve, and read off the implied serial fraction. A fitted s that is much larger than the code’s visible critical sections suggests the serialization is not in the code the author wrote: it is in a shared library, an allocator, a kernel path, or a cache coherence protocol.

That last possibility is the one most often missed. A critical section of a few instructions can still serialize heavily if it touches a cache line that other cores are writing, because the line must be transferred between caches for each access. On a machine with dozens of cores, a contended cache line can cost hundreds of cycles per access, which turns a nominally cheap atomic increment into a bottleneck comparable to a lock. The serialization is in the coherence protocol rather than in the program’s logic.

False sharing and the shape of the counter

The canonical example is a set of per-thread counters laid out adjacently in memory. Each thread increments its own counter, which requires no synchronization at the language level, yet all the counters occupy the same cache line. Every increment invalidates the line in the other cores’ caches, so the line ping-pongs and each increment pays a coherence miss. The counters are logically independent and physically shared.

The remedy is padding: place each counter on its own cache line, typically 64 bytes on the common architectures, so that no two counters share one. The cost is memory, since a padded array of a thousand counters occupies 64 kilobytes rather than 8, and the benefit is that the increments stop interfering. The padding must be explicit, since compilers and languages do not generally insert it, and the alignment must be enforced rather than assumed.

#include <stdalign.h>

struct padded_counter {
    alignas(64) _Atomic unsigned long value;   // one cache line per counter
    char pad[64 - sizeof(_Atomic unsigned long)];
};

static struct padded_counter counters[MAX_THREADS];

static inline void bump(int tid) {
    atomic_fetch_add_explicit(&counters[tid].value, 1, memory_order_relaxed);
}

The memory_order_relaxed matters as much as the padding. A counter whose value is only read for reporting needs no ordering with respect to other memory operations, and requiring sequential consistency on every increment makes each one a full barrier, which serializes the pipeline as well as the cache line. Relaxed atomics still cost a coherence transaction when contended, but they avoid the additional ordering cost.

A shared counter that must be exact is worse than a padded one. The single atomic increment is a serialization point at the hardware level: all cores must obtain exclusive ownership of the line in turn. The usual design avoids exactness at the hot path by giving each thread or each shard a local counter and summing on read, accepting that the reported total is slightly stale or that a read must gather from every shard. The trade is between exactness and scalability, and it is unavoidable for any single-word counter.

Lock granularity and the convoy

A lock’s cost has two parts: the critical section’s execution time and the handoff cost when ownership changes. The handoff is the larger part under contention, because the new owner’s cache does not hold the line, and because the scheduler may have descheduled it. A lock held for a few instructions can still be a bottleneck if it is acquired often enough.

Increasing lock granularity, sharding a map into sixteen independently locked sub-maps or a pool into per-CPU segments, reduces contention on each lock but adds a lookup cost to find the right one and creates a new problem: imbalance. If the shard function is not uniform, one shard’s lock becomes the bottleneck while the others are uncontended. The uniformity of the shard function is therefore part of the design, and a hash that is uniform in the key space can still be skewed in the access distribution.

The alternative to finer locks is no locks, through immutable data structures, per-thread state merged on read, or message passing to an owner thread. Each removes the contention by removing the sharing, and each has its own cost: immutability costs copying, per-thread state costs memory and a merge step, and message passing costs a queue and a context switch. The choice is between paying for coordination and paying for duplication, and there is no third option.

The convoy effect described in head-of-line blocking in a shared worker pool is the queueing manifestation of the same underlying serialization: a thread that holds a lock and is descheduled makes every waiter pay its scheduling delay, and the waiters’ arrival rate at the lock grows as they accumulate.

When the ceiling is in the kernel

Some ceilings are not in the application’s locks at all. A service that accepts connections pays a kernel cost per connection: allocating a socket, inserting it into tables, and waking a thread. A service that reads from many sockets pays a cost per readiness event. These costs are serialized to a degree by kernel locks on the socket tables and by the per-CPU run queues, and they scale differently from application work.

The standard architectural response is to reduce the number of kernel crossings per unit of work: accept on many connections and hand them to workers (the accept-and-dispatch pattern), use readiness notification rather than one thread per connection, and batch reads and writes so that one syscall carries several operations. Each of these reduces the rate at which workers enter the serialized kernel path, which is exactly the quantity the contention bound depends on. The mechanism is the same as batching’s amortization of fixed cost, described in batching and the amortization of per-request cost, applied to the syscall boundary rather than to a device.

A second kernel-level ceiling is memory allocation. A general-purpose allocator maintains per-size-class free lists and, for large allocations, a global structure. Under many threads allocating and freeing small objects, the allocator’s central structures become contended even when the per-thread caches absorb most operations, because cross-thread frees must return memory to the owning arena. The consequence is that allocation-heavy request handlers scale worse than their visible work suggests. Reusing buffers, pooling objects, and preferring arena allocation per request all reduce the rate of entry into the allocator.

Measuring the ceiling rather than guessing it

The measurement that distinguishes contention from capacity is a scaling curve with a controlled variable. Hold the workload fixed, vary the worker count, and record both throughput and the time workers spend blocked. Throughput that flattens while blocked time rises is contention. Throughput that rises and then falls while CPU is saturated is capacity plus overhead, such as cache thrashing or scheduler migration.

Two further measurements localize the cause. Sampling profiles taken at high worker counts show where cycles are spent; a profile dominated by futex or spin paths indicates a lock, while one dominated by coherence stalls indicates a shared line. Per-worker throughput distribution shows whether all workers are slowed equally or a few are; equal slowing points to a shared serialization, unequal slowing to a partitioning problem where some workers have more work or worse affinity.

The scaling curve is also the place where the difference between throughput and latency becomes visible. A system at its contention ceiling may have flat throughput and a latency that grows linearly with worker count, because the extra workers are queueing for the serialized section rather than serving requests. That combination of flat throughput and rising latency is the clearest evidence that additional concurrency is harmful, and it is the condition under which the correct action is to reduce the worker count.

Designing below the ceiling

The design question is not how to raise the ceiling but how to make the workload’s serial fraction small enough that the ceiling is beyond the required throughput. Three levers recur.

Reduce the frequency of entry. Batch operations so that one entry into the serialized section covers many units of work. This is the same amortization argument as batching, and it applies to locks, syscalls, and atomics alike.

Reduce the duration of entry. Make the critical section do less: move I/O out of it, precompute what can be precomputed, and avoid allocation inside it. The duration multiplies the entry rate to give the serialized time per second, and both factors are levers.

Remove the sharing. Partition the state so that each worker touches its own copy, and merge only when a consistent view is needed. This converts a serialized resource into a replicated one, at the cost of memory and of a merge step whose own cost must be counted.

A design that applies all three typically finds that the ceiling moves far enough that the next constraint is a genuine capacity limit: a device, a network link, or a downstream service. That is the desired outcome: capacity limits are raised by buying more of the resource, while contention limits are raised only by redesign, and redesign is the more expensive currency.