skip to content

One thread allocates buffers that a different thread frees — what does that pattern do to per-thread allocator caches?

level: seniorimportance: should knowfreq 44%

answer

  1. who frees is not who allocated
  2. stock drifts producer to consumer
  3. address masks down to its run
  4. remote free list drained in batches
  5. caches suit thread-local lifetimes

basics

~20 s

A free arriving on a thread that did not allocate the block breaks the one-owner assumption: blocks migrate from producers to consumers, draining one cache while inflating another, and the shared arena is back in the loop.

solid answer

~50 s

Per-thread caches assume the thread that takes a block is the thread that returns it. A producer/consumer split breaks that assumption in a specific direction. If the freeing thread pushes the block onto its own list, memory drifts one way: the producer's cache is chronically empty and keeps refilling from the shared arena, while the consumer's keeps growing until it flushes. Allocators handle this in one of two ways. Either the block becomes ordinary stock for the freeing thread and the drift is bounded by flushing at a high-water mark, or the allocator reads the block's out-of-band metadata to find the **owning** cache and pushes it onto that cache's remote free list with an atomic operation, letting the owner drain it in a batch later. Either way, a cross-thread free costs more than a local one, and a pipeline built entirely on them spends its time on that path.

code

pseudocode · 11 lines
pseudocode
free(block):
    run = run_of(block)            // mask address down to aligned run
    c   = run.size_class

    if run.owning_cache == my_thread_cache:
        push(my_thread_cache.lists[c], block)
        my_thread_cache.counts[c] = my_thread_cache.counts[c] + 1
        if my_thread_cache.counts[c] > high_water[c]:
            flush_batch(my_thread_cache, c)   // takes the shared arena lock
    else:
        atomic_push(run.owning_cache.remote_free[c], block)

go deeper

for a junior

Remember the assumption the design rests on: memory is usually returned by the thread that took it. When a program hands buffers between threads for release, that assumption stops holding.

for a middle

Explain the drift concretely: the allocating thread's list stays empty and keeps refilling, the freeing thread's list keeps growing until it flushes, and the shared arena is back in the loop.

for a senior

Show the diagnosis and the fix: allocator time concentrated in the free path, cached free memory scaling with consumer threads, and a redesign that keeps buffer lifetimes on one thread before any tuning is attempted.

for a principal

Judge whether the architecture should cross threads at all. Handing ownership across stages is a design choice with an allocator bill attached, and pooling buffers at the pipeline level may be worth more than any allocator tuning.

## A free is not the mirror image of an allocation The fast path works because the list is private. An allocation always happens on the thread that wants the memory, so it always finds its own cache. A **free** carries no such guarantee: the block arrives wherever the program happens to be when the last user is done with it. A pipeline — one stage produces buffers, another consumes and releases them — produces a steady stream of frees on a thread that never allocated anything. That asymmetry is the whole subject. The allocator has exactly two things it can do with such a block, and both cost something the local path does not. ## What drift looks like Suppose an ingest stage allocates one-kilobyte buffers at a high rate and hands each to a decode stage that releases it. If every thread simply keeps what it frees: - The producer's list for that size class is **always empty**, because it never frees that class. Every allocation takes the slow path and refills from the shared arena under the lock. - The consumer's list for that class **only grows**, because it never allocates that class. It fills to its high-water mark and then flushes batches back. - Net effect: memory circulates producer -> consumer -> shared arena -> producer, and the shared lock is met twice per batch rather than not at all. So the naive design does not corrupt anything; it quietly **reintroduces the contention the cache existed to remove**, and it holds a pile of free memory in the consumer's cache that the producer cannot see. With many producers and many consumers the held memory multiplies by the number of caches involved. ## The two strategies | Strategy | Mechanism | Cost | Failure mode | |---|---|---|---| | Keep it locally | The freeing thread pushes the block onto its own list for that class | One non-atomic push, same as a local free | Drift: stock accumulates on consumers, producers keep refilling from the shared arena | | Return to owner | Look up the block's owning cache and push it onto that cache's remote free list atomically | One atomic operation, plus the owner's later drain | Remote lists grow if the owning thread is idle or has exited | Real allocators mix them: a small number of remote frees may be kept locally, with a threshold above which blocks are returned to the owner, and an explicit path for a thread that exits while other threads still hold its blocks. ## The metadata that makes ownership knowable To return a block to its owner, `free` must answer two questions from a bare address: which size class, and which cache. Small blocks cannot afford a per-block header for that, so the allocator carves blocks out of larger **aligned runs** and keeps the answer per run: 1. Mask the block address down to the start of its run — one bitwise operation, because the run is aligned to its own size. 2. Read the run's descriptor: size class, and the identity of the cache that currently owns the run. 3. Compare with the freeing thread's own cache to choose the local or the remote path. This is also why ownership is usually tracked per run rather than per block: it makes the check a couple of instructions, and it means a whole run can be handed over at once. ## Symptoms and what to do about them - **The tell in a profile:** the free path, not the allocate path, dominates allocator time, with atomic operations or a lock visible inside it. - **The tell in memory:** total free-but-cached memory climbs with the number of consumer threads while the live set is flat. - **The structural fix:** stop crossing threads. Where the pipeline allows it, have the stage that allocates a buffer also release it, or hand ownership back explicitly, or reuse a pool of buffers whose lifetime is the pipeline rather than the message. - **The tuning fix:** where the crossing is inherent, the levers are the flush threshold and the batch size, which bound how far the drift can go before memory returns to the shared arena. The mental model to carry into an interview: a per-thread cache is an optimization for **thread-local lifetimes**. The more a program's object lifetimes cross threads, the more the design degrades toward the shared allocator it replaced — plus bookkeeping.

  • What happens to blocks on a thread's remote free list if that thread exits?
    The cache cannot simply vanish, or those blocks leak. Allocators retire an exiting thread's cache by flushing its lists to the shared arena and either keeping the cache alive as an orphan that is drained periodically, or reassigning its runs so a later free finds a valid owner. This is a classic source of leaks in short-lived-thread workloads.
  • Why is a remote free usually implemented as an atomic push onto a list rather than by taking the owner's lock?
    Because the owner must never be slowed by other threads' frees. An atomic push onto a singly linked list is one read-modify-write by the freeing thread and costs the owner nothing until it drains, and the drain can detach the whole list in a single atomic exchange and then process it privately.
  • Does batching help a cross-thread free the way it helps a refill?
    Yes, and allocators do it. A freeing thread can accumulate remote blocks for the same owner and push them as one chain, turning many atomic operations into one. The trade is the same as for refill: larger batches mean less coordination but more memory in flight and a longer delay before the owner can reuse it.

saying these in an interview costs you the question

  • Assumes a cross-thread free costs the same as a local one
  • Claims the freeing thread cannot tell which cache owns a block
  • Thinks cross-thread frees corrupt the heap rather than degrading it
  • Expects a per-thread cache to help a pipeline with fully crossed lifetimes
  • Ignores that an exiting thread's cached and remote blocks must be retired