On this page
Shared and mutable is woven through the strategies as you placed it (introduced with Uni, carried by Rc in Permissions again: shared and mutable, and by the collector). Draft 1 already folded in the old shared-mutable page's story there, with its own example (the inspector brightening a shared material) and the refused reshape; a separate copy added tonight was taken out again.
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:

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:

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.

Measured — TBD: tonight's evidence run, workload M1/M2/M5b.

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.

Measured — TBD: tonight's evidence run, workload M3/M5b.

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.

Measured — TBD: tonight's evidence run, workload M1/M5b.

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

Try it: the refused reshape

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:

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.

Measured — TBD: tonight's evidence run, workload M4/M5b, and S1-S3 for the shared shapes. Still owed after tonight: the cascade drop of a large tree, Arc contention across cores, and cold traversal with owner copies.

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.

Measured — the binary-trees time and the 61.7 ms worst frame are from 30 Oct (one noisy laptop, a smoke run for the pause). [pending 31 Oct run]: the full re-run, the frames figures against Go, C# and the single-owner rows, and the counted-reference time on binary trees.

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.

Measured — TBD: tonight's evidence run, workload M4 (a function over a borrow, on values in every kind of owner).

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.

Measured — frames per second from a single noisy laptop run on 30 Oct, in Cone; the by-value list did not change with the size of the long-lived set behind it. [pending 31 Oct run]: the full re-run that replaces these figures, and the same workload in Rust, Go and C#.

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.

Further reading

These links point at the Cone manual:

Why Cone · Next: Concurrency