std that avoids Rc, RefCell and lifetime headaches;typed-arena and bumpalo crates add, and the honest trade-offs of the whole approach.Vec and collections (episode 7), and smart pointers (episode 12);Learn Rust Series):Sometimes per-value ownership is simply the wrong granularity. When you build a syntax tree, a graph, or a batch of temporary objects that all live and die together, tracking each one's lifetime individually is both slow and awkward. Arena allocation flips the model on its head: you allocate everything into one big region and free the whole region at once. It is a classic systems technique that predates Rust by decades, and in Rust it happens to also dodge some of the fiercest fights with the borrow checker ;-)
We spent the last episode on variance, and I closed by promising that all of that low-level control -- raw pointers, marker fields, deciding exactly how a type relates to its parameters -- was groundwork for the moment we start hand-building allocators and pointer types. Well, here we are. Today is the allocator half of that promise. Having said that, let me first clear last episode's homework, because episode 39 left three exercises on the table.
Episode 39 was variance: covariance, contravariance, and why &mut is the strict one. There were three exercises, and here is full, runnable code for each.
Exercise 1 asked for a fn shortest<'a>(x: &'a str, y: &'a str) -> &'a str returning the shorter of two strings, called with one &'static str literal and one short local String borrow, plus a comment on which lifetime got shortened:
fn shortest<'a>(x: &'a str, y: &'a str) -> &'a str {
if x.len() < y.len() { x } else { y }
}
fn main() {
let s1: &'static str = "a long-lived static literal";
let owned = String::from("brief");
let result = shortest(s1, &owned); // s1's 'static is shortened to match &owned's 'a
println!("shorter = {result}"); // brief
}
Both parameters share one lifetime 'a, yet we pass a &'static str and a short local borrow -- two different lifetimes. It compiles because &'a str is covariant: the compiler silently shrinks s1's 'static down to the shorter lifetime of &owned so the two agree. Reading a 'static reference for a briefer window than it is actually valid can never go wrong, so the substitution is safe.
Exercise 2 wanted you to reproduce the invariance demo: declare let mut long: &'static str = "s";, then in an inner block try to assign a borrow of a local String through a &mut &'static str, read the error, and tie it back to invariance:
fn main() {
let mut long: &'static str = "static";
{
let local = String::from("temporary");
// let slot: &mut &'static str = &mut long;
// *slot = &local; // ERROR: `local` does not live long enough
let _ = &local; // (kept alive just so the block does something)
}
println!("{long}"); // still valid, precisely because that write is forbidden
}
&mut &'static str is invariant in its lifetime. If the two commented lines were allowed, *slot = &local would smuggle a short-lived reference into a slot typed &'static str; the instant the block ends and local drops, long would dangle. Invariance exists to forbid exactly that write -- writing through a loosened reference is how dangling pointers are born.
Exercise 3 asked for the three marker structs, one value of each for T = i32, and a comment naming each variance and a matching standard-library type:
use std::marker::PhantomData;
use std::cell::Cell;
struct Covariant<T>(PhantomData<T>); // covariant -- like &T, Box, Vec
struct Contravariant<T>(PhantomData<fn(T)>); // contravariant -- like a fn(T) argument
struct Invariant<T>(PhantomData<Cell<T>>); // invariant -- like &mut T, Cell
fn main() {
let _a: Covariant<i32> = Covariant(PhantomData);
let _b: Contravariant<i32> = Contravariant(PhantomData);
let _c: Invariant<i32> = Invariant(PhantomData);
println!("the PhantomData type, not T itself, selects the variance");
}
The key insight, from episode 38 and 39 both: it is the type you place inside PhantomData that chooses variance, not T on its own. PhantomData<T> produces a T (covariant), PhantomData<fn(T)> consumes a T (contravariant), and PhantomData<Cell<T>> both reads and writes (invariant). Right, homework cleared. Now, arenas.
Let me start with the problem, because the pattern only makes sense once you feel the pain it removes. Picture a compiler building an abstract syntax tree. It creates thousands of little nodes, each pointing at other nodes: an Add node points at its two operands, an If node points at a condition and two branches, and so on. In a language with a garbage collector, you just new each node and let the GC sort out the mess later. In Rust, every one of those nodes wants an owner, and the natural first attempt -- Box<Node> everywhere, or worse Rc<RefCell<Node>> when the graph is not a strict tree -- means the allocator is called once per node, the reference counts are bumped and dropped constantly, and when the tree finally dies the runtime walks the entire structure calling Drop on every single node one at a time.
A bump allocator refuses to play that game. It holds one block of memory and a single cursor. To allocate, it hands back the cursor's current position and bumps the cursor forward by the size you asked for. That is the entire allocation logic: no free list to search, no per-object header, no bookkeeping. Individual values are never freed on their own; instead, the whole arena is thrown away in one motion at the end. This makes each allocation almost free -- a pointer add and a bounds check -- and because there is no per-object Drop traffic, tearing the whole thing down is nearly free too. The price you pay is the loss of individual frees: a value lives exactly as long as the arena it was born in, no shorter.
Here is that cursor model made concrete, allocating into a pre-sized Vec so you can watch the mechanism directly:
struct Bump {
slots: Vec<u64>,
cursor: usize,
}
impl Bump {
fn with_capacity(n: usize) -> Bump {
Bump { slots: vec![0; n], cursor: 0 }
}
fn alloc(&mut self, value: u64) -> usize {
let at = self.cursor;
self.slots[at] = value;
self.cursor += 1; // bump the cursor forward -- that is the whole allocator
at
}
fn reset(&mut self) {
self.cursor = 0; // "free" everything at once, in O(1)
}
}
fn main() {
let mut bump = Bump::with_capacity(8);
let a = bump.alloc(10);
let b = bump.alloc(20);
println!("{} {}", bump.slots[a], bump.slots[b]); // 10 20
bump.reset();
println!("cursor after reset = {}", bump.cursor); // 0
}
Notice reset: it does not touch a single stored value, it just moves the cursor back to zero. The next allocation happily overwrites the old data. Freeing an entire arena's worth of objects has collapsed into one integer assignment. That is the whole magic trick, and everything else in this episode is a variation on it.
Before we build anything fancier, I want to name the second benefit, because it is the one that surprises people. In episode 12 and again in episode 33 we saw that shared, mutable, cyclic data structures are genuinely awkward in Rust: Rc<RefCell<T>> works but is verbose, has runtime cost, and leaks memory the moment you accidentally form a cycle (episode 35 was entirely about breaking those cycles with Weak). The reason is that Rust ties references to lifetimes, and a graph of interior references is precisely the shape lifetimes struggle to describe.
The arena pattern quietly removes the whole problem by replacing references with integer handles. An index is just a usize. It has no lifetime, it is Copy, and it can be stored, compared, and duplicated with zero ceremony. The borrow checker has nothing to complain about because you never handed it a self-referential web of pointers -- you handed it one flat Vec and a pile of plain integers. Let us build exactly that.
You do not need a crate for the core benefit. A Vec<T> is already a growable region of memory, so you can build an index-based arena that hands out integer handles in stead of references:
struct Arena<T> {
items: Vec<T>,
}
impl<T> Arena<T> {
fn new() -> Arena<T> {
Arena { items: Vec::new() }
}
fn alloc(&mut self, value: T) -> usize {
let index = self.items.len();
self.items.push(value);
index // a handle, not a reference
}
fn get(&self, index: usize) -> &T {
&self.items[index]
}
fn len(&self) -> usize {
self.items.len()
}
}
fn main() {
let mut arena = Arena::new();
let a = arena.alloc("hello");
let b = arena.alloc("world");
println!("{} {} (len {})", arena.get(a), arena.get(b), arena.len()); // hello world (len 2)
}
Every value lives inside one Vec, and alloc returns its index. When arena is dropped, all items are freed together in one shot -- the Vec deallocates its single backing buffer, not one allocation per element. Because the handles are just integers, they can be copied, stored in other structures, and compared freely, with none of the lifetime constraints a &T would drag along. This is the humble core of every arena crate on crates.io, and for a great many programs it is genuinely all you need.
The index approach really shines for graphs, which are notoriously painful with Rc<RefCell<...>>. Model the nodes in a Vec and the edges as indices into that same Vec, and the tangle of shared ownership simply evaporates:
struct Node {
value: i32,
edges: Vec<usize>,
}
struct Graph {
nodes: Vec<Node>,
}
impl Graph {
fn new() -> Graph {
Graph { nodes: Vec::new() }
}
fn add(&mut self, value: i32) -> usize {
let id = self.nodes.len();
self.nodes.push(Node { value, edges: Vec::new() });
id
}
fn connect(&mut self, from: usize, to: usize) {
self.nodes[from].edges.push(to);
}
fn neighbors(&self, id: usize) -> Vec<i32> {
self.nodes[id].edges.iter().map(|&e| self.nodes[e].value).collect()
}
}
fn main() {
let mut g = Graph::new();
let a = g.add(1);
let b = g.add(2);
g.connect(a, b);
g.connect(a, a); // a self-loop is trivial here: no leak, no Rc, no Weak
println!("node {a} -> edges {:?}", g.nodes[a].edges); // node 0 -> edges [1, 0]
println!("neighbors of {a}: {:?}", g.neighbors(a)); // neighbors of 0: [2, 1]
}
Look at that self-loop, g.connect(a, a). With Rc that is an instant memory leak -- a node holding a strong reference to itself never reaches a zero refcount, which is the whole reason episode 35 existed. Here it is a usize pushed into a Vec, dropped for free when the Graph dies. Cycles are trivial because nothing is reference-counted. This pattern is simpler, faster, and dramatically more borrow-checker-friendly than pointer soup for build-once, traverse-many structures like ASTs and read-mostly graphs.
The same idea evaluates an arithmetic tree, with each node referring to its children by index in stead of by pointer:
enum Expr {
Num(i32),
Add(usize, usize),
Mul(usize, usize),
}
struct Tree {
nodes: Vec<Expr>,
}
impl Tree {
fn eval(&self, i: usize) -> i32 {
match self.nodes[i] {
Expr::Num(n) => n,
Expr::Add(l, r) => self.eval(l) + self.eval(r),
Expr::Mul(l, r) => self.eval(l) * self.eval(r),
}
}
}
fn main() {
// (2 + 3) * 4 -- children are stored before their parents
let t = Tree {
nodes: vec![
Expr::Num(2), // index 0
Expr::Num(3), // index 1
Expr::Add(0, 1), // index 2 = (2 + 3)
Expr::Num(4), // index 3
Expr::Mul(2, 3), // index 4 = (2 + 3) * 4
],
};
println!("{}", t.eval(4)); // 20
}
eval walks the tree recursively, but every "pointer" is an index bounds-checked against one flat Vec. There is no Box, no lifetime annotation, no Rc clone. If you have ever tried to build a recursive enum Expr { Add(Box<Expr>, Box<Expr>) } and then found yourself fighting to share a sub-expression between two parents, the index representation is the escape hatch: two parents can hold the same child index with no ownership question to answer. This is, not coincidentally, how a lot of real interpreters and compilers actually store their trees.
Plain index arenas never reuse space -- every alloc grows the Vec, and nothing ever shrinks it. For a build-once structure that is exactly what you want. But a long-running program that allocates and releases in waves would grow forever. A small extension, a free list of returned indices, lets you recycle slots:
struct Arena<T> {
items: Vec<Option<T>>,
free: Vec<usize>,
}
impl<T> Arena<T> {
fn new() -> Arena<T> {
Arena { items: Vec::new(), free: Vec::new() }
}
fn alloc(&mut self, v: T) -> usize {
if let Some(i) = self.free.pop() {
self.items[i] = Some(v); // reuse a returned slot
i
} else {
self.items.push(Some(v)); // grow only when nothing is free
self.items.len() - 1
}
}
fn free(&mut self, i: usize) {
self.items[i] = None;
self.free.push(i);
}
}
fn main() {
let mut a = Arena::new();
let x = a.alloc("first");
a.free(x);
let y = a.alloc("second"); // reuses the slot x just vacated
println!("reused the same slot? {}", x == y); // true
}
The free list is a stack of indices that have been returned and are ready to be handed out again. alloc checks it before growing. This is the seed of what the ecosystem calls a generational arena: real crates like slotmap and generational-arena add a generation counter to every slot, so that a stale handle to a slot that was freed and then reused is detected rather than silently reading the wrong value. That extra check is worth understanding, but the free list you see above is the mechanical core of the whole idea.
Since quite some of you arrived here from the Learn Python Series, a look sideways is useful, because arenas exist in every serious systems language even though most of them do not force the concept on you. In Python (and Java, C#, Go, any garbage-collected language) you almost never write an arena, because the collector is a general-purpose memory manager running in the background: you allocate objects freely and a tracing GC reclaims them whenever it likes. The convenience is real, but so is the cost -- unpredictable pause times and a runtime constantly chasing pointers to decide what is still alive. An arena is the opposite trade: you give up per-object freedom and get, in return, allocation that is a pointer bump and deallocation that is a single reset, with zero runtime tracing.
In C, arenas are folklore -- everybody rolls their own char *pool; size_t offset; and bumps the offset, exactly like our Bump struct, but with no bounds checks and no type safety, so a mistake is undefined behaviour rather than a panic. Rust gives you the same raw speed while keeping the bounds check on the Vec index and the type on Arena<T>. And where C++ leans on custom allocators plumbed through templates, Rust's index-handle style needs no allocator machinery at all: a Vec and a usize are the whole apparatus. I argue that is a genuinely nice place to land -- the performance profile of the C trick, but a panic in stead of a silent memory-corruption bug when you get an index wrong.
Two crates turn this pattern into general infrastructure so you do not reinvent it every time. typed-arena gives you an arena whose alloc returns a real &mut T reference, tied by a lifetime to the arena itself, so you can use ordinary references in stead of integer handles:
// requires the `typed-arena` crate: shown for illustration, not compiled locally
use typed_arena::Arena;
fn main() {
let arena = Arena::new();
let a: &mut i32 = arena.alloc(1);
let b: &mut i32 = arena.alloc(2);
*a += 10;
println!("{a} {b}"); // 11 2, both valid as long as `arena` is alive
}
The trick that makes this sound is exactly the variance machinery from last episode: the returned references all borrow from the arena, so the borrow checker guarantees none of them can outlive it. bumpalo goes further and provides a general bump allocator, Bump, that allocates values of mixed types into one region and even offers arena-backed Vec and String types. That is ideal for parsers and compilers that churn through a storm of short-lived allocations during one phase and then drop them all together when the phase ends. Both crates buy you the raw speed of bump allocation with ergonomic references, at the cost of an added dependency and the same unbreakable rule: a value lives as long as its arena, and not one moment less.
I would be doing you a disservice to sell arenas as a free lunch, because they are a sharp trade, not a strict upgrade. The central limitation is baked right into the pattern: you cannot free one value early. Everything in an arena lives until the arena dies. If your objects have wildly different lifetimes -- some tiny and short-lived, some that must survive for the whole program -- an arena will pin the short-lived ones in memory long after you are done with them, and your peak memory usage suffers. Arenas are for cohorts of objects that genuinely share a lifetime, not as a blanket replacement for owned data.
There is a second, subtler catch that connects straight back to episode 20. A plain bump arena that just resets its cursor does not run Drop on the values it discards. For Copy-ish data (integers, small structs) that is perfect and precisely why it is fast. But if your values own something that must be cleaned up -- a file handle, a lock, a heap buffer with its own destructor -- a naive reset silently skips that cleanup and you leak the resource. The good arena crates are careful about this (typed-arena does run drops), and it is a question you must always ask of any allocator you build yourself. Reach for arenas for build-once, traverse-many structures of uniform lifetime -- ASTs, read-mostly graphs, per-frame scratch data in a game loop, per-request allocations in a server -- and keep ordinary ownership for everything else.
Drop traffic.usize values. They have no lifetime, they are Copy, and they let you build graphs and trees that would otherwise demand Rc<RefCell<T>> and risk cycles.Vec<T> whose alloc returns an index. Cycles and self-loops become trivial because nothing is reference-counted.typed-arena returns real &mut T references tied to the arena's lifetime; bumpalo is a general mixed-type bump allocator with arena-backed collections.Drop. Use arenas for cohorts of uniform lifetime, not as a universal replacement for ownership.Three exercises, from gentle to chewier. Type them yourself before the next episode -- allocators are one of those topics that only truly land once you have watched your own cursor move.
Arena<T> with an iter(&self) method that returns an iterator over &T for every allocated item, and use it to print all values in a small arena. (Hint: self.items.iter() is already exactly that iterator.)depth(&self, i: usize) -> usize method to the Tree from the expression-tree section that returns the height of the sub-tree rooted at index i (a Num has depth 1; an Add or Mul is 1 plus the larger of its two children's depths). Test it on (2 + 3) * 4 and confirm you get 3.Arena<T> and add a get(&self, i: usize) -> Option<&T> method that returns None for a slot that is currently free (None inside) and Some(&value) for a live one. Allocate two values, free the first, and confirm get reports the freed slot as empty and the live one as present.De groeten, en tot de volgende! ;-)
@scipio