Region Strategies

Note: The RcPool and SoPool pools, and the &eventPool mut ... allocation shown for them, are not implemented: how a value is allocated in a dynamic region such as a pool is an open design question, and only the generational Pool exists. A trynew in a region value, an arena for one, is refused: whether an allocation in a region can fail is not settled. The allocRegion method behind new x[T](...) is provisional: its name and its shape are not settled. A pool's Ref is not yet paired with its own pool: used with another pool of the same type, it is checked there, and cannot reach outside that pool's memory. An Arc value has no weak references. The region declaration the first examples show is not implemented: a region is a struct that declares RegionRef. Nor is .weak on an owning reference: a weak reference is made with Weak[T].of(owner) from an Rcw owner.

To allocate a new value, we ask a region to get it done:

imm pt = new Rc[imm, Point](1, 2);  // the 'Rc' region counts references

There are many kinds of regions, each using a different strategy for allocating memory and then later safely reclaiming that memory after an object has no references that point to it. Variations in their strategies can deliver noticeably different behavior with regard to:

• Throughput. Strategies vary greatly in runtime cycles consumed by allocating, freeing, and reference bookkeeping.
• Responsiveness. Some strategies offer excellent responsiveness to realtime demands, while others can experience erratic "lag spikes" while bookkeeping activity takes place.
• Data flexibility. Some strategies support all kinds of data structures. Others limit the structures they handle well to non-cyclic or hierarchical graphs.
• Determinism. Some strategies promptly release unneeded memory and resources. Others may wait a long time between last use and release, causing memory and resources to be tied up longer than desired.
• Memory use. Some strategies use a limited amount of memory effectively. Others have higher ratios of memory allocated-to-used or fragment memory more.
• Runtime footprint. Some strategies are easily implemented with little code. Others may require the presence of large, complex runtime logic.

Cone offers a wide selection of library-implemented regions, because no one strategy handles all these criteria well. This power of choice ensures each allocated object can select the optimal region that best serves the way the program needs that object to behave.

This page does not list every possible region that can be used by a Cone program, as new ones can be defined within the language itself. Instead, this page summarizes the five popular region strategies used to allocate new objects pointed at by an owning reference. The focus is to describe the mechanism used by each of these region strategies and assess how they compare on the above criteria. In reality, each of these region strategies may be implemented by multiple concrete regions that vary somewhat in how they work (e.g., Rc might only work within a single thread, whereas Arc might allow multiple threads to share references to the same object).

How a Region Is Written#

A region is a struct that declares the built-in trait RegionRef; there is no separate region declaration. The struct's fields are the bookkeeping kept with every value the region allocates (a count, say), and its methods are the ones the compiler calls when a value is allocated, when an owning reference is copied or goes away, and when a value is freed (custom allocators describes each one). Every method is optional, and what a region leaves out says what it does:

• fn alloc(size usize) *u8 gets the memory. It answers null for a failure, rather than an Option.
• fn free(self &uni R) gives the block back. The regions in the core package give it to core's raw blocks layer (RawBlocks), the one place the heap's bytes come from, which today forwards to C's malloc, realloc and free (the heap's region and the raw blocks layer).
• A region that declares the built-in trait Move is single-owner: a copy of its reference is a move.
• A region that adds a count is a counted one: an init that sets the count to one, an aliasRef that adds one when a reference is copied, and a dealiasRef that answers whether the count reached zero when a reference goes away. It does not declare Move, and the compiler refuses a region that declares both Move and aliasRef.
• A region that declares neither aliasRef nor Move shares its references freely. With no dealiasRef either, a reference going away does nothing and the compiler never frees the value: that is the shape of a tracing collector, which frees a value once nothing reaches it.

When a region frees a value, the value is finalized first: its final, then its fields, then the region's free.

Single Owner#

The single-owner region strategy's mechanism, strengths and weaknesses derive from a very simple constraint: there is only ever one owning reference to an object it allocates. That reference may be passed around from function to function or from thread to thread, but it does so using move mechanics to ensure no copy of the reference is ever made. Because there is only one reference to the object, the memory for that value can be automatically finalized and freed when the reference expires.

Here is the simple definition of a single-owner region:

region So is Move {    // Move ensures move semantics on references, i.e. no aliasing
    pub fn alloc(size usize) Option[*u8] {
	    malloc(size);  // May use any general-purpose memory allocator
    }
	pub fn free(self &uni So) {
	    free();
	}
}

Written as the core package's So is, a region is a struct that declares RegionRef (below):

struct Solo is RegionRef, Move {    // Move ensures move semantics on references, i.e. no aliasing
    fn alloc(size usize) *u8 {
        RawBlocks.alloc(size, 16usize);  // May use any general-purpose memory allocator
    }
    fn free(self &uni Solo) {
        RawBlocks.release(self as *u8);
    }
}

Single owner is a good choice if you are looking for:

• Better throughput garbage-collected or ref-counted region strategies (as there is no runtime bookkeeping cost). Throughput will likely be worse than arenas.
• Determinism, as reclamation happens immediately after the last reference expires. Indeed, single owner is the only region strategy that allows the programmer to decide exactly when the object is to be explicitly destroyed and to support exception handling in the event of an unsuccessful destruction.
• Efficient use of memory.
• Negligible runtime footprint.

The key shortcomings are:

• Data structures are limited to hierarchical graphs. It cannot be used to construct cyclic or many directed-acyclic graphs, as these require the use of multiple references to the same node.
• Use of these references must comply with the more-constrained move mechanics. Where moves are forbidden, workarounds (such as swaps) must be employed to extract a reference.
• Multiple owning references cannot point to the same object. That said, multiple borrowed references may be temporarily obtained to this object. These are considered temporary, because the lifetime of those borrowed references is constrained to the scope they were created in.

Reference Counting#

As the name suggests, the Rc region keeps a running counter of the number of references to each allocated object. When the object is first allocated, its counter starts at 1. Every time a copy is made of an Rc owning reference, the counter is incremented. Whenever an owning reference goes out of scope, the counter is decremented. When the counter reaches 0, the object is reclaimed.

Here is the simple definition of a reference counting region, where aliasing happens automatically:

region Rc {
    pub cnt u32;
    pub fn alloc(size usize) Option[*u8] {
	    malloc(size);
    }
	pub fn init(self &uni Rc) {
	    cnt = 1;
	}
	pub fn aliasRef(self &uni Rc) {
	    ++cnt;
	}
	pub fn dealiasRef(self &uni Rc) {
	    if (--cnt == 0) {
		  free();
	    }
	}
	pub fn free(self &uni Rc) {
	    free();
	}
}

Written as a struct that declares RegionRef, the form built today:

struct Counted is RegionRef {
    cnt u32;                       // the count is the bookkeeping kept with each value
    fn alloc(size usize) *u8 {
        RawBlocks.alloc(size, 16usize);
    }
    fn init(self &new) {
        *self = new Counted(1u32);   // a new value starts with one owner
    }
    fn aliasRef(self &uni Counted) {
        cnt = cnt + 1u32;
    }
    fn dealiasRef(self &uni Counted) bool {
        cnt = cnt - 1u32;
        cnt == 0u32;               // true: that was the last owner, so free the value
    }
    fn free(self &uni Counted) {
        RawBlocks.release(self as *u8);
    }
}

Variations on this algorithm may be built to support multi-threaded use (with atomics, as Arc does) and leverage move semantics and explicit aliasing (to improve throughput).

Reference counting is a good choice if you are looking for:

• Memory utilization for non-cyclic data structures.
• Semi-determinism, as reclamation happens immediately after the last reference expires.
• Runtime footprint, as the mechanism is very simple.

The biggest shortcomings are:

• Throughput is typically the worst, due to expensive allocation and free algorithms, and frequent cache-damaging reference counts updates.
• Memory leaks due to cyclic reference counts that keep unused data islands alive forever.

To prevent cycle-based memory leaks, one can use a variation that supports weak references to make any cycle breakable. A weak reference may be obtained from any owning reference:

childnode.parent = parentnoderef.weak;

Today that variation is the rcweak package's Rcw, which counts strong owners and weak references, and a weak reference is made from a strong owner with Weak[T].of(owner) (Rcw and Weak):

childnode.parent = Weak[Parent].of(parentnoderef);

Atomic Reference Counting: Arc#

Arc is Rc whose count several threads may change at once: each change of its count is one atomic instruction. Owners of one value may be copied and dropped on different threads, and the value is finalized and freed exactly once, after the last of them goes. Its strengths and weaknesses are Rc's, with an atomic instruction in place of each plain count change.

Arc is in the sync package. It is not in core, whose names every module has, so a module names it once it folds it in, import sync use Arc (or use *), and a module that does not keeps Arc free for its own use. It is allocated as Rc is, new Arc[imm, T](...).

An Arc[imm, T] owner is the one to share between threads: hand it to thread.start, or send it over a channel. An Arc[mut, T] owner would let two threads change the value itself unsynchronized, so it may not cross. A value several threads change is shared as an Arc[Mutex, T] or an Arc[Rwlock, T], whose lock permission makes every change wait for the lock.

import stdio use *;
import thread;
import sync use Arc;

struct Table {
  pub scale i64;
  fn final(self &uni) { printStr("table gone\n"); }
}

fn work(t Arc[imm, Table]) i64 { t.scale * 2i64; }

fn main() i32 {
  imm shared = new Arc[imm, Table](21i64);
  imm a = thread.start(shared, &work);      // the thread gets an owner of its own
  imm b = thread.start(shared, &work);
  printInt(a.join() + b.join());
  printStr("\n");
  0i32;
}

This prints 84 and then table gone, once.

Arc declares the built-in trait ThreadSafe, which Rc does not: the region's own statement that its owners may be held by several threads, which only a region ref may declare. The thread check reads it. An Arc[imm, T] owner may be handed to another thread, while an Rc[imm, T] one, whose count is not atomic, is refused, and so is an Arc[mut, T] one (Race condition safety).

The count's memory ordering is what makes the finalizer safe. A copy adds one to the count with relaxed ordering. A drop subtracts one with release ordering, and the drop that reaches zero reads the count again with acquire ordering before the value dies, so everything every owner did with the value happens before its finalizer.

Arc has no weak references: the rcweak package's Weak is made only from an Rcw owner.

Tracing Garbage Collection#

A tracing GC region captures metadata about every object it allocates, including detailed information about its references to other allocated objects. Periodically, the region's runtime garbage collector will trace out all references reachable from a root set of objects (including execution stacks). Any allocated value that cannot be traced from the root is considered unreachable, and therefore is safe to automatically finalize and free.

Its region ref declares neither aliasRef nor Move, and has no dealiasRef. So copying one of its references costs nothing, and an owning reference going away does nothing at all: it is the collector, not the reference, that decides when a value dies.

Tracing GC is a good choice if you are looking for:

• Data structure flexibility, supporting all kinds of data in the same way.
• Better throughput than Rc (though slower than other regions due to its regular mark-and-sweep bookkeeping costs).
• Stable memory use over long runtimes.

The biggest shortcomings are:

• Poor responsiveness, due to unpredictable stop-the-world lag spikes.
• Poor determinism, as there can be a sizeable lag between last use and free.
• Large and complex runtime footprint, resulting from the need for sophisticated and tunable incremental, generational, and multi-threading algorithms for optimizing performance.
• Memory greedy, as optimal performance can require 4-6x more memory than the amount used.

Two collectors exist, both as library code: the collector package's Gc, the general one, and an actor's own, ActorGc.

Gc, the general collector#

The collector package's Gc is the general incremental collector: import collector; and then new Gc[mut, T](...). It is an incremental mark and sweep. It runs a step at a time inside allocation, whole on Gc.collect(), or generationally (Gc.setGenerational(true)). Details of the collectors that exist are with the traced allocators.

It is single threaded, and for use outside actors only: a Gc reference held in an actor's state or used in an actor's method is refused, as it is in a parallel each. It is discouraged. It is likely to be replaced, so new code does not build on it.

ActorGc, an actor's own region#

Inside an actor, the actors package's ActorGc is a region of the actor's own. It is collected only between that actor's messages, by a copying collector, so a collection stops no other actor and needs no write barrier and no stack scan. An actor's state leads to this region (see region values below), and new self[T](...) in the actor's methods allocates there. The reference it gives is an ActorGc[mut, T]:

import stdio use *;
import actors;

struct Node { pub n i64; pub next Option[ActorGc[mut, Node]]; }

actor Keeper {
  head Option[ActorGc[mut, Node]];

  fn init(self &new) { *self = new Self(None[ActorGc[mut, Node]]); }

  pub async do push(self, n i64) {
    head = Some[ActorGc[mut, Node]](new self[Node](n, head));   // in the actor's own region
  }

  pub async do total(self) {
    mut sum = 0i64;
    mut at = head;
    while {
      match at {
        case imm k Some[ActorGc[mut, Node]] { sum = sum + k.n; at = k.next; }
        else { break; }
      }
    }
    printInt(sum);
    printStr("\n");
  }
}

fn main() {
  imm k = new Keeper();
  k.push(1i64);
  k.push(2i64);
  k.push(3i64);
  k.total();
}

This prints 6. A bare new ActorGc[mut, T](...) names no actor, so it has no region to be in, and panics. How the region is collected, what it costs an actor, and how a collection made in it works are described with the actor's own region.

Arena#

An arena region begins life pre-allocating a large (and growable) slab of memory. This is the arena. Every new allocation takes a bite out of this arena using a fast bump pointer. Allocations are never individually freed. The entire arena is freed as a single event when the arena dies (a scratch arena at the end of its function, a dynamic one with whatever holds it), and each value in it that needs finalizing is finalized then, newest first.

Arena region is a good choice if you are looking for:

• Blazing-fast throughput. Bump pointer allocation is much faster than malloc. Even better, there are no free nor runtime bookkeeping costs.
• Excellent realtime responsiveness, as memory management never causes lag spikes.
• Data structure flexibility, supporting all kinds of data in the same way.
• Minimal runtime footprint.

The biggest shortcomings are:

• Memory use grows without bounds, due to individual objects never being freed. A growable collection made in an arena (new a[List[i32]](16)) leaks the block it outgrows whenever it cannot grow in place, until the arena dies, and the larger the block, the more is held.
• Poor determinism for finalizers, as objects are only finalized when the arena dies.

An arena region is a surprisingly good fit for a limited-lifetime program that allocates a lot of small objects but wants optimal performance. This applies well to many command-line tools, including compilers.

Allocating in an arena#

An arena is a value of the arena package: mut a = Arena.empty(). A value is allocated into it with a.alloc(value), which returns a borrowed &mut reference to the value there. The same allocation is written with new, the arena in its head and the type in brackets, new a[Node](1, 2), which the compiler reads as a.alloc(new Node(1, 2)) and so answers what that call does. Writing new a[mut, Node](1, 2) does the same: mut is all an arena lends.

import stdio use *;
import arena use *;

struct Node {
  pub a i64;
  pub b i64;
  fn final(self &uni) { printStr("final "); printInt(a); printStr("\n"); }
}

fn main() i32 {
  mut ar = Arena.empty();
  imm x = ar.alloc(new Node(1, 2));         // a borrowed &mut Node
  imm y = new ar[Node](3, 4);               // the same call, written with new
  imm z = new ar[mut, Node](5, 6);          // mut is all an arena lends
  x.a = 10;
  printInt(x.a + y.b + z.a);
  printStr("\n");
  0i32;
}                                           // the arena dies: z, y, x finalized, newest first

This prints 19, and then final 5, final 3 and final 10.

A trynew in an arena is refused for now: whether an allocation in a region can fail is not settled. A block the arena cannot get is a panic.

An arena is itself a region: a type that gets its memory from a region (a collection) and is made with new a[T](...) is handed that arena's, so new a[List[i32]](16) keeps the list's words and its block in the arena. The block grows in place while it is the arena's last and the room is there, otherwise it is copied to a new one and the old one abandoned, held until the arena dies, and giving one back does nothing (the details).

A scratch arena#

An arena held in a local variable is a scratch arena. Its references are borrows with that variable's lifetime, so they may be passed down to any function called while the scratch lives, and a function handed the arena, &mut Arena, can allocate into it for its caller. Returning one, or assigning it where it would outlive the arena, is refused.

The arena declares NoLoanMut, so an allocation loans nothing else of it and any number of allocations may be live at once (see borrowed references). What an allocation held in a local keeps is the arena's life: the arena being moved, replaced or ended while one is still used is refused, whether the reference is held bare or inside a value the local holds. A value holding one is checked as the bare borrow is.

import stdio use *;
import arena use *;

struct Node { pub a i64; pub b i64; }

fn fill(ar &mut Arena) &mut Node { ar.alloc(new Node(7, 8)); }

fn main() i32 {
  mut ar = Arena.empty();
  imm x = ar.alloc(new Node(3, 4));
  imm y = fill(&mut ar);                    // lent to a function that allocates
  printInt(x.a + y.b);                      // 11: both are live at once
  printStr("\n");
  0i32;
}

These are refused:

fn make() &mut Node {
  mut ar = Arena.empty();
  ar.alloc(new Node(3, 4));                 // returned borrow outlives the arena
}

struct Holder { pub n &mut Node; }
fn hold() Holder {
  mut ar = Arena.empty();
  new Holder(ar.alloc(new Node(3, 4)));     // a value holding one is checked as the bare borrow is
}

fn main() {
  mut ar = Arena.empty();
  imm x = ar.alloc(new Node(3, 4));
  ar = Arena.empty();                       // replacing the arena while x is used
  printInt(x.a);
}

A dynamic arena#

An arena that is itself a value may live as long as a local variable does, a scratch arena whose references are ordinary borrows, or travel: a dynamic arena, the package's DynArena, may be returned, stored and passed, its values with it. A reference into a dynamic arena cannot be a borrow, which ends with a scope, so it is a key: a reference carrying the arena's invariant lifetime, which reaches nothing on its own.

mut a = DynArena.empty() mints a brand of its own, an invariant lifetime, and a.alloc(value), or new a[T](...), returns a key of that lifetime, &'=a mut T, which goes anywhere. The arena is the lock: a[key] reaches what a key names, and only where the two carry the same invariant lifetime, which the compiler checks at no cost at run time. In set position (a[key] = v, a field or a method through it) it writes the value. Each arena made has a lifetime of its own, so one arena's key never opens another's:

import stdio use *;
import arena use *;

struct Node['=a] { pub val i64; pub next Option[&'=a mut Node['=a]]; }
struct Chain['=a] { pub ar DynArena['=a]; pub first Option[&'=a mut Node['=a]]; }

fn build(n i64) Chain['=a] {
  mut ar = DynArena.empty();            // a brand of its own
  mut head Option[&'=a mut Node['=a]] = None[&'=a mut Node['=a]];
  mut i = 0i64;
  while i < n {
    head = Some(ar.alloc(new Node(i, head)));
    i = i + 1;
  }
  new Chain(ar, head);                  // the arena leaves with its keys
}

fn sum(c &Chain['=a]) i64 {
  mut total = 0i64;
  mut at = c.first;
  while {
    match at {
      case imm k Some[&'=a mut Node['=a]] {
        total = total + c.ar[k].val;    // read through the arena
        at = c.ar[k].next;
      }
      else { break; }
    }
  }
  total;
}

fn main() i32 {
  imm c = build(5);
  printInt(sum(&c));                    // 10
  printStr("\n");
  mut a = DynArena.empty();
  imm key = a.alloc(5);                 // a key to an i32
  a[key] = 2;                           // in set position: write
  printInt(*a[key]);                    // 2
  printStr("\n");
  0i32;
}

A key used with another arena's, b[key], is refused, and so is reaching through a key on its own, *key.

Region Values: the Head of a new#

A construction whose head is a region value rather than a type, new a[Node](1, 2), allocates in that value's region. The head must be a region value, or a value that leads to one:

• A region value is a value whose type is a struct whose first field is a public *MemRegion, as an Arena's and a DynArena's are.
• A value that leads to one has a type with an allocRegion method giving the region value, and new x[T](...) is x.allocRegion().alloc(new T(...)). The head's call is made again to hand the region to a type that gets its memory from one, so it should lend nothing still borrowed when it is called again.

Any other head is refused. An actor's state leads to the actor's own garbage-collected region (ActorGc), which is how new self[T](...) allocates there.

import stdio use *;
import arena use *;

struct Node { pub a i64; pub b i64; }

struct Scene {
  pub ar Arena;
  pub fn allocRegion(self &mut) &mut Arena { &mut ar; }
}

fn main() i32 {
  mut s = new Scene(Arena.empty());
  imm n = new s[Node](1, 2);                // s.allocRegion().alloc(new Node(1, 2))
  printInt(n.b);                            // 2
  printStr("\n");
  0i32;
}

Pool#

The mechanism for pools derives from this constraint: all objects in a pool have the same type and size. A pool region begins with a pre-allocated (and growable) memory area that is logically partitioned into identically-sized slots. Allocating space for a new object is efficient: it either reuses a slot found on a linked-list of free slots, or else uses a bump pointer to carve out a new slot from the unused area.

The generational Pool#

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

• p.add(value) returns a Ref[T], a slot and a generation. A Ref owns nothing and is copied freely.
• 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.
• p[r] and &mut p[r] borrow the value, ending the program if it has been removed.

import stdio use *;
import pool use *;

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

fn main() i32 {
  mut p = Pool[Event].empty();
  imm a = p.add(new Event(1));          // a Ref[Event]: a slot and a generation
  imm b = p.add(new Event(2));
  imm 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 imm e Some { printStr("alive\n"); }
    case is None { printStr("gone\n"); }
  }
  match p.get(b) {
    case imm 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. Reading p[a] after p.remove(a) ends the program with a panic.

A borrow from p[r] or &mut p[r], or the Option that p.get(r) or p.getMut(r) returns, held in a local keeps the pool from being changed (a remove, or an add, which may move every value), moved or ended while the borrow is used, and none may be returned or stored where it would outlive the pool. A pool reached through a shared path (a &mut Pool parameter, a field of self, an Rc owner) is protected the same way: a remove through it is refused while such a borrow is used.

Pools of Counted or Owned Values#

A pool region must be created before using it to allocate values:

mut eventPool RcPool[Event];

This example creates a new region called eventPool. All its allocated object have the type Event (which might be an enum type). This pool is an RcPool, which means references to pool-allocated objects are reference-counted, thereby determining when to free the object. An SoPool would use single-owner references, and so on.

Once a pool region is defined, the region may be specified to allocate a new value:

imm newevent = &eventPool mut Event.QuitEvent;

Pools are a good choice if you are looking for:

• Decent throughput. Pool-based allocation and free is faster than any strategy other than arenas.
• Memory efficiency. Pools are very good at reusing reclaimed memory.
• Responsiveness and determinism varies according to the reference freeing mechanism: SoPool and RcPool will do pretty well.
• Minimal runtime footprint.

The biggest shortcoming is:

• All values must have the same type.

When a program has a large number of objects of the same type being regularly allocated and freed, as is true in many games, pools can be very useful strategy. This is particularly true when functions process all objects sequentially in a cache-friendly way.