Arenas: scratch and dynamic
On this page
A burst of work, one frame of a game, one request, one compile, often makes thousands of small values and is done with all of them at once. Freeing them one by one is wasted effort. An arena hands out memory by moving a pointer along a block, never frees a single value, and gives everything back in one go when it dies. This page covers allocating in an arena, the scratch arena held in a local, and the dynamic arena that travels with its values, whose safety rests on a lifetime of a new kind. Afterwards you can make a burst of allocation nearly free:
mod frame;
import stdio use *;
import arena use *;
struct Particle {
pub x i64;
pub v i64;
}
// One frame's scratch work: many small values, all freed together
fn step(n i64) i64 {
var scratch = Arena.empty();
var total = 0i64;
var i = 0i64;
while i < n {
let p = scratch.alloc(new Particle(i, 2)); // a bump of a pointer, no more
p.x += p.v;
total += p.x;
i += 1;
}
total;
} // the arena goes: every particle, all at once
fn main() {
print <- "frame total: ", step(1000), "\n";
}
It prints:
frame total: 501500
Try this: make step hand back one of its particles, fn step(n i64) &mut Particle. The compiler refuses it (Error 1064: Returned borrowed reference outlives the local value it points to): the particle would outlive the arena that holds it.
How an arena works#
An arena starts with a large block of memory, and grows by taking more. Every allocation takes the next piece of the block by moving a pointer along it. Nothing is freed on its own: the whole arena is freed as one event when it dies (a scratch arena at the end of its function, a dynamic one with whatever holds it), and each value in it that needs finalizing is finalized then, newest first.
That makes an arena the fastest strategy there is: allocating is a bump of a pointer, much faster than a general-purpose allocator, and there is no freeing and no bookkeeping. Nothing ever pauses, any shape of data works, cycles included, and the runtime is tiny. The price is memory: it grows without bound while the arena lives, since nothing in it is freed early, and finalizers all wait for the end. That is a surprisingly good fit for a limited-lifetime program, or a phase of one, that makes many small values and wants speed: many command-line tools, compilers among them, and the scratch work of each frame or request in a long-running program.
Allocating in an arena#
An arena is a value of the arena package: var a = Arena.empty(). A value is allocated in it with a.alloc(value), which returns a borrowed &mut reference to the value there. The same allocation is written with new, the arena in its head and the type in brackets, new a[Node](1, 2), which the compiler reads as a.alloc(new Node(1, 2)) and so answers what that call does (Region values). Writing new a[mut, Node](1, 2) does the same: mut is all an arena lends. Either way the value is built where it stays: the construction's arguments are evaluated, the arena takes room, and the construction runs in that room, with no copy of a value built elsewhere:
mod nodes;
import stdio use *;
import arena use *;
struct Node {
pub a i64;
pub b i64;
fn final(self &uni) { printStr("final "); printInt(a); printStr("\n"); }
}
fn main() i32 {
var ar = Arena.empty();
let x = ar.alloc(new Node(1, 2)); // a borrowed &mut Node
let y = new ar[Node](3, 4); // the same call, written with new
let z = new ar[mut, Node](5, 6); // mut is all an arena lends
x.a = 10;
printInt(x.a + y.b + z.a);
printStr("\n");
0i32;
} // the arena dies: z, y, x finalized, newest first
This prints 19, and then final 5, final 3 and final 10.
A trynew in an arena is refused for now: whether an allocation in such a region can fail is not settled. A block the arena cannot get is a panic.
An arena is itself a region: a type that gets its memory from a region (a collection) and is made with new a[T](...) is handed that arena's, so new a[List[i32]](16) keeps the list's own words and its block in the arena. The block grows in place while it is the arena's last and the room is there; otherwise it is copied to a new one, twice the size asked when the arena's current block has no room for it, and the old one is abandoned, held until the arena dies. Giving one back does nothing. So a growable collection made in an arena leaks each block it outgrows, until the arena dies, and the larger the block, the more is held (A collection in an arena).
A scratch arena#
An arena held in a local variable is a scratch arena. Its references are borrows with that variable's lifetime, so they may be passed down to any function called while the scratch lives, and a function handed the arena, &mut Arena, can allocate into it for its caller. Returning one, or assigning it where it would outlive the arena, is refused: the borrow rules are its whole safety (How long a borrow may live).
The arena declares NoLoanMut: an allocation loans nothing else of it, so any number of allocations may be live at once, and while one is used the arena may be allocated from again, borrowed and read. A container may declare this because it never moves what it lent, and an arena's allocations are fresh and stay where they are. (A container of values that never change could declare NoLoanRead for the read-only borrows it lends. The names are provisional, and the compiler takes the container's word for it.) What an allocation held in a local keeps is the arena's life: the arena being moved, replaced or ended while one is still used is refused, whether the reference is held bare or inside a value the local holds. A value holding one is checked as the bare borrow is:
mod scratch;
import stdio use *;
import arena use *;
struct Node { pub a i64; pub b i64; }
fn fill(ar &mut Arena) &mut Node { ar.alloc(new Node(7, 8)); }
fn main() i32 {
var ar = Arena.empty();
let x = ar.alloc(new Node(3, 4));
let y = fill(&mut ar); // lent to a function that allocates
printInt(x.a + y.b); // 11: both are live at once
printStr("\n");
0i32;
}
These are refused:
fn make() &mut Node {
var ar = Arena.empty();
ar.alloc(new Node(3, 4)); // Error 1064: Returned borrowed reference outlives
} // the local value it points to
struct Holder { pub n &mut Node; }
fn hold() Holder {
var ar = Arena.empty();
new Holder(ar.alloc(new Node(3, 4))); // Error 1064: Returned value carries a borrow of 'ar'
}
fn main() {
var ar = Arena.empty();
let x = ar.alloc(new Node(3, 4));
ar = Arena.empty(); // Error 1168: 'ar' is borrowed (by 'alloc'), and that
printInt(x.a); // borrow is used again below. It may not be changed.
}
A dynamic arena#
A scratch arena is tied to one scope, and its memory is held until that scope ends. That gets worse the longer a program runs, and worst for an arena that lives as long as the program. A dynamic (first-class) arena is the answer: one made at any time, used for a batch of values, and destroyed soon after, when none of them is needed any more. Short-lived arenas keep the speed and give memory back far sooner.
If the references into such an arena never need to outlive the scope that got them, borrows are enough, as for a scratch arena. But if the arena, or its references, must be returned, stored or passed across several scopes, a borrow is too short. The arena package's DynArena may be returned, stored and passed, its values with it. A reference into it cannot be a borrow, which ends with a scope, so it is a key: a reference carrying the arena's invariant lifetime, which reaches nothing on its own.
var a = DynArena.empty() mints a brand of its own, an invariant lifetime, and a.alloc(value), or new a[T](...), returns a key of that lifetime, &'=a mut T, which goes anywhere. The arena is the lock: a[key] reaches what a key names, and only where the two carry the same invariant lifetime, which the compiler checks at no cost at run time. In set position (a[key] = v, a field or a method through it) it writes the value. Each arena made has a lifetime of its own, so one arena's key never opens another's. Although it looks like indexing, nothing is looked up when the program runs: a[key] is the key's own pointer, and the brackets are there so the compiler can see that the arena, and so the value, is still alive:
mod chain;
import stdio use *;
import arena use *;
struct Node['=a] { pub val i64; pub next Option[&'=a mut Node['=a]]; }
struct Chain['=a] { pub ar DynArena['=a]; pub first Option[&'=a mut Node['=a]]; }
fn build(n i64) Chain['=a] {
var ar = DynArena.empty(); // a brand of its own
var head Option[&'=a mut Node['=a]] = None[&'=a mut Node['=a]];
var i = 0i64;
while i < n {
head = Some(ar.alloc(new Node(i, head)));
i = i + 1;
}
new Chain(ar, head); // the arena leaves with its keys
}
fn sum(c &Chain['=a]) i64 {
var total = 0i64;
var at = c.first;
while {
match at {
case let k Some[&'=a mut Node['=a]] {
total = total + c.ar[k].val; // read through the arena
at = c.ar[k].next;
}
else { break; }
}
}
total;
}
// The same lifetime '=a names the arena and the key, so they must match
fn bump(ar &mut DynArena['=a], key &'=a mut i64) {
ar[key] = ar[key] + 1;
}
fn main() i32 {
let c = build(5);
printInt(sum(&c)); // 10
printStr("\n");
var a = DynArena.empty();
let key = a.alloc(2i64); // a key to an i64
bump(&mut a, key);
printInt(*a[key]); // 3
printStr("\n");
0i32;
}
A key used with another arena's brackets, b[key], is refused, and so is reaching through a key on its own, *key. The lifetime must be named wherever an arena or a key is passed to a function, as bump does; naming one brand for both is what keeps the pair safe.
Invariant lifetimes#
Every lifetime on the Lifetime annotations page is a scope: a borrow of it may go anywhere inside that scope and nowhere beyond it, and two of them are ordered by which lasts longer. An invariant lifetime, written with an equals sign, '=a, is no scope. It is equal only to itself, has no order with any other lifetime, and a value carrying one may go anywhere: be returned, stored, passed. What it protects is not when a reference is used but with what: a reference of an invariant lifetime is a key, which reaches nothing on its own, and the only way in is through the value of the same invariant lifetime that made it, its lock. A dynamic arena is the lock, and the references it hands out are its keys:
struct R { pub n i64; }
struct Pair['=a] { pub left &'=a R; pub right &'=a R; }
fn sum(ar &DynArena['=a], p &Pair['=a]) i64 {
ar[p.left].n + ar[p.right].n; // Ok: the arena and the keys are one brand
}
fn main() {
var a = DynArena.empty();
var b = DynArena.empty();
let p = new Pair(a.alloc(new R(1)), a.alloc(new R(2)));
sum(&a, &p); // Ok: 3
sum(&b, &p); // Error 1240: This value carries the brand minted at one
// DynArena.empty(), and the call's other values carry the
// brand minted at another: a key unlocks only the arena it came from
p.left.n; // Error 1242: This is a key ... it gives no access on its own.
} // Reach what it names through its arena, 'arena[key]'.
ar[key] reads what the key names; in set position (ar[key] = v, ar[key].f = v, ar[key].f += 1, a method taking self &mut) it writes it. Dereferencing a key, reading its field or calling its method directly is refused: the key alone gives no access. The compiler checks every use as an identity between the arena's lifetime and the key's, so at run time ar[key] is the key's own pointer and nothing more.
Brands. Inside a function, each invariant lifetime is a brand, compared only by identity. A name its signature writes is one brand, for the whole body. A function whose result names an invariant lifetime that none of its parameters does creates a fresh one at each call site: DynArena.empty() is such a function, so two arenas are always two brands, and a key of one used with the other is refused when the program is compiled. Inside such a function, the name is the brand of whatever it returns, given by the first value the body binds to it; a body handing back two arenas of different brands as that one name is refused. A call binds each name in the callee's signature to the brand its arguments carry, and the result carries the brands so bound: a key ar.alloc(v) returns carries ar's. Recursion is fine: each activation's brands are its own.
Loops. An arena made inside a loop lasts only for that pass, so its brand is the pass's: a key from one pass may not be kept for a later one, nor carried out of the loop by a break (Error 1241: This value's brand was minted in a pass of a loop, and its arena dies with that pass). A fixed number of arenas, each with its own name, made before the loop, may be used in every pass.
Where clauses. where '=a == '=b declares two invariant names one brand, so a key of one opens an arena of the other, and a caller must give both the same. '=a >= '=b, or '=a == 'b with an ordinary lifetime, is refused.
Types. A struct declares an invariant lifetime in its brackets, as it does any other, struct Graph['=a] { ... }, so a value holding keys carries the brand, and a use names it, Graph['=a], in its place: an ordinary lifetime is not given where an invariant one is declared, and a signature always names a struct's invariant lifetimes. A body may name its signature's invariant lifetimes in a type, List[&'=a Node['=a]].empty(), and no others (Error 1243: a body names only the invariant lifetimes its signature does). A generic holds keys like any value; a key stays a key inside it. A key is a plain reference, &'=a T: a slice or a virtual reference takes no invariant lifetime. What a key names lives as long as its arena, past every scope, so it holds no borrow.
Invariant lifetimes are what make a dynamic arena safe without a check at run time: an ordinary borrow would bind the arena's values to one scope, and a counted or generational reference would pay for a check at every use. The cost is that a key is only ever useful beside its own arena, which a function's signature says by naming one brand for both.
You can now make bursts of allocation nearly free, keep an arena to one scope or send it travelling with its keys, and read a brand error. An arena never frees a single value, though. When values of one kind come and go one at a time and others still point at them, a pool is the answer.