Cone Language Reference

Pools: values of one kind that come and go

On this page

A game is full of things of one kind that appear and vanish at any moment: creatures, bullets, sparks. One creature follows another for a while, and then its target dies. A single owner could free the target, but would leave the follower pointing at nothing; a counted owner would keep a dead creature alive for as long as anyone follows it. A pool keeps values of one type in slots, frees one the moment it is removed, and hands out references that check, on each use, whether their value is still there. This page covers the generational Pool and how its references stay safe. Afterwards you can let values vanish while others still refer to them:

mod chase;

import stdio use *;
import pool use *;

struct Npc { pub hp i64; pub target Ref[Npc]; }

fn report(world &Pool[Npc], who Ref[Npc]) {
  match world.get(world[who].target) {          // is the target still there?
    case let t Some { print <- "following a target with ", t.hp, " hp\n"; }
    case is None { print <- "target gone\n"; }
  }
}

fn main() {
  var world = Pool[Npc].empty();
  let orc = world.add(new Npc(10, Ref[Npc].none()));
  let elf = world.add(new Npc(8, orc));         // the elf follows the orc
  report(&world, elf);
  world.remove(orc);                            // the orc dies, whoever follows it
  report(&world, elf);
}

It prints:

following a target with 10 hp
target gone

Try this: after the orc is removed, read it directly, print <- world[orc].hp;. The program stops with a panic: pool: pool[r] of a reference whose value has been removed. Asking with get first is the safe way.

How a pool works#

A pool's mechanism follows from one constraint: all its values have the same type, and so the same size. It begins with a block of memory, which grows, divided into slots of that size. Allocating either reuses a slot from a list of free ones, or takes a new slot from the unused part of the block, and removing a value puts its slot back on the list.

That makes a pool fast, faster than any strategy but an arena, and good with memory, since freed slots are reused at once. Freeing is prompt and predictable, and the runtime is small. Values of one type side by side in memory are also quick to walk in order, which is how a game often processes all its creatures each frame. The one limit is that every value in a pool has the one type: a pool per kind of thing. An enum counts as one type, and since all its variants are one size, a pool of an enum can hand out and reclaim any of its variants interchangeably (unless the enum is @unsized).

The hard part is the references. A borrowed reference cannot be kept from one frame to the next; an owning reference would let the value be freed under the others, or keep it from being freed. So a pool hands out a kind of weak reference: asked each time whether its value is still alive, and giving a borrow of the value if it is. Underneath, a pool can tell in several ways, generational indexing, a variant of counting, or lists of subscribers; Cone's Pool uses the first.

The generational Pool#

The pool package's Pool is a generational pool: var p = Pool[T].empty(). It is a value, like an arena.

  • p.add(value) returns a Ref[T]: a slot and a generation, the count of values that slot has held. A Ref owns nothing and is copied freely, and Ref[T].none() is one that refers to nothing.
  • p.get(r) answers Some borrow of the value, or None once p.remove(r) has finalized it, even after another value takes its slot, since the slot's generation has moved on. p.getMut(r) answers a mutable borrow the same way.
  • p[r] and &mut p[r] borrow the value, ending the program with a panic if it has been removed.
mod events;

import stdio use *;
import pool use *;

struct Event {
  pub kind i64;
  fn final(self &uni) { printStr("removed "); printInt(kind); printStr("\n"); }
}

fn main() i32 {
  var p = Pool[Event].empty();
  let a = p.add(new Event(1));          // a Ref[Event]: a slot and a generation
  let b = p.add(new Event(2));
  let copy = a;                         // a Ref owns nothing and is copied freely
  printInt(p[a].kind);                  // p[r] borrows the value
  printStr("\n");
  p.remove(a);                          // finalizes it
  p.add(new Event(3));                  // takes a's slot again
  match p.get(copy) {                   // the old Ref still finds nothing
    case let e Some { printStr("alive\n"); }
    case is None { printStr("gone\n"); }
  }
  match p.get(b) {
    case let e Some { printInt(e.kind); printStr("\n"); }
    case is None { printStr("gone\n"); }
  }
  0i32;
}

This prints 1, removed 1, gone and 2, and when the pool dies, removed 3 and removed 2.

Borrows of a pool's values#

A borrow from p[r] or &mut p[r], or the Option that p.get(r) or p.getMut(r) returns, which carries the pool's loan wherever it goes, keeps the pool from being changed while it is used: no remove, and no add, which may move every value. Nor may the pool be moved or ended, and no such borrow may be returned or stored where it would outlive the pool:

var p = Pool[Pt].empty();
let r = p.add(new Pt(7));
let o = p.get(r);              // an Option holding a borrow into p
p.add(new Pt(8));              // Error 1168: 'p' is borrowed (by 'get'), and that borrow is used
match o { case let e Some { e.x; } else { 0; } }   //   again below

A pool reached through a shared path (a &mut Pool parameter, a field of self, an Rc owner) is protected the same way, by the rules for shape-changing values, since a Pool is one: a remove through it is refused while such a borrow is used (Error 1339: This call could change the shape of a 'Pool' while 'e' still holds a borrow into it).

Not built yet: pairing a Ref with its own pool. Used with another pool of the same type, a Ref is checked there, against that pool's slots and generations, and cannot reach outside that pool's memory.

Pools of counted or single owners#

Not built yet. The design also has pools whose values are freed by another strategy: an RcPool, whose references are counted and free a value when the last goes, and an UniPool, of single owners. How a value is allocated in a dynamic region such as a pool is an open design question; today the packages allocate with a.alloc(value), new a[T](...) and p.add(value), and only the generational Pool exists.

You can now keep many values of one kind, remove any of them at any moment, and hold references that find out safely when their value has gone. One strategy remains, the one that handles any shape of data with no thought at all: garbage collection.