Arenas and region allocation

What does an arena buy by freeing everything at once, and what does it cost in peak memory and dangling pointers?

The constraint

A general allocator's per-object work exists to support "free in any order". Concretely:

• an 8–16 byte header on small allocations,
• size-class rounding (the allocator rounds your request up to the nearest standard size),
• a free-list search,
• coalescing (merging neighbouring free blocks) on release.

A malloc/free pair costs tens to low hundreds of nanoseconds. A bump-pointer allocation (keep a pointer into a big block, add the size, check the bound) is an add and a comparison: single-digit nanoseconds. The ratio is 50–100×, and it matters because the allocation rate in an execution engine is per tuple or per batch, not per request.

Fragmentation, named properly

Fragmentation is the disease that arenas cure.

• Internal fragmentation is size-class rounding. Allocators of the jemalloc kind round to classes, so an 8-byte payload plus a header can occupy 32 bytes. This is granularity mismatch: allocation granularity versus object granularity. It is the same arithmetic as page size versus record size in storage, and it produces space amplification in the same way.
• External fragmentation is worse because it does not look like itself. Free memory exists but not contiguously. RSS stays high while the reported heap usage is low, and the process appears to leak while leaking nothing. Long-running workloads with mixed allocation sizes produce it structurally. The failure message is "4 GB free, cannot allocate 1 GB".

The mechanism

If allocations in a unit of work share a lifetime, replace free-in-any-order with free-all-at-once:

1. Take one large chunk from the OS.
2. Bump a pointer through it for every allocation.
3. When the phase ends, reset the pointer.

// A minimal arena (sketch). No per-object header, no per-object free.
typedef struct { char *base; size_t used, cap; } Arena;

void *arena_alloc(Arena *a, size_t n) {
    n = (n + 7) & ~(size_t)7;              // keep 8-byte alignment
    if (a->used + n > a->cap) return NULL; // a real arena would add a new chunk
    void *p = a->base + a->used;
    a->used += n;                          // the whole allocation is this addition
    return p;
}

void arena_reset(Arena *a) { a->used = 0; } // frees EVERY object in one instruction

Consequences:

• Deallocation is O(1) for the entire region.
• Per-object metadata disappears, because no object needs to be individually found.
• Internal fragmentation collapses to the last partial chunk.
• External fragmentation becomes impossible inside the arena, by construction.

Everyone keys it to an execution phase

The reference implementation is PostgreSQL memory contexts. They are worth reading because their hierarchy mirrors the executor's phases: a per-query context, a per-portal context (a portal is a running query's cursor), and an ExprContext that is reset once per tuple. Expression evaluation can allocate freely (intermediate text values, detoasted data, function results) and the per-tuple reset reclaims all of it in one step. Postgres can afford arbitrary intermediate allocation in expression evaluation only because the reset point is defined by the iterator, not by the expression.

What it assumes and cannot verify

It assumes that nothing outlives the region. The escape analysis is manual. A pointer that survives a reset is a use-after-free with no diagnostic. That is why arenas are rare in application code and nearly universal in engine internals: in an engine the phase boundary is visible in one place, and in application code it is not.

What it costs

Costs are moved, not removed. The freeing cost moves from per-object to per-phase and is paid in peak-held memory: an arena holds its high-water mark until reset, so a single large early allocation is kept for the whole phase even after it is dead. An arena turns a memory-rate problem into a memory-peak problem. The peak is exactly the quantity that Rationing must reserve against.

One-line compression: an arena trades the right to free in any order for ~50× cheaper allocation and bounded fragmentation, and pays in peak-held memory and silent dangling pointers.