Arena allocator

Deep dive

How it works

In: allocation layout (size, align); a reset call · Out: pointer to uninitialised bytes, valid until reset or drop · State: cur, end and the list of chunks · Cost: O(1) per allocation (a few instructions); reset O(chunks).

1. Keep cur and end pointers into the current chunk.
2. Allocate (size, align): pad = (−cur) & (align − 1); if pad + size ≤ end − cur, return cur + pad and set cur += pad + size.
3. Otherwise allocate a new chunk (doubling sizes, at least big enough for the request) and retry.
4. Reset: free all chunks except the largest, set cur to its start. Drop: free all chunks.

chunk 1 [AST|AST|str···|AST|pad|u64|·······free·······]
                                    ▲cur              ▲end
chunk 2 (2× size) allocated when the request doesn't fit

Code

use std::alloc::{alloc, dealloc, handle_alloc_error, Layout};
use std::cell::{Cell, RefCell};
use std::ptr::{self, NonNull};

const MIN_CHUNK: usize = 4096;

/// Single-threaded bump arena. Values are never dropped: store only types
/// without meaningful Drop, or run destructors yourself.
pub struct Arena {
    cur: Cell<*mut u8>,
    end: Cell<*mut u8>,
    chunks: RefCell<Vec<(NonNull<u8>, Layout)>>,
}

impl Arena {
    pub fn new() -> Self {
        Arena { cur: Cell::new(ptr::null_mut()), end: Cell::new(ptr::null_mut()), chunks: RefCell::new(Vec::new()) }
    }

    #[inline]
    fn try_bump(&self, layout: Layout) -> Option<NonNull<u8>> {
        let cur = self.cur.get();
        if cur.is_null() { return None; }
        let pad = (cur as usize).wrapping_neg() & (layout.align() - 1); // bytes to next aligned address
        let remaining = self.end.get() as usize - cur as usize;
        if pad.checked_add(layout.size())? > remaining { return None; }
        unsafe {
            let start = cur.add(pad);                // pointer arithmetic keeps provenance
            self.cur.set(start.add(layout.size()));
            Some(NonNull::new_unchecked(start))
        }
    }

    #[cold]
    fn grow(&self, layout: Layout) {
        let last = self.chunks.borrow().last().map_or(0, |(_, l)| l.size());
        let size = (last * 2).max(MIN_CHUNK).max(layout.size() + layout.align());
        let cl = Layout::from_size_align(size, 16).expect("chunk layout");
        let p = NonNull::new(unsafe { alloc(cl) }).unwrap_or_else(|| handle_alloc_error(cl));
        self.chunks.borrow_mut().push((p, cl));
        self.cur.set(p.as_ptr());
        self.end.set(unsafe { p.as_ptr().add(size) });
    }

    pub fn alloc_layout(&self, layout: Layout) -> NonNull<u8> {
        if let Some(p) = self.try_bump(layout) { return p; }
        self.grow(layout);
        self.try_bump(layout).expect("fresh chunk fits the request")
    }

    pub fn alloc<T>(&self, val: T) -> &mut T {
        let p = self.alloc_layout(Layout::new::<T>()).cast::<T>();
        unsafe { p.as_ptr().write(val); &mut *p.as_ptr() } // each allocation is disjoint
    }

    pub fn alloc_str(&self, s: &str) -> &str {
        let p = self.alloc_layout(Layout::for_value(s.as_bytes()));
        unsafe {
            ptr::copy_nonoverlapping(s.as_ptr(), p.as_ptr(), s.len());
            std::str::from_utf8_unchecked(std::slice::from_raw_parts(p.as_ptr(), s.len()))
        }
    }

    /// Free everything but the largest chunk; `&mut self` proves no references remain.
    pub fn reset(&mut self) {
        let chunks = self.chunks.get_mut();
        if let Some(keep) = chunks.pop() {
            for (p, l) in chunks.drain(..) { unsafe { dealloc(p.as_ptr(), l) } }
            chunks.push(keep);
            self.cur.set(keep.0.as_ptr());
            self.end.set(unsafe { keep.0.as_ptr().add(keep.1.size()) });
        }
    }
}

impl Drop for Arena {
    fn drop(&mut self) {
        for (p, l) in self.chunks.get_mut().drain(..) { unsafe { dealloc(p.as_ptr(), l) } }
    }
}

struct Node<'a> { val: i64, left: Option<&'a Node<'a>>, right: Option<&'a Node<'a>> }

fn leaf<'a>(a: &'a Arena, val: i64) -> &'a Node<'a> { a.alloc(Node { val, left: None, right: None }) }

fn main() {
    let arena = Arena::new();
    let root = arena.alloc(Node { val: 0, left: Some(leaf(&arena, 1)), right: Some(leaf(&arena, 2)) });
    let name = arena.alloc_str("expr");
    println!("{name}: {}", root.left.unwrap().val + root.right.unwrap().val);
} // one drop frees every node

Complexity and constants

• Hot path: load, add, mask, compare, store: a few cycles when inlined; the #[cold] grow path runs once per chunk.
• Chunk doubling from 4 KB reaches 1 GB in ~18 chunks; total waste ≤ the unused tail of each chunk (bounded by ~50 % in the worst case, usually far less).
• Free-all: one dealloc per chunk instead of one free per object: freeing 10⁶ small objects drops from milliseconds to microseconds.
• Locality: consecutively allocated objects are adjacent, so traversals stream through cache lines and the prefetcher helps.

Efficiency

• Cost: The bump path is a load, add, mask, compare and store: order of 1-2 ns, against order of 10-50 ns for a malloc + free fast path. No header per object. Cold memory (order of 0.1-1 µs per fresh 4 KB page), not the bump, is the bound. Free-all is one dealloc per chunk, not one free per object.
• Levers:
  • Reset and reuse the largest chunk — avoids page faults and keeps memory cache-warm (order of 0.1-1 µs per fresh page) — repeated phases such as per request or frame.
  • One arena per thread — no atomics on the bump path (a shared arena needs fetch_add) — multi-threaded servers.
  • First chunk sized to the phase's typical total — one grow instead of about log₂ chunks — predictable workloads.
  • Allocate related objects consecutively — traversals stream through cache lines — trees, ASTs, query plans.
• Naive → standard → state of the art:
  • One Box/malloc per node, freed one by one · order of 10-50 ns per object plus a free each.
  • Bump arena with doubling chunks and one drop · order of 1-2 ns per object, one dealloc per chunk.
  • Per-thread arena that resets and keeps its largest chunk · order of 1-2 ns, no page faults after warm-up.

Implementation notes

• Thread-local or per-worker arenas: the bump path needs no atomics. A shared arena needs an atomic fetch_add on cur (still cheap, but contended).
• Reset-and-reuse beats drop-and-recreate: keeps the largest chunk warm in cache and avoids mmap/page-fault costs (first touch of a fresh 4 KB page costs order of 0.1-1 µs).
• Large requests (e.g. > 1/4 of chunk size) can get their own dedicated chunk so they don't waste the current chunk's tail.
• Arena-backed collections: growing a Vec inside an arena copies and abandons the old buffer unless it is the last allocation (then it can extend in place); build with known sizes when possible.
• Index-based arenas (Vec<T> + u32 indices) are the safe-Rust alternative for graphs: 4-byte "pointers", no lifetimes, trivially serializable.
• Destructors: either restrict to Copy/no-drop types (assert with std::mem::needs_drop::<T>()), or keep a list of drop thunks to run at reset (typed arenas do this).

Pitfalls

• Storing types that own heap memory (String, Vec) in a non-dropping arena: their buffers leak.
• Long-lived arena used for short-lived objects: memory grows until reset (a leak in all but name).
• Returning arena references beyond reset: Rust's lifetimes catch it; in C/C++ it's use-after-free.
• One arena per tiny request with a large initial chunk: memory overhead per in-flight request multiplies by concurrency.
• Mixing arena pointers with free(): crash.

Variants and alternatives

In production

bumpalo (Rust), rustc's DroplessArena/TypedArena, LLVM BumpPtrAllocator, Protocol Buffers C++ Arena, PostgreSQL memory contexts (per query/tuple), nginx request pools (ngx_pool_t), Apache APR pools, per-frame allocators in game engines.

Implementations

Sources

• David R. Hanson, Fast Allocation and Deallocation of Memory Based on Object Lifetimes, Software: Practice and Experience 20(1), 1990. paper
• Emery D. Berger, Benjamin G. Zorn, Kathryn S. McKinley, Reconsidering Custom Memory Allocation, OOPSLA 2002. paper
• Mads Tofte, Jean-Pierre Talpin, Region-Based Memory Management, Information and Computation 132(2), 1997. paper
• Nick Fitzgerald, bumpalo, Rust bump allocation arena. code