How does a per-thread allocator cache make the common allocation path run with no synchronization at all?

middlemust knowfreq 54%

answer

private stock, one owner
one free list per size class
no second party, so no race
pop the head, decrement the count
synchronization only at refill and flush

basics

~20 s

A per-thread allocator cache gives each thread its own free list per size class. Allocation pops that private list's head, and since no other thread can reach it, the pop needs no lock — only refill and flush synchronize.

solid answer

~50 s

The cache is a small array of free lists, one per size class, owned by exactly one thread. Allocating means mapping the requested size to a class, looking at that thread's list for the class, and popping the head: three or four loads and stores against memory no other thread may touch. That single-owner invariant is what removes the synchronization. A lock-free pop normally gets its correctness from an atomic read-modify-write; here there is no second party to race with, so plain loads and stores suffice. Synchronization returns only at the edges — refilling the list from the shared arena when it empties, flushing it back when it grows too large, and accepting a block freed by a different thread. In steady state those edges are rare, so the path that runs millions of times per second is genuinely uncontended.

The cache is a small array of free lists, one per size class, owned by exactly one thread. Allocating means mapping the requested size to a class, looking at that thread's list for the class, and popping the head: three or four loads and stores against memory no other thread may touch. That **single-owner invariant** is what removes the synchronization. A lock-free pop normally gets its correctness from an atomic read-modify-write; here there is no second party to race with, so plain loads and stores suffice. Synchronization returns only at the edges — refilling the list from the shared arena when it empties, flushing it back when it grows too large, and accepting a block freed by a different thread. In steady state those edges are rare, so the path that runs millions of times per second is genuinely uncontended.

code

pseudocode · 13 lines

pseudocode

allocate(size):
    c = size_class(size)
    list = my_thread_cache.lists[c]

    if list.head == null:
        refill(my_thread_cache, c)   // takes the shared arena lock
        if list.head == null:
            return out_of_memory

    block = list.head
    list.head = block.next
    my_thread_cache.counts[c] = my_thread_cache.counts[c] - 1
    return block

go deeper

for a junior

Recall the shape: each thread keeps a small private supply of free blocks grouped by size, and taking one from your own supply needs no coordination with anyone.

for a middle

Explain why no lock is needed: a lock protects against another party interleaving, and a private list has no other party. Then name the edges where coordination returns — refill, flush, cross-thread free.

for a senior

Be ready to say when the cache underdelivers: workloads dominated by outsized allocations, or by frees arriving on other threads, spend their time on the edges rather than the fast path.

for a principal

Treat it as trading contention for footprint. Private stock is memory no other thread can use, so the design question is how much unavailable memory a scalable allocation path is worth on your fleet.

What a per-thread allocator cache holds

A per-thread cache is not a copy of the heap. It is a small amount of stock: for each size class the allocator supports, a short singly linked list of free blocks of that class, threaded through the free blocks themselves so the list costs no extra memory, plus a count of how many are on it.

thread_cache:
  lists[0..K]      // one free list per size class
  counts[0..K]     // how many blocks each list holds
  high_water[0..K] // when to flush back to the shared arena

The cache is reachable only through a per-thread slot, so a thread never has to ask which cache is its own; it is handed the pointer. Nothing in the structure is shared, which is precisely the property the fast path exploits.

The fast path, step by step

Classify. Round the requested size up to a size class. This is arithmetic or a small table lookup on a value already in a register.
Select. Index this thread's list array by the class.
Test. If the list head is null, take the slow path (refill) instead.
Pop. Read the head block, store its next pointer into the head, decrement the count.
Return the block's address.

That is it. No lock acquisition, no atomic read-modify-write, no memory fence, no retry loop. The number of instructions is small enough that the cost is dominated by whether the list head is still in cache.

Why the single-owner invariant removes the lock

Synchronization exists to make an operation appear indivisible to other parties. A list pop is three dependent steps — read head, read next, write head — and if a second thread could pop between them, both would receive the same block. That is the only reason the shared version needs a lock.

When the list is private, the second thread does not exist. Interleaving with a different thread is impossible by construction, so plain loads and stores are already indivisible enough. Being preempted mid-pop is harmless: when the thread resumes, its own list is exactly as it left it.

The invariant to hold onto: a lock is required by sharing, not by mutation. Remove the sharing and the lock has nothing left to protect.

Where synchronization comes back

Edge	What it costs	How often
Refill: the list is empty	one shared-arena lock acquisition, a batch moved	once per batch of allocations
Flush: the list exceeds its high-water mark	one shared-arena lock acquisition, a batch returned	once per batch of frees
A block freed by a different thread	one atomic push onto the owning cache's remote list	once per cross-thread free
A request larger than the biggest size class	straight to the shared arena, every time	every such allocation

This table is the honest answer to the question. The fast path is unsynchronized; the allocator is not. If a workload hits the edges constantly — allocating sizes with no size class, or living entirely on cross-thread frees — the cache buys much less than the headline suggests.

What the cache does not do

It does not reduce memory used. It moves free blocks from a shared pool into private ones. Blocks parked in a thread's list are not available to any other thread until they are flushed back.
It does not help very large allocations. Those bypass size classes and go to the shared arena directly, where the lock is back and the allocation is expensive anyway.
It does not fix a high allocation rate. It makes each allocation cheap and parallel, but the total work of classifying, popping, touching and eventually reclaiming still grows with the rate.
It does not make frees free. A local free is the mirror of the fast path — push the block onto the private list — but a free from another thread is materially more expensive.

A good mental summary: a per-thread allocator cache converts a contention problem into a footprint problem. The private stock is memory the program is not using and other threads cannot have, and that is the price paid for an allocation path that scales linearly with cores.

## What a per-thread allocator cache holds A per-thread cache is not a copy of the heap. It is a **small amount of stock**: for each size class the allocator supports, a short singly linked list of free blocks of that class, threaded through the free blocks themselves so the list costs no extra memory, plus a count of how many are on it. ``` thread_cache: lists[0..K] // one free list per size class counts[0..K] // how many blocks each list holds high_water[0..K] // when to flush back to the shared arena ``` The cache is reachable only through a per-thread slot, so a thread never has to ask which cache is its own; it is handed the pointer. Nothing in the structure is shared, which is precisely the property the fast path exploits. ## The fast path, step by step 1. **Classify.** Round the requested size up to a size class. This is arithmetic or a small table lookup on a value already in a register. 2. **Select.** Index this thread's list array by the class. 3. **Test.** If the list head is null, take the slow path (refill) instead. 4. **Pop.** Read the head block, store its `next` pointer into the head, decrement the count. 5. **Return** the block's address. That is it. No lock acquisition, no atomic read-modify-write, no memory fence, no retry loop. The number of instructions is small enough that the cost is dominated by whether the list head is still in cache. ## Why the single-owner invariant removes the lock Synchronization exists to make an operation appear indivisible **to other parties**. A list pop is three dependent steps — read head, read `next`, write head — and if a second thread could pop between them, both would receive the same block. That is the only reason the shared version needs a lock. When the list is private, the second thread does not exist. Interleaving with a different thread is impossible by construction, so plain loads and stores are already indivisible enough. Being preempted mid-pop is harmless: when the thread resumes, its own list is exactly as it left it. The invariant to hold onto: **a lock is required by sharing, not by mutation.** Remove the sharing and the lock has nothing left to protect. ## Where synchronization comes back | Edge | What it costs | How often | |---|---|---| | Refill: the list is empty | one shared-arena lock acquisition, a batch moved | once per batch of allocations | | Flush: the list exceeds its high-water mark | one shared-arena lock acquisition, a batch returned | once per batch of frees | | A block freed by a different thread | one atomic push onto the owning cache's remote list | once per cross-thread free | | A request larger than the biggest size class | straight to the shared arena, every time | every such allocation | This table is the honest answer to the question. The fast path is unsynchronized; the **allocator** is not. If a workload hits the edges constantly — allocating sizes with no size class, or living entirely on cross-thread frees — the cache buys much less than the headline suggests. ## What the cache does not do - **It does not reduce memory used.** It moves free blocks from a shared pool into private ones. Blocks parked in a thread's list are not available to any other thread until they are flushed back. - **It does not help very large allocations.** Those bypass size classes and go to the shared arena directly, where the lock is back and the allocation is expensive anyway. - **It does not fix a high allocation rate.** It makes each allocation cheap and parallel, but the total work of classifying, popping, touching and eventually reclaiming still grows with the rate. - **It does not make frees free.** A local free is the mirror of the fast path — push the block onto the private list — but a free from another thread is materially more expensive. A good mental summary: a per-thread allocator cache converts a **contention problem into a footprint problem**. The private stock is memory the program is not using and other threads cannot have, and that is the price paid for an allocation path that scales linearly with cores.

If the pop is not atomic, what happens when the thread is preempted between reading the head and writing it back?
Nothing. Preemption is not concurrency on this data: no other thread can touch a private list, so the half-done pop is simply resumed with the same values. That is why the single-owner invariant, not atomicity, is doing the work here — and why breaking the invariant, for example by migrating caches between threads, is a correctness bug rather than a slowdown.
What does the allocator have to store so a free knows which size class and which cache a block belongs to?
Out-of-band metadata keyed by address. Blocks are carved from larger, aligned runs, and a lookup from the block address to its run — by masking the address, or through a small index of runs — yields the size class and the owning cache. Keeping that metadata out of the block avoids a per-block header for small classes.
Does a per-thread cache remove the need for a shared arena?
No. The arena is where blocks come from and where they return, so every cache is a temporary loan against it. The cache changes how often the arena is touched, not whether it exists, and memory must be able to flow back so that one thread's surplus can become another's supply.

Each cashier keeps a float of change in their own drawer. Making change is instant because nobody else can reach that drawer; only when the float runs low, or overflows, does the cashier queue at the vault where everyone must take a turn.

saying these in an interview costs you the question

Believes a per-thread cache means the shared arena is never touched again
Thinks the private pop still needs an atomic compare-and-swap to be correct
Assumes the cache reduces total memory rather than reserving it per thread
Expects large allocations to benefit from the same private fast path
Says freeing is always as cheap as allocating regardless of which thread frees

How does a per-thread allocator cache make the common allocation path run with no synchronization at all?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What a per-thread allocator cache holds

The fast path, step by step

Why the single-owner invariant removes the lock

Where synchronization comes back

What the cache does not do

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

What a per-thread allocator cache holds

The fast path, step by step

Why the single-owner invariant removes the lock

Where synchronization comes back

What the cache does not do

answer

go deeper