Memory management: choosing a strategy

Every value a program makes needs memory, and that memory must be given back once the value is done with: not before, or the program reads memory that now holds something else, and not never, or the program leaks. Most languages settle how for you, with one strategy for every value. Cone lets you choose, variable by variable. This page tours the strategies, what each does well and badly, and what is at stake; the rest of this part shows how to use each one. Here are five rooms of one house plan, each managed a different way:

mod rooms;

import stdio use *;
import sync use Arc;
import arena use *;

struct Room {
  pub name &str;
  pub width i32;
  pub length i32;
}

// Borrows a room: it neither knows nor cares how the room's memory is managed
fn describe(r &Room) {
  print <- r.name, ": ", r.width * r.length, " square metres\n";
}

fn main() {
  // A local variable: its memory goes when main ends, at no cost
  let hall = new Room("hall", 2, 6);

  // A single owner, Uni: freed the moment its one owner goes
  let kitchen = new Uni[Room]("kitchen", 4, 5);

  // A counted owner, Rc: copies share it, and the last one frees it
  let lounge = new Rc[imm, Room]("lounge", 6, 7);
  let sameLounge = lounge;

  // Arc counts atomically, so its owners may be on several threads
  let study = new Arc[imm, Room]("study", 3, 4);

  // An arena: many values, all freed at once when the arena goes
  var plan = Arena.empty();
  let attic = plan.alloc(new Room("attic", 5, 8));

  describe(&hall);
  describe(kitchen);
  describe(sameLounge);
  describe(study);
  describe(attic);
}

It prints:

hall: 12 square metres
kitchen: 20 square metres
lounge: 42 square metres
study: 12 square metres
attic: 40 square metres

Try this: hand the kitchen to a second owner, let chef = kitchen;, before it is described. A single owner moves rather than copying, so the compiler refuses the later describe(kitchen): This variable's value has been moved out. Do the same with the lounge, and both names keep working.

Five rooms, four ways of managing memory and a local variable, and one function serves them all. That function takes a borrowed reference, &Room: it may use a room for as long as the call lasts, but it does not own one, so it neither frees a room nor pays for any of the bookkeeping that the strategies differ in. The rest of this page is about those differences.

What is at stake#

Memory goes wrong in a few well-known ways, and each strategy is a different answer to them:

• Use after free. Memory given back too soon is soon handed out again, to something else. A reference that still points there reads, or worse writes, a value that is no longer the one it meant. Its close cousins are a double free, giving the same memory back twice, and an invalid free, giving back memory that was never handed out. These are the errors that crash programs at random and let attackers in.
• Leaks. Memory never given back is lost to the program. A tool that runs for a second and exits hardly notices, since the operating system takes everything back at the end. An editor, a game or a server that runs for days grows until it fails.
• Data races. When two threads reach the same value and one of them changes it, the other may read it half changed. Who may change a value, while who else can see it, is the same question memory management asks about who may free it, and Cone answers both with one idea, the permission each reference carries.
• How much memory. Strategies also differ in how expansively they use memory: how much bookkeeping each value carries, how long memory stays held after its last use, and how much spare room a strategy needs to run well.

The division of labour is one sentence: regions and lifetimes ensure memory safety; permissions ensure data-race safety. Between them, Cone's compiler is designed to rule out the first and the third, whichever strategy a value uses: no reference outlives the value it points to, nothing is freed twice, and no two threads race on one value. The pages of this part show those checks at work. A few gaps remain today, among them a var global reached from several threads, and raw pointers, which are not yet fenced off behind the trust keyword planned for them; Safety says exactly what a clean compile promises. Leaks and memory use are not errors the compiler can see; they are what the choice of strategy is about.

The strategies, and what each costs#

Every strategy has to decide when a value can no longer be used, so that its memory can be given back. They differ in how they decide, and so in what they cost. None wins on every count, which is why no single one is right for every value.

• A single owner (Uni, and every local variable). Each value has exactly one owner. Ownership may move, but never be copied, so the value can be freed the moment its owner goes, decided when the program is compiled. Nothing is counted or traced while it runs, freeing is immediate and predictable, and no memory is held past its last owner. The cost is the shape of the data: one owner means a tree, where each value hangs from one parent. Two parents sharing a node, or a cycle, cannot be built from single owners alone, and moving values in and out of their owners takes some care.
• Reference counting (Rc on one thread, Arc across threads). Each value counts its owners. Copying an owner adds one, dropping one subtracts one, and the value is freed when the count reaches zero. Values may be shared, and are still freed promptly and fairly predictably, with a small runtime. The cost is throughput, often the worst of any strategy: every copy and drop updates a count, in memory that may be far from anything else the program is touching, and atomically for Arc. And a cycle of owners keeps its own counts above zero for ever, so it leaks unless one link of it is a weak reference.
• Tracing garbage collection (Gc, and each actor's own ActorGc). Every so often a collector traces what the program can still reach, starting from its variables, and frees the rest. Any shape of data works, cycles included, and copying a reference costs nothing. Its reputation comes from collectors that stop the whole program while they trace, causing pauses at moments nobody chose. That is one kind among many: an incremental collector works in small steps between the program's own, a generational one spends its effort on young values, since most die young, a concurrent one runs alongside the program, and an actor's own collector in Cone tidies one actor's memory between its messages, stopping no other actor. What every tracing collector pays is the work of tracing, a delay between a value's last use and its freeing (so a finalizer runs late), a larger runtime, and room: running fast can take four to six times the memory actually in use. Where data is a tangled graph and those costs are affordable, a collector is the simplest correct answer.
• Arenas (Arena, DynArena). An arena hands out memory by moving a pointer along a large block, and never frees one value: it frees everything at once when the arena itself goes. Allocation is as fast as it gets, there is no bookkeeping and no pause, and any shape of data works. The cost is memory, which only grows until the arena dies, and finalizers, which all wait for that moment. For a burst of work, one frame, one request, one compile, that is exactly right.
• Pools (Pool). A pool holds values of one type in slots of one size, reuses a slot as soon as its value is removed, and hands out references that check whether their value is still there. It is fast, reuses memory well, and lets a value be removed at any moment while others still refer to it. The cost is that every value in it has the one type.

One more way to use a value costs nothing at all: to borrow it. A borrowed reference never frees anything, so no strategy's bookkeeping applies to it, and the compiler checks that it never outlives what it borrowed. Its limit is that lifetime: a borrow cannot be kept beyond the scope it came from. And underneath them all, memory can still be managed by hand with raw pointers (Pointers), which is how new strategies are built; such code is meant to be marked as trusted, which is not built yet.

In short:

	Single owner	Counting	Tracing	Arena	Pool
Runtime cost	none	every copy and drop	tracing	none	small
Pauses	none	freeing a large structure	depends on the collector	none	none
Freed	at once	at once	later	with the arena	when removed
Memory overhead	none	a count each	several times	grows until the end	reuses slots
Shapes of data	trees	no cycles, without weak references	any	any	any, one type
Runtime size	none	small	large	small	small

Choosing, variable by variable#

Real programs want all of these at once: a game wants a pool for its creatures, an arena for each frame's scratch work and single owners for the rest; a server wants an arena per request and a few counted values shared across threads. A language with one strategy makes every value pay for the needs of the hardest ones. Cone instead lets each variable choose, by the type of its reference: Uni[Room], Rc[imm, Room], Arc[imm, Room], or a borrow into an arena. The rooms program above is that idea in miniature.

The differences are large enough to matter. Tracing and counting are flexible and nearly invisible, and are usually the slowest in throughput and the least predictable in responsiveness; an arena or a pool can be ten to twenty times faster, and a single owner is often faster still. A realtime 3-D frame has about 17 milliseconds to draw everything, and there that difference decides what a program can do.

Two things make the mixing work. A borrowed reference may point at a value whatever its strategy, so most functions take borrows, like describe, and are written once for every strategy, with none of the strategies' costs inside them: the more a program uses borrowed references instead of owning ones, the faster and more flexible it becomes. And each reference carries a permission saying what it may do, which the compiler checks the same way whatever the strategy, so safety does not depend on the choice.

Nor do you need all of this at once. A local variable and an occasional Uni or Rc take a program a long way; the other strategies are there for when a measurement, or the shape of the data, asks for them.

How this part is laid out#

It comes in two halves. The first is about using values that someone else owns, which needs no strategy at all. It assumes one fact about moves: a single owner, like any value there can only be one of, moves rather than copies (Moves, in Recipes, has the rules for such values).

• Borrowed references: lending a value instead of moving it, and what a borrow leaves its source free to do.
• Permissions: the static permissions, uni, mut, imm, ro and the rest, and how they keep threads from racing.
• Lifetime annotations: telling the compiler how long a borrow lives, where it cannot work it out.
• Borrowing into a collection or an enum: why a push waits for a borrow of an element.

The second is about the strategies themselves, each a region that owns its values:

• Regions and owning references: new, the owning reference types, and the single owner, Uni.
• When a value dies: the exact moment each finalizer runs, for a local, a temporary, a value assigned over, a value in a region, an enum and a global.
• Reference counting: Rc and Arc.
• Weak references: breaking a cycle of counted owners.
• Lock permissions: Mutex, Rwlock and Rwcell, for values several owners change.
• Arenas: scratch arenas, and dynamic arenas whose keys carry an invariant lifetime.
• Pools: the generational Pool.
• Garbage collection: Gc, and an actor's own region.
• Collections in a region: where a list's memory comes from.
• Making your own region: a region written as a struct.

You now know what each strategy costs, what the compiler guards whichever you choose, and why Cone lets every variable choose for itself. It all starts with the way of using a value that costs nothing and needs no strategy at all: borrowing it.