Arena Allocation and the Cost of Releasing Everything at Once

Freeing an object individually costs more than most call sites assume. The allocator must find the block’s metadata, update its free list, possibly coalesce with a neighbour, and touch a cache line that the caller may not otherwise need. The work is proportional to the number of objects, and in a workload that builds a large tree and then discards it, that work dominates. Arena allocation removes the per-object cost by changing the unit of release: objects are allocated by advancing a pointer, and they are released all together when the arena is discarded or reset. What is lost is the ability to free one object early, and that loss is a design constraint rather than an oversight.

Bump allocation in detail

An arena is a contiguous region with a base pointer and a current offset. Allocation aligns the offset to the requested alignment, returns the resulting address, and advances the offset by the size. The region grows by acquiring a new chunk when the request does not fit, and the chunks are kept in a list so that reset can walk them.

struct arena_chunk {
    struct arena_chunk *next;
    size_t used;
    size_t cap;
    unsigned char data[];
};

void *arena_alloc(struct arena *a, size_t size, size_t align)
{
    struct arena_chunk *c = a->head;
    size_t off = c ? (c->used + align - 1) & ~(align - 1) : 0;
    if (!c || off + size > c->cap) {
        /* new chunk: at least size + align, rounded to a power of two */
        size_t cap = 1u << 16;
        while (cap < size + align) cap <<= 1;
        struct arena_chunk *n = malloc(sizeof(*n) + cap);
        if (!n) return NULL;
        n->next = c; n->used = 0; n->cap = cap;
        a->head = n;
        c = n;
        off = 0;
    }
    c->used = off + size;
    return c->data + off;
}

Two properties follow from that code. Allocation is a few arithmetic operations plus a bounds check, with no search through a free list and no metadata per object. And there is no way to free one object, because the only state is the offset and the objects before it have no record of their own size.

The absence of per-object headers is where the space saving comes from. A general-purpose allocator typically stores a size and a link per block, which on a 64-bit target means at least 16 bytes of overhead for a 32-byte object, a 50 percent tax. An arena that allocates a fixed-size object type can store nothing at all, because the size is implied by the type.

Alignment deserves attention because the offset arithmetic above can waste space. A request for 1 byte followed by a request for 8 bytes leaves up to 7 bytes of padding. Allocating the largest-aligned objects first, or separating the arena into sub-arenas per alignment class, reduces the waste. In practice the ordering of requests is a property of the program rather than something the allocator controls, so the padding is accepted.

Lifetimes and the discipline they impose

The correctness rule for an arena is that no object allocated from it may outlive the arena. That sounds obvious, and it is the rule most often broken, because the arena’s lifetime is usually tied to a scope that is wider than the code using the objects realises.

Region-based memory management makes this a type-level property. A region is created, values are allocated into it, and the region is destroyed when control leaves the scope that owns it. The type system tracks which region a reference belongs to and rejects a reference that escapes its region. The Tofte-Talpin work formalised the calculus and the inference rules; the practical effect is that escape is a compile error rather than a dangling pointer.

Languages without such a type system rely on convention, and the conventions are specific. A parser that allocates its syntax tree in an arena must not return a pointer into that arena to a caller that outlives the parse, unless the caller also takes the arena. A request handler that allocates per-request data in a per-request arena can safely return that arena to a pool when the response is written, because nothing else refers to it. The boundary is the lifetime of the arena, and every interface that hands out an arena-allocated pointer has to document which arena it belongs to.

The failure mode is a use-after-free that is harder to diagnose than an ordinary one. Because the arena’s memory is returned as a whole, the region may be unmapped or reused by a different arena, and a stale pointer then reads unrelated data. A sanitizer that poisons freed regions can catch it, but the quarantine has to cover a whole arena rather than a block, so the detection window is coarse.

Reset, pooling, and the growth that never stops

Discarding an arena costs one free per chunk, which is a small constant independent of the number of objects allocated inside it. Reusing it costs even less: reset sets every chunk’s offset to zero and keeps the chunks allocated, so the next round of allocations reuses the same pages and the process’s resident size stabilises.

That reset-and-reuse pattern is what keeps a long-running service from growing. The naive version, allocating a fresh arena per request and freeing it at the end, performs an allocator call per request and returns the pages to the system, which then has to fault them back in on the next request. The pooled version trades a bounded memory footprint for the absence of that fault traffic.

The bound is set by the high-water mark of concurrent arena use, not by the total number of requests. A pool that keeps as many arenas as the maximum number of simultaneously active handlers will stop growing once that maximum is reached. A pool that allocates a new arena whenever the free list is empty and never trims will grow to the maximum concurrency the process ever experienced, which may be far above its steady-state load. Trimming is therefore a policy decision: keep the free list capped, and free arenas beyond the cap.

A second growth source is the arena that is never reset. A program that creates one arena at startup and allocates into it for the whole run has, in effect, a bump allocator over an unbounded heap, and it will exhaust memory. The absence of a reset is the same defect as a missing free, expressed at a coarser granularity, and the diagnostic from leak detection applies with the arena as the unit.

Where arenas fit against other schemes

The comparison is clearest on three axes: cost per allocation, cost per release, and flexibility.

A general-purpose allocator has a cost per allocation that depends on the size class and the state of the free lists, typically tens of instructions for a hit in the fast path, and a cost per release of similar magnitude. It supports individual frees and arbitrary lifetimes.

An arena has a cost per allocation of a handful of instructions and a cost per release that is amortised across the whole region. It supports only bulk release, and its objects share one lifetime.

Reference counting, described in shared ownership, has a per-copy atomic cost and a per-object release cost, and it supports arbitrary individual lifetimes at the price of a header and the cycle problem.

Garbage collection has no per-release cost at all and a per-collection cost proportional to the live set, and it supports arbitrary lifetimes with no programmer discipline, at the price of pauses and a runtime.

The arena wins when the object graph has a natural lifetime boundary: a parse, a request, a compilation phase, a frame’s worth of temporary data. It loses when objects from one region must outlive the region while others do not, because then either the region is widened to the longest lifetime and grows, or the long-lived objects must be copied out.

Copying out as an explicit cost

The escape problem has a standard answer: when an object must outlive its arena, copy it into the longer-lived region. A parser that produces a syntax tree in a scratch arena and then converts it into a compact form in the output arena pays one copy of the data it retains, and frees the scratch arena wholesale. The cost is proportional to the retained data, not to the total data, which is the point: the scratch arena absorbed all the intermediate allocations, and only the survivors are copied.

The copy must be deep enough to cover every pointer in the retained structure. A shallow copy that moves the root and leaves interior pointers aimed at the scratch arena produces dangling references the moment the scratch arena is reset. This is the same class of defect as a move that transfers a handle without transferring the pointed-to graph, described in ownership transfer, and it is the reason arena-based interfaces tend to expose the arena as an explicit parameter rather than hiding it behind an allocator that looks general.

A related pattern is the arena that is never freed but is instead transferred. A compiler that produces an object file can move its output arena into the linker’s input set, and the linker then owns the lifetime. The transfer is a pointer assignment, and the release happens once at the end of the link. That is the same trick as a bulk release, applied across a phase boundary instead of within one.