How much state does an allocation need?_

With eight threads, the stock allocator reached 2.3 times its single-thread throughput. The sharded arena reached 7.85 times its own single-thread rate in the same harness. This compares scaling, not single-operation speed. Profiles and cache measurements point to shared metadata and cache-line movement as contributors to the gap.

My first instinct was to look for a better lock. The more useful question was smaller: which shared state does one allocation actually have to touch? The arena reduces that path to one packed cursor. The segregated allocator uses a lock-free queue per size class, with a sequenced front and a separate back pointer.

These allocators came from low-level game-engine runtime work. Each was built for a different allocation pattern.

The four allocators

A general allocator must free any pointer it returns, from any thread, in any order. Size classes, free lists, per-block headers, and locks support that flexibility. A subsystem that releases thousands of allocations together may never use most of it, but still pays for it on every allocation.

The library uses a two-level segregated-fit allocator for general use and a bump arena when allocations mostly share a lifetime. A page allocator provides raw virtual memory for page-sized scratch. The fourth allocator wraps an allocation in inaccessible guard zones so an overrun faults before reaching neighboring data.

The segregated allocator removes per-allocation headers and keeps growth off its normal path. The arena goes further and reduces allocation itself to one packed atomic cursor.

The arena is the narrowest allocator in that set. It serves allocations with grouped lifetimes, so it does not need a free list or per-allocation metadata. One 64-bit word holds the current block index, that block's size factor, and the next free position.

Allocation adds the requested size to that word. The value returned by fetch_add names both the block and the caller's starting position, so the common case touches no other shared state. The price for this smaller operation is a smaller API: callers release the arena together instead of freeing objects in arbitrary order.

Metadata that lives in the free blocks

A segregated-fit allocator rounds each request up to a size class, and every class keeps a queue of matching blocks. The two-level index finds the nearest class at or above the requested size. The interesting work starts inside those queues.

The first interesting decision is where the queue linkage lives. This one keeps it inside the free blocks themselves: a free block's first bytes hold the pointer to the next free block. The queue 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.

A live allocation has no header and no side-table entry. Its queue link exists only while the block is free, using bytes that are otherwise idle.

The API makes that possible with sized deallocation. deallocate(ptr, size) receives the original size, maps it through the same two-level class function used by allocation, and returns the block to that class. The allocator does not recover the class from the pointer.

The minimum size class must be at least pointer-sized. On a 64-bit target, a one-byte request therefore receives an eight-byte block so it can hold the queue link when freed. A header-based allocator pays for its metadata beside both live and free allocations.

The fast path and the growth lock

Each size class exposes a lock-free MPMC queue. Consumers advance a sequenced front pointer, a pointer paired with a generation index so removing and later reusing the same address does not make an old front snapshot valid again. Producers exchange a separate back pointer and then link the previous tail. Front and back occupy separate cache lines.

The free side puts the intrusive link back into dead memory, exchanges the queue's back pointer, and links the previous tail to the returned block. It does not acquire the growth lock. The transition from an empty queue also republishes the front, so "one freelist word" would be an inaccurate description of this path.

When blocks are available, allocation only pops the class queue. When a class is empty, one thread takes the growth lock and calls the base allocator. Queue operations remain lock-free, while the rare capacity increase is serialized.

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

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

After taking the growth lock, the winner checks the queue again so ten empty observations do not trigger ten base allocations. The new blocks go into the shared queue, and every thread retries the same pop.

A separate try-entry pops or fails without growing. Latency-critical callers can choose that behavior explicitly instead of discovering a base-allocation call as a spike.

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 in private memory. Publishing the batch exchanges the queue's back pointer once and links the previous tail to the first new block. If the queue was empty, publication also restores the front state. The shared work is per batch rather than per block.

The expensive part happens in private memory at plain-store cost. Publication updates queue state once for the chain rather than once for every block.

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 batch call receives the first and last block plus their shared size class. It publishes the chain through the same queue-back exchange and tail link used by a single free.

Growth and batch free both publish pre-linked chains. The arena can use less shared state because it gives up cheap arbitrary-order frees.

How the packed cursor allocates

In the configuration compiled below, the cursor uses seven bits for the block index, two bits for the size factor, and fifty-five bits for the position. Block lifetime and capacity bookkeeping live outside that cursor on colder paths.

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 inspect emitted instructions across compilers as part of this work. For this path, I lifted the encoding and fast path into a standalone file and compiled it with clang-18 at -O2 on an Intel Core Ultra 7 265. The reservation is one locked add followed by register arithmetic, with no branch 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 fit in one word so allocation touches only one piece of shared mutable state. The value returned by fetch_add identifies the block, size factor, and byte position.

No retry loop

The fast path has no software retry loop. The atomic fetch_add reserves a distinct range and returns its previous value. Contention still serializes updates to the cursor's cache line, and a target may implement the atomic below the language abstraction in different ways, but the allocator does not recompute and retry a rejected reservation.

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. Let P be one past the largest position value, C the configured concurrent-access capacity, and M the maximum aligned request. The safety threshold is L = P - C*M. A fresh block starts at position zero. The reserved C*M range sits at the top of the position field, leaving room for at most C simultaneous maximum-size increments without carrying into the size-factor or block-index bits.

When no free block remains and the accumulated position reaches L, a losing allocation removes its increment with compare-exchange unless another thread has already installed a new block. The default capacity is 1024 and callers are forbidden to exceed it. That bound, together with request <= M, is the reason overshoot cannot reach P. The cursor does not start near the limit.

A CAS loop could check before committing, but every allocation would then retry when another thread won. This design reserves enough position bits for the configured number of simultaneous entrants. The caller can raise that limit, and the documentation states what happens if it is exceeded. The default of 1024 is a policy choice.

A counter that ends at exactly zero

Freeing from a bump allocator is usually a non-feature. This arena also tracks one allocated-byte counter per block. When the active cursor rotates, the old cursor position, including failed reservations that still need unwinding, is added to that block's counter. Every sized deallocation subtracts its aligned size with release ordering. The thread whose subtraction observes exactly that remaining size moves the counter to zero and takes the capacity lock to recycle or evict the block.

This is accounting, not stale-free protection. The caller must deallocate each allocation exactly once with the correct size, and no delayed free may arrive after that block has been reclaimed and reused. The generation IDs used by statistics do not authorize stale pointers.

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.

The arena therefore supports individual sized frees and can recycle drained blocks. The caller must pass the exact size and free each allocation once before its block can be reused.

The same word on two machines

The design rests on one atomic add, so I compiled the same loop for arm64 and ran it on an Apple M5 Max beside 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?

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 55-bit position mask also differs. The constant 0x7FFFFFFFFFFFFF does not fit in an x86 instruction, so clang materializes it with movabs and then ANDs. Arm64 folds the mask into the AND as a logical immediate.

Extracting the two-bit size factor takes a shift and mask on x86. Arm64 uses one ubfx.

On both machines, each worker performs 20 million 16-byte reservations and decodes the returned packed word into the checksum. After one warmup, the table reports the median of seven repetitions. Nanoseconds per operation and million operations per second come from the same elapsed time:

The Intel run measured 3.979 nanoseconds per reservation. The M5 Max measured 2.446 nanoseconds, or 1.63 times the throughput. This wall-clock comparison does not isolate frequency, microarchitecture, compiler, or memory-order implementation. It shows the cost of this complete loop on these two systems.

Costs of the packed cursor

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.

Callers that need arbitrary frees or more concurrent entrants use the segregated allocator.

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.

The second thread cuts total throughput to a third or worse. With eight threads, throughput falls below one fifth of the single-thread result because every lock xadd needs exclusive ownership of the same line.

The standard fix is to give each thread a chunk and a private, non-atomic cursor. The shared word is touched only when a chunk runs out, once per refill rather than 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:

At eight threads, the private cursor delivered 85.9 times the shared-word rate on Intel and 55.9 times on the M5 Max. Those multipliers use a 4 KiB refill. On both machines, moving the shared atomic out of each allocation changed the scaling.

; 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

Linux uses fs:-relative access for thread-local state. I inspected the macOS assembly from a native build because Compiler Explorer does not target that ABI. The private cursor won even at one thread on both machines, and contention widened the gap. This benchmark does not isolate TLS access from the rest of the loop.

The packed cursor uses eight bytes and performs one atomic read-modify-write per allocation. The thread cache adds per-thread slack, but avoids that shared update until refill. The better choice depends on contention and TLS cost.

Eight-thread allocator scaling

The final benchmark uses eight allocate/free threads and scores each allocator against its own single-thread rate. The arena is sharded, so one thread normally touches each hot word. A 7.85x result means that it retained nearly all of its own throughput as threads were added. It does not compare its single-thread latency with the stock allocator.

The ordering tracks shared state in this harness. The libc allocator, which carries the widest contract and the most bookkeeping, reaches 2.3 times its single-thread rate. The per-thread-cache allocator reaches 5.8. The segregated fit, with a sequenced front pointer and a separate producer tail for each size class, reaches 7.6. The sharded arena reaches 7.85x against the theoretical 8x ceiling.

At one million 64-byte allocations, metadata overhead measured roughly 50% for the libc allocator and about 25% for the caching allocator. The segregated fit's per-span state fell below the table's displayed precision at this scale. The arena used about 0.4%, or roughly a quarter of a byte per allocation.

L1 misses per million operations on a random allocation pattern were about 87,000 for the libc allocator, about 27,000 for segregated fit, and about 11,000 for the arena. Metadata may not explain the entire scaling gap, but the designs clearly move different amounts of data through L1.

These are scaling results for each allocator's intended workload, not a universal allocator ranking. Libc can win on other workloads.

Why the arena keeps a small lead

The remaining gap is small and unsurprising. The arena reserves bytes with one unconditional lock xadd. Segregated fit maintains a queue: its wider front update may retry, producers update a separate tail, and removing the final node requires both ends to agree on the empty transition.

That extra coordination is consistent with 7.6x scaling instead of 7.85x. This benchmark does not separate the cost of compare-exchange retries from the rest of the queue bookkeeping, so it cannot assign the difference to one instruction.