In an allocator guarded by one shared lock, why does allocation throughput flatten as a worker pool grows from four threads to sixty-four?

## The allocation fast path is a critical section An allocator hands blocks out of **shared bookkeeping**: a free list per size class, a bitmap of free cells, a set of spans that are partly in use. A thread that takes a block must mutate that bookkeeping, and the mutation has to be atomic with respect to every other thread doing the same thing. The simplest correct design guards all of it with **one lock**. That design is small, obviously correct, and perfectly adequate — for one thread. The work inside the lock is tiny: classify the requested size, pop a block off a list, decrement a count. Tens of nanoseconds. That smallness is exactly what makes the ceiling so hard. If the critical section takes `t`, the structure serves at most `1/t` allocations per second **in total**, regardless of how many cores run the code around it. Sixty-four threads do not get sixty-four times one thread's allocation throughput; they get `1/t`, minus the cost of the sixty-four-way queue that forms in front of it. ## What the symptom looks like from outside | Observation | What it means | |---|---| | Throughput flat as the pool doubles | arrival rate already exceeds the lock's service rate | | Processor utilization far below the core count | threads are blocked, not computing | | Time inside the allocator dominated by acquiring, not by searching | the algorithm is fine; the queue is not | | Tail latency climbing much faster than the median | classic queueing signature | | The same binary scaling cleanly at four threads | the code did not change, the contention did | The last row is the one that misleads people. Nothing about the allocation got slower per call. What changed is how many threads want the same small resource at the same instant. ## Why more threads make it worse rather than merely neutral 1. **Queueing.** Once arrivals exceed the service rate, waiting time is not bounded by the critical section; it grows with the number of waiters ahead of you. 2. **Handoff cost.** The lock word and the list head have to become visible to the next owner on every handover, and that transfer between cores costs more than the pop it protects. 3. **Park and unpark.** A blocking lock puts losers to sleep. Waking a thread costs microseconds to protect a critical section measured in nanoseconds. 4. **Convoying.** A thread descheduled while holding the lock stops every other thread until it is scheduled again, and the chance of that rises with the number of runnable threads. So the curve does not merely flatten. Past the knee it often bends **downward**: adding workers subtracts throughput. ## Proving it is the allocator - **Draw the scaling curve.** Measure the same workload at 1, 2, 4, 8, 16, 32 and 64 threads. Contention on one structure gives a curve that rises, flattens, then declines — not a straight line that stops at the core count. - **Look at where time goes, not how much.** Sampled stacks show threads parked in the allocator's acquire path rather than inside its search. A slow algorithm would show the opposite. - **Run a single-threaded control** with the same total number of allocations. If cost per allocation is flat at one thread and terrible at many, the per-call work is not the problem. - **Take the allocations away.** Re-run the hot loop against a pre-obtained buffer that is reused. If the flat line becomes a rising one, the shared allocator was the ceiling. ## What actually fixes it - **Remove the shared structure from the fast path.** Give each thread its own free lists so the common allocation touches memory nothing else can reach. This is the whole point of a per-thread allocator cache. - **Batch the sharing that remains.** The thread still needs stock from the shared arena, but it takes many blocks per visit, so the lock is met once per batch rather than once per allocation. - **Allocate less.** Reuse buffers, hoist allocations out of the inner loop, prefer one larger block to many small ones. This lever is independent of the allocator and often the cheapest. - **A faster lock is the weakest lever.** Spinning instead of parking, or a fairer queue, moves the ceiling a little and changes its shape; it does not remove a serialization point. The last point is worth internalizing, because it is the answer interviewers listen for. Contention is a **structural** problem: the resource is shared. Making the sharing cheaper is a constant-factor improvement; making it unnecessary changes the scaling.