Thread-Local Caches and the Cost of a Remote Free

The serialised allocator is a victim of its own success. A single lock-protected heap is correct and simple, and on a single core it is fast. On a machine with dozens of cores, the lock’s cache line is transferred between cores on every operation, and the transfer latency, on the order of a hundred cycles for a line that is dirty in another core’s cache, dominates the handful of instructions the critical section actually contains. Throughput stops scaling and then declines. The standard remedy is to give each thread its own allocation state so that the common path touches no shared line.

What a thread cache holds

A thread cache is a set of free lists, one per size class, private to a thread. Allocation pops from the class list; freeing pushes. No lock, no atomic operation, no shared cache line. The lists are bounded: each class holds at most some number of objects, and beyond that the thread must hand objects back to a shared structure. The bound is the whole design. An unbounded thread cache would be a memory leak proportional to the peak allocation of each thread, retained forever after the peak passes.

The bound is usually expressed in bytes per thread rather than objects per class, because the goal is to cap retention. A budget of a few hundred kilobytes per thread is typical: small enough that hundreds of threads do not hold tens of megabytes idle, large enough that the shared path is taken rarely. Because the classes differ in size, the per-class limit is derived by dividing the budget among classes or by giving each class a limit proportional to its object size.

The shared structure behind the caches is a central free list per class, itself organised in pages with occupancy metadata, and it is where the slab design reappears. Each central list owns spans of pages carved into objects of one class; a span is on the central list when it has free objects, and is returned to the page allocator when it empties. The thread cache is a buffer in front of that, and refilling it means taking a batch of objects from a span rather than one at a time, so the central lock is taken once per batch.

The remote free problem

The assumption that fails is that a thread frees what it allocated. In any program with ownership transfer: a producer allocating messages that a consumer frees, a pool of worker threads taking tasks from a queue, a garbage collector freeing objects on behalf of mutators. In each case the freeing thread differs from the allocating thread. The pointer carries no ownership tag, so the allocator must determine which thread cache owns the object.

The standard answer is to derive ownership from the address. Since objects live in spans, and spans belong to a central list, the allocator can map a pointer to its span by rounding down to the page boundary and looking up the page’s metadata. From the span it can find the owning thread cache. Two paths follow:

• Push into the owner’s cache. Requires synchronising with the owner, since the owner’s list is not designed for concurrent modification. This is where a lock or an atomic stack per class appears, and where the fast path of the freeing thread becomes a slow path.
• Push into a queue the owner drains. A per-thread mailbox of remote frees, appended to with an atomic exchange or a lock-free stack, drained by the owner the next time its cache is refilled. The freeing thread does bounded work and never touches the owner’s hot list.

The mailbox design keeps the free path uniform and bounded, at the cost of delay: the object is not available for reuse until the owner drains the mailbox, which may be much later, or never if the owner exits. A thread that receives remote frees faster than it allocates accumulates a backlog that counts against its memory but is not in its cache. Allocators that use mailboxes typically drain them on refill, on cache flush, and at thread exit, and cap the mailbox depth so a burst cannot grow it without bound.

There is a correctness trap in address-based ownership: a pointer that does not belong to the allocator at all, one obtained from mmap, from a static array, or from a different allocator, must be rejected rather than looked up. Page metadata lookup is only valid for pages the allocator manages, so the allocator must have a way to answer “is this address mine” before it dereferences any metadata. Freeing a foreign pointer is undefined behaviour in C, but allocators that crash rather than corrupt are preferable, and the check is cheap when the allocator’s regions are known ranges.

Rebalancing and the stranding problem

Per-thread caches convert a contention problem into a distribution problem. Threads do not allocate uniformly: one thread may allocate most of the memory and then go idle, holding its cache while other threads refill from the central list and grow the heap. The result is a process whose resident size reflects the sum of per-thread caches plus the central free lists, not the live set.

The classic response, from the Hoard design, is to bound the global free space as well as the per-thread space, and to move memory between heaps when the imbalance exceeds a threshold. Hoard’s structure is a set of per-processor heaps plus a global heap; a heap that exceeds its share of the total free space returns spans to the global heap, from which a heap that is short can take them. The threshold is expressed as a fraction of the total heap size, so the amount of stranded memory is proportional to the live set rather than to the number of threads.

Practical user-space allocators approximate this with periodic rebalancing: a scavenger that runs when a thread’s cache is flushed, or when the total free bytes exceed a target, and that returns objects from over-full caches to the central lists. The trigger conditions matter more than the mechanism, because a scavenger that runs too eagerly turns the fast path into a slow path, and one that runs too rarely lets footprint grow.

Thread exit is the case that must be handled explicitly. When a thread terminates, its cache is unreachable, so the objects it holds are lost unless something releases them. Allocators register a destructor that flushes the cache into the central lists. A thread that exits without running destructors, for example one terminated asynchronously, leaves its cache stranded until the process ends, and in a thread-per-request server that recycles threads this is a slow leak.

Measuring the trade

The contention removed by thread caches is measurable in a straightforward way: the allocator’s scaling curve. A lock-based allocator’s throughput flattens as cores are added, because the critical section serialises; a thread-cached allocator’s throughput rises roughly linearly until memory bandwidth or cache capacity becomes the limit. The interesting question is where the second limit bites, and it depends on the size class: small objects are dominated by the cache line transfers that thread caches eliminate, while large objects are dominated by page faults and page zeroing, which no amount of per-thread state avoids.

The costs are equally concrete:

• Footprint. Per-thread budgets multiply by thread count. A thousand threads with 256 KiB each reserve a quarter of a gigabyte before any live object is counted.
• Delay. Objects freed remotely are unavailable until the owner drains, so a pattern that frees on one thread and allocates on another sees a working set larger than the live set.
• Complexity. Ownership, mailboxes, scavenging, and thread-exit hooks are four separate mechanisms, each with its own failure mode, and the interactions are where bugs live.

A degenerate case deserves mention: a program that allocates on many threads and frees on one, a common shape for a queue with a single consumer, makes the consumer the bottleneck, because every free crosses into a mailbox it must drain. The allocator can do little about this beyond making the drain cheap; the structural fix is at the application level, transferring ownership in batches so that the allocator sees a bulk operation rather than a stream of individual remote frees.

Where the cache boundary sits

Thread caches sit between two other mechanisms and inherit constraints from both. Below them, the central lists and spans are a slab cache and inherit its release policy: a span returns to the page allocator only when empty, so the central lists hold the high-water mark of each class. Above them, the application’s own pools and arenas, bump-allocated regions in particular, bypass the thread cache entirely, which is a large part of why they remain faster than any general allocator: they remove the class lookup, the refill path, and the ownership question at once.

The address arithmetic that makes remote frees possible is the same arithmetic that makes large allocations awkward. A pointer that was aligned to a boundary greater than the allocator’s page size no longer maps back to a span by simple rounding, so the allocator must record the original base somewhere the free path can find it, in the page metadata or in a slot ahead of the payload, instead of relying on a fixed negative offset. An allocator that serves such a request from a dedicated mapping and keeps no such record cannot free it.