Arena

Purpose

An arena owns a block of storage and hands out slots in it. Individual objects are never freed. When the arena drops, everything inside it goes at the same instant.

The obvious payoff is speed. Allocation becomes a pointer bump instead of a walk through a free list, and teardown becomes one operation instead of ten thousand. The less obvious payoff, and the reason arenas show up constantly in Rust specifically, is that an arena dissolves an ownership problem. Ownership in Rust is a tree: every value has exactly one owner. Real data structures are frequently graphs, with cycles and back-references and nodes pointed at from several directions. Those two facts are in direct conflict, and the arena is how you resolve it without reaching for reference counting.

Design

The arena holds a growable vector of nodes. Adding a node returns a handle, typically an index wrapped in a Newtype so it cannot be confused with any other integer in the program. Nodes refer to each other by handle rather than by reference.

That indirection is the whole trick. A cycle between two nodes is now just two integers pointing at each other, which the borrow checker has no opinion about whatsoever. The arena is the single owner; everything else holds what is effectively a private pointer that the compiler does not have to reason about.

There is a second flavor worth knowing. A typed arena hands back a genuine reference tied to the arena's lifetime, so nodes point at each other directly and no index lookup is needed. It is more ergonomic to read and harder to use, because every type that touches a node now carries a lifetime parameter, and that parameter is contagious.

Example

Autobot Robotics' task scheduler needs a dependency graph. A production run is a set of tasks where one cannot start until others have finished, and the same subtask legitimately appears as a prerequisite of several others. Drilling must precede inspection; cleanup follows both; a fixture change is a prerequisite of everything downstream of it.

In the C# scheduler this was a straightforward object graph, because a garbage collector will happily let two objects point at each other forever. The first attempt at porting it kept that shape and immediately hit the wall every Rust newcomer hits: a parent owns its children, a child needs to see its parent, and there is no way to write that without reference counting, weak pointers, and a runtime borrow check on every access.

The arena version deleted all of that. One vector owns every task, tasks name each other by TaskId, and the whole graph is freed when the run completes by dropping a single value.

#[derive(Copy, Clone, PartialEq)]
struct TaskId(usize);

struct Task {
    name: String,
    children: Vec<TaskId>,
}

struct Arena {
    nodes: Vec<Task>,
}

impl Arena {
    fn new() -> Arena {
        Arena { nodes: Vec::new() }
    }

    fn add(&mut self, name: &str) -> TaskId {
        let id = TaskId(self.nodes.len());
        self.nodes.push(Task {
            name: name.to_string(),
            children: Vec::new(),
        });
        id
    }

    fn add_child(&mut self, parent: TaskId, child: TaskId) {
        self.nodes[parent.0].children.push(child);
    }

    fn get(&self, id: TaskId) -> &Task {
        &self.nodes[id.0]
    }
}

Seen in the Wild

The Rust compiler allocates its own syntax trees and type structures into arenas, which is why so much of rustc's internal API carries an explicit lifetime. The bumpalo, typed-arena and slotmap crates are the common off-the-shelf implementations, and petgraph represents graphs by index for exactly the reason described above. Outside Rust the idea is much older: Apache and nginx both allocate per-request memory pools and release them wholesale when the request finishes, and region-based allocation has been standard practice in compilers and game engines for decades.

Comparisons

• Object Pool is the pattern arenas are most often confused with. A pool hands out one object and takes it back for reuse; an arena hands out many and takes none of them back until the end. Pools manage reuse, arenas manage lifetime.
• Composite is what you are usually building inside an arena. In a garbage-collected language a Composite is just references; in Rust an arena is the normal way to express one.
• Flyweight also reduces allocation, but by sharing identical state between objects rather than by grouping unrelated objects under a common lifetime.
• Interior Mutability is the alternative answer to the same ownership problem, and the worse one. Reach for an arena before reaching for Rc<RefCell<T>>.
• Newtype is what stops an arena handle being an ordinary usize that can be passed anywhere.

Why It Exists

Criticisms

Handles are not references, and the compiler stops helping you. An index into the wrong arena, or an index kept after the object it named was logically retired, compiles perfectly and reads the wrong data. This is the same class of bug as a dangling pointer, reintroduced by the pattern that was supposed to avoid it. Generational indices fix it by pairing each slot with a counter and checking the counter on access, which works, at the cost of the thing you adopted an arena for in the first place.

Nothing is reclaimed early. An arena that lives for the duration of the process and keeps having things added to it is indistinguishable from a leak. Arenas are a good fit for phase-shaped work with a clear end, and a bad fit for a long-running server that never reaches one.

Some implementations do not run destructors on the objects they hold, since skipping that is part of how they stay fast. If your nodes own a file handle or a socket, an arena will quietly not close them. And the lifetime-parameter flavor is genuinely viral: one arena reference in a struct forces a lifetime parameter onto that struct, everything that holds it, and everything that holds those, until it has spread through a surprising fraction of the codebase.