Cone Language Reference

Reference counting: Rc and Arc

On this page

A single owner cannot share: a song on two playlists, a texture used by many models, a node with two parents. A counted region lets one value have several owners. It counts them, and frees the value when the last one goes, promptly and predictably, with no collector. This page covers Rc, which counts on one thread, and Arc, which counts across threads, and what counting costs. Afterwards you can share values between parts of a program, and between threads:

mod playlists;

import stdio use *;
import collections use *;

struct Song {
  pub title &str;
  fn final(self &uni) { print <- "freed ", title, "\n"; }
}

alias Track = Rc[imm, Song];   // a counted owner of a song that never changes

fn main() {
  var evening = List[Track].empty();
  {
    var morning = List[Track].empty();
    morning.push(new Track("ballad"));
    let anthem = new Track("anthem");
    morning.push(anthem);        // a copy of the owner: the count is now 2
    evening.push(anthem);        // and 3
    print <- "morning has ", morning.len(), " songs\n";
  }                              // morning goes: the ballad's last owner with it
  print <- "evening still plays ", evening[0usize].title, "\n";
}                                // the anthem's last owner goes

It prints:

morning has 2 songs
freed ballad
evening still plays anthem
freed anthem

Try this: make the track a single owner, alias Track = Uni[Song];. The compiler refuses the second playlist: the anthem moved into the first (This variable's value has been moved out).

How counting works: Rc#

The Rc region keeps a count with every value it allocates. A new value's count starts at one. Every copy of an owning reference adds one, and every owner that goes, at the end of its scope or when what holds it is replaced, subtracts one. When the count reaches zero, the value is finalized and freed. In the program above, the ballad's only owner was in morning, so it went with that list; the anthem had owners in both lists and a variable, so it lived until evening went.

The permission decides whether owners may be copied at all. An Rc[T], with no permission written, is uni: the one owner, which moves, and which may later become shared (From uni, for good). An Rc[imm, T] is copied freely and never changes its value, and an Rc[mut, T] is copied freely and may change it, through any copy, on one thread.

Counting is written in Cone, not built into the compiler. Its region ref is a struct declaring RegionRef whose field is the count kept with each value, and whose methods the compiler calls when a value is allocated, when an owner is copied and when one goes (Making your own region):

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;          // an owner copied
    }
    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 scheme count atomically, so that several threads may share owners (Arc, below), or use moves and borrowing to touch the count less often.

When to count#

Counting suits shared data that is not cyclic, and that should go as soon as it is no longer needed: memory is used tightly, values are freed as soon as their last owner goes, so a finalizer runs at a predictable point, and the runtime is tiny. It pays in throughput, typically the worst of any strategy, since every copy and drop of an owner updates a count, often in memory far from anything else the program is touching. A good habit keeps that cost down: hold a counted owner where the value is kept, and hand borrows to the functions that only use it, which touch no count at all.

Its other weakness is cycles. Two values that own each other keep each other's counts above zero for ever, and an island of them, unreachable from the rest of the program, leaks. The cure is to make one link of every cycle a weak reference, which does not count as an owner: a child holds its parent weakly, say, while the parent owns its children.

Across threads: Arc#

Arc is an 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 change of the count.

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. Each thread gets an owner of its own:

mod tables;

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

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

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

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

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 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 (Error 1194: start requires A is Sendable, and Rc[imm, Table] is not Sendable: it is an owner that may be copied, and Rc does not declare ThreadSafe). So is an Arc[mut, T] one, which would let two threads change the value itself unsynchronized (it is an owner whose permission, mut, is not race-safe); What may cross a thread has the rules. A value that several threads change is shared as an Arc[Mutex, T] or an Arc[Rwlock, T], whose lock permission makes every change wait its turn.

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.

You can now share a value among several owners, on one thread or many, and know what each copy costs. Shared owners bring one danger with them, the cycle that never frees itself. Next is how to break it.