Cone Language Reference

Garbage collection: Gc and an actor's own region

On this page

Some data is a tangle: a graph whose nodes point at each other every which way, cycles and all, with no natural owner for anything. Single owners cannot build it, counting leaks its cycles, and an arena never lets any of it go. A tracing garbage collector handles it with no thought from the program: every so often it finds what the program can still reach, and frees the rest. This page covers how tracing works, what it costs, and the two collectors Cone has: Gc, and the one every actor has of its own. Afterwards you can choose a collector where it is the right tool, and know what you are paying:

mod ring;

import stdio use *;
import collector;

// Two people who each point at the other: a cycle no count could free
struct Person {
  pub id i64;
  pub friend Option[Gc[mut, Person]];
  fn final(self &uni) { print <- "collected person ", id, "\n"; }
}

fn befriend() {
  let a = new Gc[mut, Person](1, None[Gc[mut, Person]]);
  let b = new Gc[mut, Person](2, Some(a));
  a.friend = Some(b);                    // the cycle is closed
  print <- "made a pair\n";
}                                        // nothing reaches them now

fn main() {
  befriend();
  Gc.collect();                          // a whole collection: the pair is unreachable
  print <- "done\n";
}

It prints:

made a pair
collected person 2
collected person 1
done

Try this: take out Gc.collect(). The program now ends before any collection has run, and neither finalizer prints: a collector frees a value when it gets round to it, not when the value's last reference goes.

How tracing works#

A tracing region keeps information about every value it allocates, including where each one holds references to other values in the region. From time to time its collector traces every reference reachable from a set of roots, the program's variables, on the stack and elsewhere. Any value it cannot reach can never be used again, so it is finalized and freed. Cycles are no problem: the pair above point at each other, but nothing reaches either of them.

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 (Single owner, shared and counted).

Collectors come in many kinds, and the old picture of a program frozen while its whole heap is traced is only the simplest. An incremental collector does its work a little at a time, between the program's own steps. A generational one spends its effort on young values, since most values die young. A concurrent one runs beside the program on other threads. And a collector per actor tidies one actor's memory between its messages, stopping nothing else.

What every kind gives is flexibility: any shape of data, handled the same way, with nothing for the program to decide, and steady memory use over a long run. Throughput is better than counting's, though below the other strategies', because of the tracing. What every kind costs:

  • Responsiveness. Some tracing work has to happen at moments the program does not choose; a simple collector stops the program for it, and even an incremental one adds work to the steps it runs in.
  • Determinism. A value is freed some time after its last use, so a finalizer runs late, which matters when a value holds something scarce, like a file.
  • Runtime. A collector that performs well, incremental, generational and safe with threads, is large and complex, and needs tuning.
  • Memory. Running fast can take four to six times the memory actually in use.

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, which works a bounded step at a time inside allocation once the heap passes its trigger, and whole on Gc.collect(). Run generationally (Gc.setGenerational(true)), what survives a collection is old, and the collections after it are minor: they mark and sweep only the young values, the write barrier staying on between them so that an old value's new young child is found. It runs a dead value's finalizer one collection before it frees the value, so a finalizer may still read the Gc values it holds. A finalizer runs some time after its value became unreachable, when a collection's step reaches it, not at a moment the program chooses. Gc.step(work) runs some collection work on demand, and Gc.setStress(true) a step at every allocation, for testing.

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 (Error 1389: A traced reference (a Gc, for example) cannot be used inside an actor or a parallel each ... Use Gc only in code that runs on a single thread; in an actor, allocate with 'new self[T](...)' and hold an ActorGc). It is discouraged. It is likely to be replaced, nothing else in Cone's packages depends on it, and new code does not build on it.

A traced value may not hold a borrowed reference, even a string literal's &str: it lives as long as it is reached, past any lifetime a borrow is checked against, and its trace cannot see a borrow (Error 1173). It may hold Rc and Uni owners, which its finalizer releases. Where else a traced reference may and may not be held is with traced regions.

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 scan of a stack. An actor's state leads to this region (Region values), and new self[T](...) in the actor's methods allocates there. The reference it gives is an ActorGc[mut, T]:

mod keeper;

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) {
    var sum = 0i64;
    var at = head;
    while {
      match at {
        case let k Some[ActorGc[mut, Node]] { sum = sum + k.n; at = k.next; }
        else { break; }
      }
    }
    print <- "total: ", sum, "\n";
  }
}

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

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

In the terms of Making your own region: ActorGc declares the built-in trait ActorLocal (a provisional name) beside Traced. Its references stay in one actor, no stack is scanned for its roots, and it declares no writeBarrier, so a reference behind an Rc is traced. The compiler refuses a traced region's reference inside an actor or a parallel each unless the region declares ActorLocal; there, a read-only reference counts as Shareable, and none may be made.

You can now hand a tangled graph to a collector, keep an actor's data in a region no other actor waits for, and weigh what collection costs. That completes the strategies. The last two pages go underneath them: where a collection's own memory comes from, and how to write a region of your own.