Draft 2 for Jon, 30 Oct 2026. Not live. Three changes from draft 1 (29 Oct, kept beside this file as memory-draft1-2026-10-29.html): (1) the tracing-collector section now says what the evidence supports: good throughput, a long pause when the live set is large, a young generation as the planned fix; (2) a new section, Layout: the biggest multiple of all, on data-oriented layout, with one new example (memory_layout_values.cone, compiled and run); (3) in passing, collections are region-based too (in the “each structure chooses” section and in the arena section). Still [pending 31 Oct run]: every Measured box except the collector's (arena, pool, Uni, Rc and Arc, borrows); the counted-reference figure on binary trees; the collector's frames figures against Go and a re-run of the 61.7 ms pause; the frames-per-second figures in the layout section (one noisy laptop run, 30 Oct); the cost of a young generation, which is not built. Also still open from draft 1: the Try it and manual links, and my wording of what Cyclone, Pony, Midori and Rust taught you.
This is a long page, and it begins with how I got here. I will tell it in the order it happened to me, because the design only makes sense that way. Parts of it are unfinished, and I would rather say so as we go than have you find out.
Where this started
I set out to build Web 3D. A 3D engine is greedy twice over: it wants a great deal of memory, and a great deal of processing, on every frame, for as long as the scene is open. If I wanted it fast, and still fast when the scenes grew, a large part of the answer was how quickly a program can allocate memory, use it, and free it. And how correctly. A frame that draws a mesh somebody already freed does not draw slowly. It draws garbage, or crashes.
So before I wrote a language, I went looking for the best way to manage memory.
There is no best strategy
I did not find one. I found a lot of good ones, and each buys something by selling something else:
- Tracing garbage collection (mark-sweep, copying, generational, incremental, concurrent): it copes with any tangle of objects and asks nothing of the programmer. It pays in pauses, in tail latency, and in memory kept in reserve.
- Reference counting (deferred counting, cycle collection): a value is freed the moment its last owner lets go. It pays in count traffic on every copy, and it cannot free a cycle on its own.
- Ownership and RAII: one owner, freed when it goes out of scope. It costs nothing at run time, but it fits only data shaped like a tree.
- Arenas and regions: allocate by moving a pointer, free everything in one step. Wonderful for scratch work, and no use at all for anything that has to outlive it.
- Pools and slabs: slots of one size, reused as soon as they are returned. Fast, and only for values of one size.
- The stack: the fastest of all, for whatever lives exactly as long as a call.
And a 3D engine needs all of these. A frame's scratch results want an arena. Sparks that appear and burn out want a pool. A scene graph is a tree. A mesh is shared by hundreds of models. An editor's undo history is a tangle. Every language I knew gave me one of these strategies for everything, and the rest, if I could get them at all, as libraries that the rest of the language did not know about.
What if each data structure chose?
That was the question I could not put down. What if each data structure picked the strategy that suited it, and not just for speed, but for everything else it needs: how soon its memory comes back, how predictable that is, how much it costs to share, whether it can hold a cycle?
I did not invent my way to an answer, and I want to say so plainly, with thanks. Cyclone, above all, showed me that regions could be made safe in a language that works close to the machine. Pony showed me what it means for every reference to carry a statement of what it is allowed to do. Midori showed me how far that idea could be pushed in a system of real size. Rust showed a great many programmers that borrowing is something a person can live with. Cone's way of managing memory, which I have been calling gradual memory management, is made of two ideas I took from them and have tried to fit together:
- Regions. The strategy that manages a value's memory is part of the value's type. Each strategy is an ordinary library written in Cone, and you choose one per value, not per program. Collections are region-based too: a list or a map takes its memory from the region you give it, like anything else.
- Permissions. Every reference carries a word saying what it may do: uni, imm, mut. The compiler checks them, and they are what makes sharing safe.
Where the design works, they deserve the credit. Where it does not, the mistakes are mine.
The rest of this page takes the strategies in turn. I will use one example throughout, a small Web 3D scene, and each strategy gets the part of it that suits:
- Each frame's scratch work goes in an arena.
- The particles go in a pool.
- The scene graph's single-owned parts are Uni.
- The meshes and textures models share are Rc (Arc, across threads).
- The editor's undo graph, full of cycles, lives in a collected region.
For each strategy I try to say three things: what it is good at and what it costs, how natural it is to reach for in Cone, and its downside and what Cone does about that. The second matters most to me. In most systems languages, a pool or an arena or a collector is a library that nothing else was designed around, so people rarely reach for one. Here each is an ordinary choice, written the ordinary way, and the same borrowed references work on all of them. That is where the section on borrowed references is going.
Arenas: allocate cheaply, release it all at once
An arena is the simplest allocator I know: a block of memory and a pointer to the next free byte. To allocate, move the pointer. When the block is full, get another. For a game, the natural home is a frame's scratch work: the list of things to draw, the results of culling, the temporary vectors. Each is made, used, and finished with by the end of the frame.
Speed
Allocating is about as cheap as allocating gets. There is no search for a free spot and no bookkeeping for plain data, and values made one after another sit next to one another. The price is on the other side: nothing is freed one at a time. The whole arena goes at once. For values that need no cleanup that is a single step, however many there are. A value that does need cleanup (a string, a list, anything with a final function) gets a small header, and when the arena ends its cleanup still runs, newest first, before the blocks are released. So “free everything at once” is true of the memory. The finalizers still happen, one for each value that has one.
Convenience, and how it is written
In Cone the frame's scratch is a local variable. Allocate into it with alloc, or with new frame[...] when even a collection should live there (collections are region-based too, so the list of draw calls below is in the arena with its contents). A function that should allocate for its caller is simply handed the arena. What comes back is an ordinary borrowed reference, the same kind any other function takes, so nothing written for other data has to know it is looking at arena data.
struct Vec3 { pub x: f32; pub y: f32; pub z: f32; }
// One thing to draw this frame: made, used, and forgotten within the frame
struct DrawCall {
pub mesh: &str;
pub depth: f32;
}
// Anything handed the frame's arena may allocate into it for its caller
fn cull(frame: &mut Arena, visible: &mut List[&mut DrawCall], mesh: &str, at: &Vec3) {
if at.z > 0.0 {
visible.push(frame.alloc(DrawCall(mesh, at.z)));
}
}
fn drawFrame(n: i32) usize {
var frame = Arena.empty(); // this frame's scratch
let visible = new frame[List[&mut DrawCall]](64); // a list that lives in it too
var i = 0;
while i < n {
let at = frame.alloc(Vec3(1.0, 2.0, f32.from(i % 3))); // a bump of a pointer
cull(&mut frame, visible, "rock", at);
i += 1;
}
visible.len()
} // the frame ends: every value in the arena, freed at once
fn main() {
var frameNo = 0;
while frameNo < 3 {
print <- "frame ", frameNo, ": ", drawFrame(1000), " of 1000 objects to draw\n";
frameNo += 1;
}
}
mem_arena_frame.cone (its module and import lines left out)
frame 0: 666 of 1000 objects to draw frame 1: 666 of 1000 objects to draw frame 2: 666 of 1000 objects to draw
Try it: a frame's scratch in an arena
The trade-off
The price of an arena is in its description: scratch. If a value put there should have lived longer, it does not, and if a value put there should have died sooner, it stays until the arena goes. An arena is for work whose end you know. What I did not want was an arena that could be used wrongly, so Cone checks the one thing that goes wrong. A reference into an arena cannot outlive it:
// Refused: the draw call would outlive the frame whose arena holds it
fn nearest() &mut DrawCall {
var frame = Arena.empty();
let d = frame.alloc(DrawCall("rock", 1.0));
d
}
mem_arena_escape_refused.cone, lines 11 to 16
Error 1064: Returned borrowed reference outlives the local value it points to
--> d
^--- mem_arena_escape_refused.cone:15:3
Try it: the refused arena escape
Pools: the same size, over and over
A pool is an arena that remembers. It is a block of slots of one size. A bump pointer hands out fresh slots, and a free list remembers the slots given back, so the next allocation reuses one of those first. It is the right home for values that are all the same size, or close to it, and that come and go all the time: in my scene, particles.
Speed
Allocating is a bump or a pop off the free list, and freeing is a push onto it. Neither searches, and neither has to find a neighbor to merge with, because every slot is the same size. A slot is reused the moment its value leaves, so the memory stays compact and warm. Allocation and free are the point of a pool. I am not selling it as something to walk through: that is not what it is for, and today a pool has no walk of its own. You keep the references you were given (in a list, as the example below does) and walk those.
Convenience, and how it is written
Adding a value to a pool gives back a Ref: a small handle that owns nothing. Copy it, keep it anywhere, in a list, in the drone that is chasing the spark. When the spark burns out and its slot is given to a new spark, the old handle does not suddenly see the new one. Asking the pool answers Some spark or None, every time.
// Sparks are born and die every frame, all the same size
struct Spark {
pub x: f32;
pub life: i32;
}
// A homing drone keeps hold of the spark it is chasing, which may die first
struct Drone {
pub chasing: Ref[Spark];
}
fn track(sparks: &Pool[Spark], d: &Drone) {
match sparks.get(d.chasing) { // is the spark still there?
case let Some(s) { print <- "chasing a spark at ", s.x, "\n"; }
case is None { print <- "its spark has burned out\n"; }
}
}
fn main() {
var sparks = Pool[Spark].withCapacity(1024usize);
var live = List[Ref[Spark]].empty();
var i = 0;
while i < 8 {
live.push(sparks.add(Spark(f32.from(i), 2 + i % 3))); // reuses a freed slot if there is one
i += 1;
}
let drone = Drone(live[3usize]);
track(&sparks, &drone);
// A frame passes: each spark ages, and the ones that burn out are removed
var frame = 0;
while frame < 3 {
each r in live.iter() {
if let Some(s) = sparks.getMut(*r) {
s.life -= 1;
if s.life <= 0 { sparks.remove(*r); }
}
}
frame += 1;
}
print <- sparks.len(), " sparks left\n";
// New sparks take the burned-out slots; the drone's old Ref still finds nothing
sparks.add(Spark(9.0, 5));
track(&sparks, &drone);
}
mem_pool_particles.cone (its module and import lines left out)
chasing a spark at 3 2 sparks left its spark has burned out
Try it: sparks in a pool, and a drone that chases one
That Ref is worth remembering. It is a way to hold “the thing I was following, if it is still there” without owning it and without a dangling pointer, and we will want exactly that again in a few pages, when reference counting needs weak references.
The trade-off
Every slot is as big as the biggest value a pool holds, so a pool suits values of one kind. And the handle is not free: each time you use a Ref, the pool checks that its slot is still the one the handle was given, and each slot carries what is needed to check. That check is the cost of a handle that can never dangle. A pool that is only added to, and never removed from, is an arena with extra steps.
Uni: a single owner, and where permissions begin
A Uni[T] is the only way to reach its value. When it goes out of scope, the value is freed. That is all the bookkeeping there is: no count, no tracing, no region to name. It is the right answer for most of the scene graph. Each node owns its children, each child has exactly one parent, and the whole tree goes when its root does.
This is where the second idea comes in. Every reference in Cone carries a permission, a word for what it is allowed to do. Uni[T] carries uni: it is the one and only way in. Because there is only one, it may do anything. Read, write, move the value to someone else. Moving is the interesting part. When a Uni is passed on or stored away, it is no longer where it was, and the compiler will not let you use it there. Soon we will meet imm (many may read, nobody changes) and mut (many may hold, and any may change), each with different powers and a different price.
Speed
Nothing is counted or traced, and the value is freed at a moment you can see in the code. Each Uni is its own allocation from the system allocator, so it costs what that costs. If thousands of small values are born and die together, an arena or a pool is the cheaper home. And one thing about a tree of single owners deserves to be said out loud: when its root goes, the frees run down the whole tree, then and there. That is exactly what you want, and it is also a cost that arrives all at once.
Convenience, and how it is written
The scene graph below is nodes owning children in a list. A node has a final function that runs when it goes, which here just says so. The function that totals the triangles takes a borrowed &Node, so it neither knows nor cares that these are single-owned. Near the top, the terrain mesh is moved to a loader thread and moved back, with no copy and no lock.
struct Mesh {
pub name: Uni[str]; // the mesh owns its name
pub triangles: i32;
}
// The scene graph: each node owns its children, and each child has one parent
struct Node {
pub name: &str;
pub mesh: Option[Uni[Mesh]];
pub children: List[Uni[Node]];
fn final(self: &uni) { print <- "freed ", name, "\n"; }
}
fn node(name: &str, mesh: Option[Uni[Mesh]]) Uni[Node] {
Uni[Node](name, mesh, List[Uni[Node]].empty())
}
// Borrows a node: it walks the tree whoever owns it
fn triangles(n: &Node) i32 {
var total = 0;
if let Some(m) = &n.mesh { total += m.triangles; }
each c in n.children.iter() { total += triangles(*c); }
total
}
// Runs on a loader thread: the terrain was moved here, and is moved back
fn bake(t: Uni[Mesh]) Uni[Mesh] {
t.triangles = t.triangles * 4; // refine it: nobody else can see it meanwhile
t
}
fn main() {
let raw = Uni[Mesh]("terrain", 90000);
let loader = thread.start(raw, &bake); // moved to another thread: no copy, no lock
let terrain: Uni[Mesh] = loader.join();
let world = node("world", None[Uni[Mesh]]);
world.children.push(node("ground", Some(terrain)));
let house = node("house", Some(Uni[Mesh]("walls", 2400)));
house.children.push(node("door", Some(Uni[Mesh]("door", 120))));
world.children.push(house); // moved into the tree
print <- "the world has ", triangles(world), " triangles\n";
} // world goes: the whole tree, at once
mem_uni_scene.cone (its module and import lines left out)
the world has 362520 triangles freed world freed ground freed house freed door
Try it: the scene graph, one owner per node
That move is what makes it safe. Once raw has been handed to the loader, there is nothing left on this side to touch it with, and the compiler says so if you try:
fn main() {
let raw = Uni[Mesh]("terrain", 90000);
let loader = thread.start(raw, &bake);
// Refused: raw moved to the loader thread, so nothing is left here to race with it
print <- raw.triangles, " triangles\n";
let terrain: Uni[Mesh] = loader.join();
print <- terrain.triangles, " triangles\n";
mem_uni_moved_refused.cone, lines 16 to 22
Error 1048: This variable's value has been moved out. It is no longer there to use.
--> print <- raw.triangles, " triangles\n";
^--- mem_uni_moved_refused.cone:20:12
Try it: using a Uni after it has moved
The trade-off
One owner means a tree, not a graph. The moment two things want to hold the same value, a Uni says no, and the compiler says so at the second use (we will see that message in the section on cost). Much of what feels like sharing is really lending: handing a node to a function for the length of a call. Borrowed references, a few pages on, make that free. When two things really must own, the next strategy is the one.
Rc and Arc: shared, and counted
A mesh is shared by every model that draws it, and should go away only when the last of them lets go. Someone has to decide when that is, and reference counting decides it: every owner adds one to a count, every owner that goes subtracts one, and whoever brings it to zero frees the value. Rc counts on one thread. Arc counts atomically, so its owners may be spread across several.
Convenience, and how it is written
I wanted this to read like what a C# or Java programmer expects of a shared object. A type alias does most of it. Name the strategy once, and every use after that is the alias:
struct Mesh {
pub name: Uni[str];
pub triangles: i32;
}
struct Layer {
pub texture: Uni[str];
pub scale: f32;
}
struct Material {
pub name: Uni[str];
pub tint: f32;
pub layers: List[Layer];
pub edits: i32;
}
// How models hold what they share, named once
alias MeshRef = Rc[imm, Mesh]; // shared, never changed
alias MaterialRef = Rc[mut, Material]; // shared, and anyone holding it may change it
struct Model {
pub mesh: MeshRef;
pub material: MaterialRef;
pub x: f32;
}
// An editor's inspector panel holds the same material the models do, and changes it
struct Inspector {
pub editing: MaterialRef;
fn brighten(self: &mut, amount: f32) {
let top = &mut editing.layers[0usize]; // a borrow into the material's layers
top.scale *= 2.0;
editing.tint += amount; // the material is written while top is held
editing.edits += 1;
top.scale += 0.5;
}
}
// Borrows: draw neither knows nor cares that these are counted
fn draw(m: &Mesh, mat: &Material, x: f32) {
print <- m.name, " at ", x, " in ", mat.name, ", tint ", mat.tint, ", scale ", mat.layers[0usize].scale, "\n";
}
fn main() {
let rock = MeshRef("rock", 1200);
let stone = MaterialRef("stone", 0.5, List[Layer].empty(), 0);
stone.layers.push(Layer("granite.png", 1.0));
var scene = List[Model].empty();
scene.push(Model(rock, stone, 1.0)); // two models share one rock and one stone
scene.push(Model(rock, stone, 2.0));
let bark = MaterialRef("bark", 0.3, List[Layer].empty(), 0);
bark.layers.push(Layer("bark.png", 1.0));
scene.push(Model(MeshRef("tree", 800), bark, 3.0));
var inspector = Inspector(stone);
inspector.brighten(0.25); // every model with stone sees the change
each m in scene.iter() {
draw(m.mesh, m.material, m.x);
}
print <- stone.edits, " edit to stone\n";
}
mem_rc_assets.cone (its module and import lines left out)
rock at 1 in stone, tint 0.75, scale 2.5 rock at 2 in stone, tint 0.75, scale 2.5 tree at 3 in bark, tint 0.3, scale 1 1 edit to stone
Try it: models sharing a rock and a stone
MeshRef("rock", 1200) constructs a shared mesh the way a constructor does elsewhere, and two models hold the same rock by being given the same reference. The strategy shows in exactly one line each, in the alias. And look at draw. It takes a borrowed &Mesh and is handed an Rc-owned one without ceremony. We will come back to why that matters.
Permissions again: shared and mutable
The two aliases differ by a word. Rc[imm, Mesh] is shared and never changed. Rc[mut, Material] is shared and may be changed by any holder, and the example uses that. The inspector panel and every model hold the same stone material, and brighten writes to it while the models see the change at once. There is no lock around it, no cell that checks at run time, and nothing is copied in or out.
Look at brighten. It holds a borrow top into the material's list of layers, and writes to the material's other fields while it holds it. That is allowed. What would not be safe is changing the list's shape while the borrow is alive: a push may move the whole list to a bigger block, and top would point at memory that is gone. So that is what the compiler refuses, and it knows which calls reshape what from the types' own methods:
struct Inspector {
pub editing: MaterialRef;
fn brighten(self: &mut, amount: f32) {
let top = &mut editing.layers[0usize]; // a borrow into the material's layers
top.scale *= 2.0;
editing.tint += amount;
editing.layers.push(Layer("moss.png", 1.0)); // refused: top is used again below
editing.edits += 1;
top.scale += 0.5;
}
}
mem_rc_shape_refused.cone, lines 34 to 44
Error 1339: This call could change the shape of a 'List' while 'top' still holds a borrow into it (made by '&[]' at 37:15, through a path other references share), used again at 42:5: 'push' reshapes the 'List' it is called on: it writes a field of it, runs a finalizer of an element, or moves an element out. A 'List' that changes shape may move or free what it lent. Reach it through an 'imm' or 'uni' reference, or copy what is needed out before this call.
--> editing.layers.push(Layer("moss.png", 1.0)); // refused: top is used again below
^--- mem_rc_shape_refused.cone:40:19
The fix is to finish with top first, or to copy out what you need. This is the shape rule, and it is what lets mut be shared at all. The same rule serves collected data in a few pages. As for races: which of these may cross to another thread is the subject of the concurrency page. In one sentence, a uni moves, an imm may be shared, a mut stays on its own thread, and the compiler checks all three.
Arc, across threads
An Rc counts without any atomic operation, which is why it must stay on its thread. The compiler holds that line, and says what would be allowed instead:
// Refused: an Rc counts on one thread, so it may not be handed to another
alias TextureRef = Rc[imm, Texture];
fn buildMips(t: TextureRef) i64 {
t.width * t.height / 3
}
fn main() {
let atlas = TextureRef("atlas.png", 2048, 2048);
let a = thread.start(atlas, &buildMips);
let mips: i64 = a.join();
print <- mips, "\n";
}
mem_rc_thread_refused.cone, lines 12 to 24
Error 1194: start requires A is Sendable, and Rc[imm, Texture] is not Sendable: it is an owner that may be copied, and Rc does not declare ThreadSafe: its copies could not be made and dropped on several threads at once. It may cross as a uni owner, which moves it, or as an owner of a region declaring ThreadSafe, such as Arc.
--> let a = thread.start(atlas, &buildMips);
^--- mem_rc_thread_refused.cone:21:17
Try it: the refused Rc on a thread
Change the alias to an Arc and it runs. Each thread is given an owner of its own, and every owner copy is an atomic operation. The functions that do the work take borrows and touch no count at all:
struct Texture {
pub name: Uni[str];
pub width: i64;
pub height: i64;
}
// How the renderer and its worker threads share a texture, named once
alias TextureRef = Arc[imm, Texture];
// Borrows: no count is touched, and no atomic, however hot this loop gets
fn texels(t: &Texture) i64 {
t.width * t.height
}
// Runs on a worker thread, which holds an owner of its own
fn buildMips(t: TextureRef) i64 {
var total = 0i64;
var w = t.width;
var h = t.height;
while w > 0 && h > 0 {
total += w * h;
w = w / 2;
h = h / 2;
}
total - texels(t)
}
// Runs on another worker thread, at the same time, on the same texture
fn uploadBytes(t: TextureRef) i64 {
texels(t) * 4
}
fn main() {
let atlas = TextureRef("atlas.png", 2048, 2048);
let a = thread.start(atlas, &buildMips); // each thread gets an owner: an atomic add
let b = thread.start(atlas, &uploadBytes);
let mips: i64 = a.join();
let bytes: i64 = b.join();
print <- atlas.name, ": ", texels(atlas), " texels, ", mips, " more in mips, ", bytes, " bytes to upload\n";
}
mem_arc_threads.cone (its module and import lines left out)
atlas.png: 4194304 texels, 1398101 more in mips, 16777216 bytes to upload
Try it: a texture shared by two threads
The trade-off, and where I do not think counting is cheap
I want to be careful here, because reference counting is often described as cheap, and I do not think that is the whole story. Four things cost, and they are the four I would look at first in your program:
- Anything that is not a DAG needs weak references. A child that points back to its parent, a widget that knows its container, an observer that watches its subject: all of them are cycles, and counting never frees a cycle. The way out is a weak reference that does not count. It works, and the example below shows what it looks like. It also means every step along a weak link has to ask whether the other end is still there.
- The cascade. When the last owner of a big structure lets go, everything below it is freed right then, in the middle of whatever you were doing. Nothing in the code says “this line takes a while”, and a frame can find itself a very long frame.
- Count writes dirty cache lines. Copying an owner writes the value's count, even if all you did with the value was read it. Walk a large graph taking an owner at each step, and each node you visit has its header line written and written back.
- Atomics, for Arc. Each copy is a read-modify-write that other cores have to agree about, and when several cores copy owners of one popular value, its count bounces between them.
None of these is a reason to avoid Rc. They are the reason it is one strategy of several, and the reason the section on borrowed references matters: it is about not paying them as often. Here is the weak-reference one in the scene, a node that knows its parent so it can work out where it is in the world:
// A scene node that knows its parent, to work out where it is in the world
struct NodeValue {
pub name: Uni[str];
pub x: f32; // relative to its parent
pub parent: Weak[NodeValue]; // the weak half of the cycle
pub children: List[SceneNode]; // the strong half
fn final(self: &uni) { print <- "freed ", name, "\n"; }
}
alias SceneNode = Rcw[mut, NodeValue];
fn adopt(parent: SceneNode, child: SceneNode) {
child.parent = Weak[NodeValue].of(parent);
parent.children.push(child);
}
// Every step up asks the weak reference whether its parent is still there
fn worldX(n: &NodeValue) f32 {
var x = n.x;
var up = n.parent.upgrade();
while {
match up {
case let Some(p) {
x += p.x;
up = p.parent.upgrade();
}
case is None { break; }
}
}
x
}
fn main() {
let world = SceneNode("world", 0.0, Weak[NodeValue].none(), List[SceneNode].empty());
let ship = SceneNode("ship", 100.0, Weak[NodeValue].none(), List[SceneNode].empty());
let turret = SceneNode("turret", 5.0, Weak[NodeValue].none(), List[SceneNode].empty());
adopt(world, ship);
adopt(ship, turret);
print <- "the turret is at ", worldX(turret), "\n";
} // the last strong owners go: the whole family is freed
mem_weak_parent.cone (its module and import lines left out)
the turret is at 105 freed world freed ship freed turret
Try it: a scene node with a weak parent
A type that has weak links is Rcw rather than Rc, a different type, and upgrade() hands back an Option because the parent might be gone. This is where I feel the weight of Rc most, and it is why the undo graph in the next section is not done this way.
Tracing garbage collection: for tangles
Some data is a tangle. Take the editor's undo history. Each edit points back to the one before and forward to the one after, so every step is a cycle. Branch the history, and a whole side branch is dropped, cycles and all. Single ownership has no tree to work with. Counting would need a weak reference in every direction. This is what tracing garbage collection is for.
The collectors come in several kinds. Mark-sweep finds what is reachable and frees the rest; its work follows the size of the heap. A copying collector moves the live data somewhere fresh, so its work follows what survived, and dead data costs nothing, but it needs room to copy into. Generational collectors bet that most values die young and collect those often and cheaply. Incremental and concurrent collectors slice the work, or run it beside the program, to shorten the pauses, and pay for it in bookkeeping on every write.
Speed
The strengths are real. Cycles and tangled graphs are no problem. Nobody has to decide who owns what. And allocation can be very fast. The weaknesses are the ones everyone knows: pauses, a bad tail on the slowest frame, and memory held in reserve and in headers. The question is only what a program that does not need a collector pays for the one that does.
In Cone the answer is: nothing, because the collector is a region like the others. The one I mean is ActorGc, the collector that each actor can keep for itself. It is a copying collector that looks at one actor's data only, and runs only between that actor's messages, so it cannot pause the rest of the program. It runs once what has been allocated since the last collection exceeds what survived it (and not under a floor, so a tiny actor does not collect constantly). Each collected value has a 24-byte header. An actor that never asks for a collected region pays one word.
Its throughput is good. On the frames workload (a game frame making thousands of small temporaries, with a large set of long-lived objects behind them) it kept level with Go's collector in a first smoke run. On binary trees, the allocation-heavy classic, it finished depth 18 in 656 ms, where single owners took 1,026 ms in an earlier run [pending 31 Oct run: both side by side, with counted references in Cone and Rust].
Its weak point is the pause. A copying collector copies what survived, so when the long-lived set is large, a collection copies all of it, in one go. In a smoke run with two million long-lived objects, the worst frame took 61.7 ms, and that frame was a full copy of the live set. A frame is meant to be sixteen milliseconds. The fix the design points to is a young generation: collect the newest values often and cheaply, and touch the old ones rarely. It is planned, not built. Until it is, the sensible use of this collector is data that is tangled and moderate in size, such as the undo history below, and not a large world kept in one actor.
Convenience, and how it is written
An actor allocates in its own region by naming itself: new self[Edit](...). After that, the edits are ordinary references. Notice c.next = Some(e). Many references to an edit may exist at once (the actor's current one, its neighbors), and any of them may write, with no lock and no weak references. That is the same shared-and-mutable rule as for Rc, and the same shape rule keeps it safe.
// One edit in the scene editor's history. Each points both ways:
// a cycle at every step, which no count could free
struct Edit {
pub what: Uni[str];
pub prev: Option[ActorGc[mut, Edit]];
pub next: Option[ActorGc[mut, Edit]];
}
// The editor's history lives in this actor's own collected region
actor History {
current: Option[ActorGc[mut, Edit]];
count: i64;
fn init(self: &new) { *self = Self(None[ActorGc[mut, Edit]], 0i64); }
// A new edit after some undos simply drops the redo branch, cycles and all:
// the collector finds it unreachable between this actor's messages
pub async fn did(self, what: Uni[str]) {
let e = new self[Edit](what, current, None[ActorGc[mut, Edit]]);
match current {
case let Some[ActorGc[mut, Edit]](c) { c.next = Some(e); }
else {}
}
current = Some(e);
count += 1;
}
pub async fn undo(self) {
match current {
case let Some[ActorGc[mut, Edit]](c) {
match c.prev {
case is None {} // nothing older to go back to
else { current = c.prev; }
}
}
else {}
}
}
pub async fn show(self) {
var at = current;
print <- "history, newest first:";
while {
match at {
case let Some[ActorGc[mut, Edit]](e) { print <- " ", e.what; at = e.prev; }
else { break; }
}
}
print <- " (", count, " edits made)\n";
}
// What the actor's collected region holds right now
pub async fn held(self) {
print <- "the region holds ", self.allocRegion().stats().objects, " edits\n";
}
}
fn main() {
actors.setStress(true); // collect after every message: a program this small would not otherwise collect at all
let h = History();
h.did("add ship");
h.did("add turret");
h.did("paint turret red");
h.undo();
h.undo();
h.did("move ship"); // the turret edits, a branch nothing reaches, are left for the collector
h.show();
h.held(); // the two turret edits, cycle and all, are gone
}
mem_actorgc_undo.cone (its module and import lines left out)
history, newest first: move ship add ship (4 edits made) the region holds 2 edits
A note on what that shows. The program turns on the collector's test mode (the setStress line) so that it collects after every message. A program this small would otherwise not collect at all. In a real program the collector decides for itself. The two turret edits point at each other and nothing else points at them, and they are gone.
Try it: an undo history, with branches dropped
The trade-off
A collection is a pause, even when it stops only one actor, and the pause grows with the actor's live data: today every collection copies all of it, which is the 61.7 ms frame above. A young generation is how I mean to fix that. A reference into an actor's collected region also stays inside that actor. It cannot be put in a message, so what leaves the actor is a value of another kind (a Uni, which moves, or an Arc, which is shared). And the collected region today belongs to actors. A collector for ordinary code outside an actor is not something I am ready to recommend yet.
Borrowed references: one function, any owner
Everything so far has been about owning. Most of a program does not own anything, though. It just uses. A borrowed reference, &T, says: use this for as long as this call lasts. You own nothing, so you free nothing. And because it has forgotten who owns the value, one function can take it from anyone.
Here is a single function, draw, drawing a mesh from seven different homes: a local, a single owner, a counted owner, a shared-across-threads owner, an arena, a pool slot, and an actor's collected region.
struct Mesh {
pub name: Uni[str];
pub triangles: i64;
}
// Borrows a mesh: one function, whoever owns the mesh and however
fn draw(m: &Mesh) i64 {
print <- " ", m.name, ": ", m.triangles, " triangles\n";
m.triangles
}
// Called deep in the renderer, still with only a borrow: nothing counted on the way down
fn drawTwice(m: &Mesh) i64 {
draw(m) + draw(m)
}
// An actor's meshes live in its own collected region, and lend the same borrow
actor Editor {
fn preview(self) {
let ghost = new self[Mesh]("ghost", 64);
draw(ghost);
}
pub async fn run(self) {
print <- "in the editor's actor:\n";
preview();
}
}
fn main() {
let sky = Mesh("sky", 2); // a local value
let terrain = Uni[Mesh]("terrain", 90000); // a single owner
let rock = Rc[imm, Mesh]("rock", 1200); // counted
let tree = Arc[imm, Mesh]("tree", 800); // counted, across threads
var frame = Arena.empty();
let debris = frame.alloc(Mesh("debris", 40)); // this frame's scratch
var sparks = Pool[Mesh].empty();
let spark = sparks.add(Mesh("spark", 2)); // a pool's slot
var total = 0i64;
total += draw(&sky);
total += draw(terrain);
total += drawTwice(rock);
total += draw(tree);
total += draw(debris);
total += draw(&sparks[spark]);
print <- total, " triangles drawn\n";
Editor().run();
}
mem_borrow_any.cone (its module and import lines left out)
sky: 2 triangles terrain: 90000 triangles rock: 1200 triangles rock: 1200 triangles tree: 800 triangles debris: 40 triangles spark: 2 triangles 93244 triangles drawn in the editor's actor: ghost: 64 triangles
Try it: one draw function, seven owners
Two things follow from this, and the second is the one I care most about.
It cuts the cost of management. A borrow carries none of any strategy's bookkeeping. When drawTwice is handed the Rc-owned rock and passes it down to draw, no count goes up and none comes down, however deep the call goes. That makes Rc the biggest winner. Its whole cost is those count writes, and a program that passes borrows through its inner loops does not make them. Arenas gain next: allocate once, and every function that sees the scratch sees an ordinary reference. And a borrow of shared data needs no atomic and no lock to read, because it cannot outlive its owner, and the compiler has already checked that.
It makes functions simpler to write. A function that only needs to look at a mesh does not have to say how the mesh is owned, or be written again when the owner changes. Library authors do not have to choose a strategy for everyone else.
The trade-off
A borrow cannot be kept. It cannot be stored in something that lives longer than its owner, or handed back from the function that owns the value; the compiler refuses, as it did for the arena. If you want to keep a reference, you need an owner: an Rc copy, a Pool ref, a place in a collected region. Most languages you have used have nothing like this, since every reference there may be kept and the runtime works out when to let go. Learning to see which references are for using and which are for keeping is a real cost, and I am asking you to pay it in exchange for the rest.
Layout: the biggest multiple of all
Everything so far chose how a value is owned and when it is freed. There is a question under it that matters more than any of those, and it is whether the value needs to be a separate allocation at all.
Consider the sparks. A pool gives each its own slot and a Uni gives each its own heap object, and either way the frame follows a pointer to every spark. A spark is five numbers. If the sparks are simply the bytes of a list, side by side, there is nothing to allocate for each one and nothing to free, and the loop that moves them walks memory in order, which is what a processor is built to do quickly. Reuse the list on the next frame and the allocator is out of the picture altogether. This is the heart of data-oriented design: arrange the data for the way it is read, and the rest follows.
// A spark is five numbers
struct Spark { pub id: i64; pub x: i64; pub y: i64; pub vx: i64; pub vy: i64; }
fn spark(frame: i64, i: i64) Spark { Spark(i, i % 97, frame % 89, 3, 0 - 2) }
fn step(s: &mut Spark) i64 {
s.x += s.vx;
s.y += s.vy;
s.id + s.x * 3 + s.y
}
// One heap object per spark: every spark is its own allocation, and its own free
fn oneObjectEach(frames: i64, perFrame: i64) i64 {
var total = 0i64;
var f = 0i64;
while f < frames {
var list = List[Uni[Spark]].empty();
var k = 0i64;
while k < perFrame { list.push(Uni[Spark](spark(f, k))); k += 1; }
each s in list.mutItems() { total += step(*s); }
f += 1;
}
total
}
// The sparks are the list's own bytes, side by side, and the list is reused every frame
fn byValue(frames: i64, perFrame: i64) i64 {
var total = 0i64;
var list = List[Spark].empty();
var f = 0i64;
while f < frames {
list.clear();
var k = 0i64;
while k < perFrame { list.push(spark(f, k)); k += 1; }
each s in list.mutItems() { total += step(s); }
f += 1;
}
total
}
fn main() {
print <- "one object each: ", oneObjectEach(3, 1000), "\n";
print <- "by value: ", byValue(3, 1000), "\n";
}
memory_layout_values.cone (its module and import lines left out)
one object each: 1945455 by value: 1945455
Try it: sparks as objects, and sparks as values
The two functions do the same work and give the same answer. Only where the sparks live differs, and the difference is the largest one in this page, larger than the gap between any two regions above. In a frames workload with twenty thousand sparks a frame, values in a reused list ran at about 26,000 to 28,000 frames a second, against about 1,100 to 1,650 for one heap object per value.
I take two things from that. The first is that choosing a region well is worth a good deal less than choosing whether to allocate. Within the one-object-per-value strategies the differences are small, and between them and a flat list of values they are large, so the first question to ask of a program's hot data is whether its lifetimes can be grouped, or even avoided. The second is that I would like Cone to make this layout easy to reach for. That means a struct-of-arrays option for a collection, switched in one place, and tools that suggest which fields to move where, so that cache locality is something the language helps with and not something you pay a specialist to arrange. None of that is built. It is on the list, and I think it is among the more important items on it.
What this costs you, and what I tried to keep small
I should say it plainly: this is more complex than one strategy. If a language gives you one collector, you have one thing to learn, its cost is paid evenly, and you can stop thinking about it. Most languages give you one strategy. The ones that give you more tend to restrict them heavily. Cone gives you six and asks you to choose, and a choice is a burden as well as a freedom. I think it is worth carrying, but I do not pretend it is free.
What I tried hard to keep small is the burden of typing it out. You have already seen the main device. A type alias names the strategy, and the code reads about as it would in C#:
// How models hold what they share, named once alias MeshRef = Rc[imm, Mesh]; // shared, never changed
mem_rc_assets.cone, lines 23 to 24
let rock = MeshRef("rock", 1200);
let stone = MaterialRef("stone", 0.5, List[Layer].empty(), 0);
stone.layers.push(Layer("granite.png", 1.0));
var scene = List[Model].empty();
scene.push(Model(rock, stone, 1.0)); // two models share one rock and one stone
scene.push(Model(rock, stone, 2.0));
mem_rc_assets.cone, lines 51 to 57
Which makes changing your mind cheap. Suppose a profile says the counting costs something, and it turns out few meshes are really shared. Change one line, alias MeshRef = Uni[Mesh];, and the constructions, the lists of models and every borrow read the same. This is the program with that line changed and one other, which I will come to:
// How models hold what they share, named once alias MeshRef = Uni[Mesh]; // was Rc[imm, Mesh]: now each mesh has one owner alias MaterialRef = Rc[mut, Material]; // shared, and anyone holding it may change it
mem_alias_uni.cone, lines 22 to 25
var scene = List[Model].empty();
scene.push(Model(rock, stone, 1.0)); // the rock has one owner now, this model; the stone is still shared
scene.push(Model(MeshRef("boulder", 3000), stone, 2.0)); // its own mesh now
let bark = MaterialRef("bark", 0.3, List[Layer].empty(), 0);
bark.layers.push(Layer("bark.png", 1.0));
scene.push(Model(MeshRef("tree", 800), bark, 3.0));
mem_alias_uni.cone, lines 55 to 60
rock at 1 in stone, tint 0.75, scale 2.5 boulder at 2 in stone, tint 0.75, scale 2.5 tree at 3 in bark, tint 0.3, scale 1 1 edit to stone
Try it: the same program with a single-owner mesh
The other change is the second model. Where two models did share a rock, the compiler shows me exactly where, at the second use:
var scene = List[Model].empty(); scene.push(Model(rock, stone, 1.0)); // two models share one rock and one stone scene.push(Model(rock, stone, 2.0));
mem_alias_uni_refused.cone, lines 55 to 57
Error 1048: This variable's value has been moved out. It is no longer there to use.
--> scene.push(Model(rock, stone, 2.0));
^--- mem_alias_uni_refused.cone:57:20
Try it: the refused second rock
I want to be honest about what that is. The compiler did not do the work for me. It told me where my design had been relying on sharing, and I had to decide, here by giving the boulder a mesh of its own. That is the bargain: a change of strategy is one line, and wherever the line changes what is true, you are shown the places.
Still to come
A few things in this page are unfinished, and I would rather list them than hide them.
- Every Measured box is waiting on a run, and so is every Try it link, which will open the example in the playground.
- The per-actor collector exists only inside actors, and a pool has no walk of its own.
- This page touches safety only lightly. Its own page covers what each check protects you from.
- Which references may cross threads is the concurrency page.
Further reading
These links point at the Cone manual:
- Memory management: choosing a strategy.
- Regions and owning references and Borrowed references.
- Reference counting, Arenas, Pools and Garbage collection.
- Permissions and shape changes.
- Making your own region.
Why Cone · Next: Concurrency