How much state does an allocation need?_

Eight threads hammered a stock allocator and produced 2.3 threads' worth of throughput. The same harness gave an arena from the library 7.85. Nothing was wrong with the stock allocator; it was paying for promises the benchmark never used. The missing 5.7 threads were the price of generality, expressed as shared metadata and cache lines in motion.

My first instinct was to look for a better lock. The more useful question was smaller: how little shared, mutable state can one allocation touch? For the specialized allocators here, the answer keeps collapsing toward one word: a freelist head for blocks with independent lifetimes, or a packed cursor for blocks that die together.

These benchmark-suite results come from low-level runtime work for game engines, and each belongs to the workload and lifetime contract it was built around. I start with that contract, derive the metadata it still requires, then follow one allocation to the instruction and cache line it contends on.

A family instead of a malloc

Start with what a general allocator has to promise, because the promise is where the cost lives. It will free any pointer it handed out, from any thread, at any time. Everything it keeps, it keeps so that some caller can use that promise: the size classes, the free lists, the header in front of every block, the lock. Most callers never use it. A subsystem that allocates a few thousand things and frees them all at the end of the frame is paying, on every single allocation, for a guarantee it will never call in.

So the library ships four allocators instead of one. A two-level segregated-fit allocator is the general-purpose member. A bump arena covers allocations that live and die together. A page allocator hands out raw virtual memory for page-granular scratch, with no size-class machinery in the way. A guard-zone wrapper brackets each allocation with tripwire regions for hunting memory stomps, so an overrun lands in a tripwire instead of in a neighbor's data. Each one keeps a different piece of the general promise and drops the rest.

Between the segregated fit and the arena, the shared state drops from one word per size class to one word total, so those two get the detail.

Metadata that lives in the free blocks

Segregated fit is the standard shape for a general allocator: requests round up to a size class, and each size class keeps a freelist of blocks of exactly that size. The two-level part is the usual indexing scheme over the classes and it is not where the interesting decisions were, so I will leave it at: you ask for n bytes, you get the nearest class at or above n, and the rounding waste stays bounded.

The first interesting decision is where the freelist lives. This one keeps its linkage inside the free blocks themselves: a free block's first bytes hold the pointer to the next free block. The list is intrusive, and the memory it threads through is exactly the memory it is handing out. When a block is allocated, the link is overwritten by the caller's data, because nothing needs to find that block anymore. When it is freed, the link goes back in.

So a live allocation carries nothing: no header sits in front of it and no side table tracks it. The only bookkeeping the scheme owns, the link, exists only while the block is free, in bytes that would otherwise sit idle.

The design pays for this in one place, and the library is quiet about it: the minimum size class is silently raised to pointer size. Ask for one byte on a 64-bit target and you get an 8-byte block, because that block will someday be free again, and a free block must be able to hold its own link. Compare that with a header-based allocator, where the metadata sits beside every allocation whether it is live or free.

The fast path and the growth lock

Each size class exposes its freelist as a lock-free stack: pop a block to allocate, push a block to free. The shared state a thread touches on the fast path is one word, the head of the list for its class, and the whole fast path is one atomic operation each way.

The free side is the intrusive trick from the previous section put back to work. The block being freed is dead memory again, so its first bytes are available for the link the moment the caller lets go. Freeing writes the link into the dead block and pushes the block. There is no slow path on this side; a free never grows anything and never takes a lock.

That covers the common case. The uncommon case is a class running out of blocks, and here the design splits the world in two instead of picking one lock for everything. A lock around the whole allocate path makes every thread pay for the rare grow: every pop queues behind a mutex so that the rare grow is convenient to write. A lock around only the grow leaves the pops lock-free and serializes the thing that was going to serialize anyway, because growth calls into the base allocator and there is no useful concurrency to be had there. The library locks only the grow.

The choreography around that lock is easier to see as pseudocode than as prose:

// pop is one atomic; grow only under the class lock, then retry
void* allocate(int cls) {
    for (;;) {
        if (void* p = freelist[cls].pop())     // one atomic on the hot path
            return p;
        std::lock_guard<std::mutex> g(growth_lock[cls]);
        if (freelist[cls].empty())             // re-check under the lock
            grow(cls);
        // no block is reserved for us; go around and pop again
    }
}

First, the grower re-checks after taking the lock. Say ten threads find the list empty at the same moment; the first one through the lock grows, and the other nine must notice the world changed while they waited, because growing nine more times would be nine wasted trips to the base allocator.

Second, the loop retries the lock-free pop after growth instead of handing the grower a block directly. The freshly added blocks are published to the same freelist everyone else is popping from, so they can be stolen by threads that never took the lock. The grower gets no reservation and goes around the loop again like everyone else. This keeps the fast path uniform, and the cost is honest: under a stampede you might grow and then pop a block someone else's growth paid for.

Third, there is a separate try-entry that pops or fails and never grows. The allocator cannot know whether this call site can afford a trip into the base allocator; the call site knows. A caller on a latency-critical path uses the try-entry, takes the failure, and does something else, rather than discovering the slow path by measuring a spike.

So the class in steady state is one word of contended state and zero locks; the lock exists, guards only growth, and a caller who cannot tolerate even that can opt out of it per call.

Growth builds in private and publishes once

A growth span starts with a question to the base allocator: what will you round this request to? The span is then sized to exactly that answer, so the allocation lands exactly on page boundaries and no rounding slack is left stranded on the far side. Sizing the span first and letting the base allocator round it up would strand rounding slack past every growth.

The span's bookkeeping header goes at the tail, not the head. A header at the head would start the first block one header past the page boundary, and every block after it would inherit the skew, so the allocator's own bookkeeping destroys the alignment the base allocator just handed over. At the tail, the header lives in the leftover space at the end where alignment does not matter, and every block stays exactly where the base allocator aligned it.

Then the new blocks are linked into a chain, non-atomically, in memory no other thread can see yet. Linking a thousand blocks through the shared freelist head would be a thousand contended atomics before anyone gets to allocate. Linking them privately costs plain stores, and the whole chain is published with one atomic push of its head onto the freelist, so growth touches the contended word once no matter how many blocks it minted.

The expensive part happens in private memory at plain-store cost, and the shared freelist head is touched exactly once.

Batch free

Batch free applies the same trick in the other direction. Growth pre-linked new blocks in private memory and published them with one push; batch free asks the caller to pre-link dying blocks in memory that is already dead.

A caller with a thousand allocations to release links them into a chain through their own bytes. The allocations are dead the moment the caller decides they are dead, which makes their bytes available as link storage right now, before the allocator has heard anything. The caller threads the chain, hands the whole thing over in one call, and the allocator splices it in with one contended atomic for the whole thousand. The bookkeeping cost moved into plain stores to dead memory, where it contends with nothing.

The segregated fit leaves one contended word per size class. Its metadata lives inside free blocks, its lock guards only growth, and both growth and free publish batches. The arena reduces the state again, to one word for the whole region.

The arena: one 64-bit word

The arena serves a narrower profile: many allocations with grouped lifetimes, where the caller does not need arbitrary-order individual frees to be cheap. For that narrower promise it gets to be almost stateless. The entire allocator state is one 64-bit word that packs three fields: which block we are allocating from, a size factor that says how many times the base block size this block was grown to, and the current position inside it. The split is seven bits of block index at the top, two bits of size factor, and the remaining fifty-five bits of position at the bottom.

Allocation is a single fetch_add on that word. The add reserves space and detects exhaustion at the same time, because both outcomes are readable from the value the fetch_add returns. This is the real decode, transcribed from the source I worked on and then compiled to check the instructions:

// one fetch_add, no loop; the fit check is the slow-path signal
void* allocate(size_t request) {
    uint64_t size = align_up(request, 16);
    uint64_t enc  = state.fetch_add(size, std::memory_order_relaxed); // the bump
    uint32_t block  = enc >> 57;                       // block index  [63:57]
    uint64_t pos    = enc & ((1ull << 55) - 1);         // position     [54:0]
    uint32_t factor = (enc >> 55) & 3;                 // size factor  [56:55]
    if (pos + size <= (block_size << factor))           // still inside the block?
        return base + (block << block_size_max_log2) + pos;
    return slow_path(size);                            // rotate to a fresh block
}

I did not want to trust my memory of the instructions, so I lifted the encoding and this fast path verbatim into a standalone file and compiled it with clang-18 at -O2 on an Intel Core Ultra 7 265. The whole reservation is one locked add and then pure register arithmetic, no branch back to the caller until the fit check:

; clang-18 -O2 -masm=intel (x86-64), Intel Core Ultra 7 265
    add    rsi, 15
    and    rsi, -16                    ; align the request up to 16
    mov    rcx, rsi
    lock   xadd qword ptr [rdi], rcx   ; the single bump; rcx = old packed word
    mov    rdx, rcx
    shr    rdx, 57                      ; block index = enc >> 57
    movabs rax, 36028797018963967       ; 0x7FFFFFFFFFFFFF, the 55-bit mask
    and    rax, rcx                     ; position    = enc & mask
    shr    rcx, 55
    and    cl, 3                        ; size factor = (enc >> 55) & 3
    mov    r9, qword ptr [rdi + 8]      ; block_size
    shl    r9, cl                       ; block_size << factor
    lea    r8, [rax + rsi]              ; position + size
    cmp    r8, r9                        ; fits in the block?
    jbe    .fits                         ; yes: compute the address and return

Follow one allocation through. The thread adds its request size to the packed word. The returned old value tells it which block was current and at what position its bytes begin. If the position plus the request still fits the block, that range belongs to this thread and no other, because the hardware puts every fetch_add on that word in a total order, and each add moves the position past the bytes it just claimed. If it does not fit, the block was exhausted, and the thread goes to the slow path to install a fresh block, at which point the word names a new block index and the position starts over.

All three fields ride in one word for one reason: the fast path must not touch a second piece of shared, mutating state. The value the fetch_add returns already says which block, what size factor, and where in the block, so the only contended memory in the whole operation is the word itself.

No retry loop

The fast path has no loop. A compare-and-swap based allocator can be forced to retry under contention, and the retry work grows exactly when the system is busiest. A fetch_add always succeeds. Contention still costs something, because the cache line holding the word travels between cores, but no thread ever redoes work.

Racing past the end

The fetch_add never retries, which means it also never checks first. Say ten threads hit an almost-full block at the same time. All ten adds go through, and the position ends up past the end of the block. Everyone who overflowed goes to the slow path, but the damage to the word is already done, and the question is whether the overshoot can bleed out of the low fifty-five position bits and corrupt the size factor and block index packed above them.

The library answers with a quantified envelope. A max-concurrent-entrants parameter, default 1024 and required to be a power of two, sizes the margin built into the encoding: allocation does not start the position at zero but at a limit set back from the top of the field by that many maximum-size blocks, so up to that many threads can all pile past the end simultaneously without the overflow reaching the neighboring fields. Inside the envelope, overshoot is harmless by construction. And the documentation states the other side plainly: exceed the parameter and the allocator may corrupt.

The alternative is a CAS loop that checks before committing and retries when beaten, which reintroduces exactly the retry behavior the fetch_add exists to remove, on every allocation, forever, to defend against a stampede of more than a thousand simultaneous threads on one arena. The library bounds the failure instead of paying on every allocation to prevent it. The bound sits in a parameter the caller can raise, and the consequence of exceeding it is written in the docs. Whether 1024 is the right default is a judgment call. In any redesign I would keep the written envelope and the documented corruption mode past its edge.

A counter that ends at exactly zero

Freeing from a bump allocator is usually a non-feature: the offset only moves forward, so the standard answer is "free everything at once by resetting". This arena does better than that, without giving up the one-word allocation path. Deallocation maintains a per-block counter whose arithmetic lands on exactly zero once everything allocated from that block has been freed. Zero means drained: the block's memory is reclaimable, and the check that decides it is a single comparison against a constant.

What happens to a drained block is a policy the caller controls: by default it recycles back into the arena's rotation, and an evict flag releases it instead. A long-lived arena with steady churn wants recycling, because the block is warm and the base allocator is a trip away. An arena that just finished a spike wants eviction, because holding the block is just keeping memory away from everyone else.

So the arena's contract ends up wider than "bump and reset": individual frees exist and blocks come back, provided the caller accepts the fine print.

The same word on two machines

The x86 fast path above is one machine's answer. I wanted the other one, because the whole design rests on a single atomic add and the two architectures I build for disagree about what an atomic add costs. So I compiled the identical fast path for arm64 and ran it on an Apple M5 Max next to the Intel Core Ultra 7 265.

; clang -O2 (arm64), Apple M5 Max
    add    x8, x1, #15
    and    x1, x8, #0xfffffffffffffff0   ; align the request up to 16
    ldadd  x1, x9, [x0]                  ; the single bump (relaxed LSE); x9 = old word
    lsr    x2, x9, #57                    ; block index
    and    x8, x9, #0x7fffffffffffff      ; position (the 55-bit mask folds into the AND)
    ubfx   x9, x9, #55, #2                ; size factor: one bitfield-extract
    ldr    x10, [x0, #8]                  ; block_size
    lsl    x9, x10, x9                     ; block_size << factor
    add    x10, x8, x1                     ; position + size
    cmp    x10, x9                          ; fits?

Three differences carry the comparison.

The atomic comes first. On x86 the bump is lock xadd, and the lock prefix makes it a full barrier even though the source asks for relaxed ordering. On arm64 it lowers to bare ldadd; a sequentially consistent add would use ldaddal. The C++ memory order is visible in the arm64 mnemonic and absent from the x86 one.

The second difference is the position mask. The 55-bit constant 0x7FFFFFFFFFFFFF does not fit in an x86 instruction, so clang materializes it with movabs and then ANDs. arm64 folds the same mask straight into the AND as a logical immediate, because its encoding can name a run of set bits inside the instruction. One machine spends an instruction on a constant the other spends nothing on.

The third is the size factor. Pulling two bits out of the middle of the word takes two instructions on x86, a shift and then a mask. On arm64 it is a single ubfx, unsigned bitfield extract, which is the instruction this packed layout was practically asking for. The design that hides three fields in one word decodes one of them in a single instruction on the machine that has a bitfield-extract instruction.

Then the measurement. Single thread, register accumulation, so the number is the bump and the decode and nothing else:

The Intel P-core runs the fast path at about 3.8 nanoseconds, roughly twenty cycles. The M5 Max runs the same algorithm at about 1.6, 2.4 times faster. The wall-clock result cannot separate frequency, microarchitecture, and memory ordering. On Intel, however, about 81% of samples land immediately after lock xadd, where the core is waiting for the locked add to retire. The atomic is the measured bottleneck.

The fine print

Oversized allocations leave permanent tail holes. An allocation too big to fit in what remains of the current block forces a new block, and the tail of the old one is stranded: the offset only moves forward, so nothing can go back and fill the gap. The hole lasts as long as the block does.

Realloc works in place and only for shrinking. Growing in place would need the bytes after your allocation, and in an arena those bytes were probably fetch_added to another thread before your realloc call even started.

The ownership query, "does this pointer belong to this arena", is O(block count). The word names the current block; answering for an arbitrary pointer means walking the blocks. The general allocator answers ownership questions structurally; the arena makes you pay per block, because keeping a faster index would be state, and state is the thing being minimized. So ownership checks belong in asserts and debugging tools, not on hot paths.

And the envelope from earlier is a real ceiling: more than max-concurrent-entrants threads racing one arena is documented as possible corruption, because past the margin the overshoot can reach the fields packed above the offset.

The docs state the arena's profile and the costs of leaving it, and point a caller who needs the wide contract back at the segregated fit.

When the one word is actually shared

The arena scales only when its hot word is sharded by subsystem, core, or thread. To measure the cost of violating that assumption, I pointed every thread at one arena and had all of them bump the same word.

Adding the second thread already cuts total throughput to a third or worse. By eight threads the shared word delivers less than a fifth of what one thread did, on both machines. This is the cache line the word lives on bouncing between cores: every lock xadd has to acquire that line exclusive, and while it holds it no other core can make progress. The wait-free add that was the whole point is still wait-free, it just does not help when the memory it operates on can only be in one core's cache at a time.

The fix is old and known, and it is not mine: give each thread its own chunk and a private, non-atomic cursor, and only touch the shared word when a thread's chunk runs out. This is the thread cache that every serious general allocator has some form of. The shared bump becomes the refill path, hit once per chunk instead of once per allocation.

// per-thread chunk, non-atomic bump; the atomic fires only on refill
void* allocate(size_t request) {
    size_t size = align_up(request, 16);
    Cache& c = tls();                 // this thread's cursor
    if (c.ptr + size <= c.end) {      // fast path: a plain, non-atomic add
        void* p = (void*)c.ptr;
        c.ptr += size;
        return p;
    }
    return refill(size, c);           // chunk empty: ONE shared lock xadd, amortized
}

Same benchmark, same machines. Now the shared word is out of the per-allocation path:

On Intel the thread cache scales almost linearly and at eight threads does roughly 386 times the work of the shared word. On the M5 Max, one thread improves only from 570 to 648 million allocations per second because thread-local access has its own cost.

; the SAME per-thread cursor access, two platforms

; arm64 / macOS: the cursor is behind an indirect call
    adrp x0, cache@TLVPPAGE
    ldr  x0, [x0, cache@TLVPPAGEOFF]
    ldr  x9, [x0]
    blr  x9                          ; __tlv_get_addr: emulated TLS is a function call

; x86-64 / Linux: the cursor is a segment-register offset
    mov  rax, qword ptr fs:[cache@TPOFF]   ; near-free, no call, no barrier

On Linux the per-thread cursor is an fs:-relative load the CPU does in stride, so trading one lock xadd for a couple of segment-relative loads is pure win, and the Intel numbers show it. On macOS every access to that same thread-local goes through __tlv_get_addr, an indirect call, and on Apple Silicon a relaxed ldadd is already cheap, so you spend a call to skip an add and net almost nothing single-threaded. The thread cache still wins under real contention there, because the shared word still collapses. The win comes from the algorithm, from taking the atomic off the per-allocation path; but how much of it survives single-threaded turns on the platform's thread-local model as much as on the allocator itself.

So one lock xadd per allocation can be beaten, by not sharing it, with two costs attached. The packed word costs eight bytes of state and gives back a wait-free add; the thread cache scales, but you pay in per-thread slack memory and in whatever your platform charges for a thread-local access. Neither one dominates on every axis. I went in half-hoping the measurements would knock that down and pick a winner, and they held it up instead.

The numbers

Now the benchmark from the top of the post, with the sharding assumption on the table: eight threads doing allocate/free, each allocator scored against its own single-thread rate, the arena deployed sharded, so the hot word stays a word one thread is touching. The benchmark measures scaling rather than raw speed: a 7.85x allocator is not claimed to be faster than a 2.3x allocator on one thread, only to lose almost nothing when threads are added.

The ordering tracks shared state. The libc allocator, which carries the widest contract and the most bookkeeping, keeps 2.3 of its 8 threads. The per-thread-cache allocator, a serious production design, keeps 5.8. With one contended word per size class, the segregated fit reaches 7.6. The arena, one word total and a wait-free add on it, comes in at 7.85 of 8, a loss of about two percent against the theoretical ceiling.

Metadata tells the same story from the space side. At one million 64-byte allocations, metadata overhead measured roughly 50% for the libc allocator, about 25% for the caching allocator, 0% for the segregated fit, and about 0.4% for the arena. The 50% converts to around 32 bytes of header and padding on every 64-byte allocation. The segregated fit's 0% is the intrusive freelist from earlier doing exactly what it promised: live allocations carry nothing, and the per-span bookkeeping amortizes to nothing at this scale. The arena's ~0.4% at the same allocation size works out to roughly a quarter of a byte per allocation, which is what accounting per block instead of per pointer costs.

And the cache follows the metadata. L1 misses per million operations on a random allocation pattern: about 87,000 for the libc allocator, about 27,000 for the segregated fit, about 11,000 for the arena. Bookkeeping that lives inside the blocks touches memory the caller was about to touch anyway. Headers and side structures drag extra cache lines through every operation, and eight cores pulling those lines back and forth is where the 2.3x from the first paragraph comes from.

One caveat on the whole table. Every specialized allocator here was measured on the profile it was built for, against a baseline that has to serve every profile at once, with no entrants parameter and no documented corruption mode. On other workloads the baseline sometimes wins, and the benchmark suite is not evidence about workloads it did not run. So the table reads correctly as profile-matched allocators on their home profiles, not as a ranking of allocators.

The gap I did not close

The smallest gap in the table is the one I cannot explain: 7.6x for the segregated fit against 7.85x for the arena. Both fast paths touch one shared word.

The operations on that word differ. The arena's bump is one wait-free lock xadd that cannot fail. The freelist pop is an ABA-safe compare-exchange on a pointer-and-counter pair: a lock cmpxchg16b retry loop on x86 and a single caspa on arm64. The 128-bit x86 form also takes rbx for half its operand, so the compiler saves and restores it around the call.

Retries under contention could account for the missing quarter of a thread. That is my current hypothesis, not the result. The benchmark that would isolate retry count from the rest of the allocator was never run, so the table supports the gap and the instruction trace supports a mechanism, but neither proves that the mechanism caused the gap.