Tern

How memory works

Tern has no garbage collector and no lifetimes, yet every value is freed exactly once and nothing can dangle. This page explains how: value semantics, copy-on-write storage, reference counting inserted by the compiler, read-only parameters that cost nothing to pass, and take for handing a value off. It also shows how to see when copies really happen (TERN_STATS=1), which values live forever, and the limits of the heap.

Every value is a copy

Assigning a value, passing it, returning it, or storing it in an array always behaves as if the whole value were copied. There are no references, so changing one variable can never change another:

struct Point:
    x, y: int

fn main():
    a = Point(1, 2)
    b = a                 # b is a copy of a
    b.x = 10
    xs = [1, 2, 3]
    ys = xs               # ys is a copy of xs
    ys.push(4)
    print(a, b)
    print(xs, ys)
Output
Point{x: 1, y: 2} Point{x: 10, y: 2}
[1, 2, 3] [1, 2, 3, 4]

This is the rule the rest of the language is built on. Because values can't point at each other, nothing can dangle (so there are no lifetimes to write) and nothing can form a cycle (so reference counting alone frees everything). The tour covers the rule from the programmer's side in Values, mut, and &.

Copies are lazy: copy-on-write

Copying a big array on every assignment would be slow, so Tern doesn't. What a value looks like in memory depends on its type:

TypeStored as
int, float, bool, ptrthe value itself
structits fields, side by side (a plain C struct)
enuma tag plus the fields of its variant; recursive fields are boxed
[T], str, {K: V}, fn(...)a reference to a heap block with a reference count

So b = a on a struct copies its fields, and ys = xs on an array only copies a reference and adds one to the count. The array is really copied the first time one of the sharers writes to it while the count is above one. After that each side has its own block, and further writes go straight to it.

TERN_STATS=1 prints a line of memory counters when the program ends. The last number is how many of these copies really happened:

fn main():
    xs = [0] * 1000
    ys = xs               # no copy yet: xs and ys share one block
    print(ys[999])        # reading never copies
    ys[0] = 1             # the first write to a shared block copies it
    ys[1] = 2             # ys has its own block now: written in place
    print(xs[0], ys[0], ys[1])
Output
0
0 1 2
$ TERN_STATS=1 tern run cow.tn
0
0 1 2
-- memory: 2 allocations, 2 freed, 0 leaked, 1 copy-on-write copies; no GC

One copy, for the first write. See Reading TERN_STATS below for what the other numbers mean.

Strings and maps work the same way. Strings are immutable values, so they are never copied on write at all: operations like + build a new string, and s += t appends in place when s is the only holder of its block.

Reference counting

The compiler inserts the reference-count updates itself, in the style of Perceus (the scheme used by Koka and Lean). You never write them, and there is no runtime tracing:

  • Making another holder of a block (an assignment, a struct field, an array element, a closure capture) adds one to its count.
  • When a holder goes away, the count drops by one. At zero, the block is freed right then, and so is everything it holds.
  • A variable's holdings are released when the block of code that created it ends.
  • Counts are updated atomically, so values can be shared between parallel tasks and server threads, and any thread may free any block.
  • When main returns, the program exits without releasing what main still holds: the OS takes the whole heap back at once, and freeing a big structure piece by piece would only cost time. A program built with TERN_STATS (below) does release everything, so the leak count still covers every value.

Recursive data needs no special handling. This tree is built by returning new nodes that share their unchanged subtrees with the old tree, and all of it is freed when main ends (under TERN_STATS, which the counts below come from):

enum Tree:
    Leaf
    Node(left: Tree, value: int, right: Tree)

fn insert(t: Tree, v: int) Tree:
    match t:
        Leaf:
            return Tree.Node(Tree.Leaf, v, Tree.Leaf)
        Node(l, x, r):
            if v < x:
                return Tree.Node(insert(l, v), x, r)
            return Tree.Node(l, x, insert(r, v))

fn total(t: Tree) int:
    match t:
        Leaf:
            return 0
        Node(l, x, r):
            return total(l) + x + total(r)

fn main():
    t = Tree.Leaf
    for v in [50, 30, 70, 20, 40, 60, 80]:
        t = insert(t, v)
    print(total(t))
Output
350
-- memory: 35 allocations, 35 freed, 0 leaked, 0 copy-on-write copies; no GC

Why there are no cycles and no GC

Reference counting has one classic weakness: two objects that point at each other keep each other alive forever. In Tern that can't happen. A value holds copies, never references, so a value can't contain itself, directly or indirectly. Even a closure only holds copies of what it captured when it was created, so it can't refer back to itself.

With no cycles possible, counting alone frees everything, and a garbage collector would have nothing to do. The practical results: memory is freed as soon as the last holder lets go, there are no collection pauses, and peak memory stays close to what the program actually uses. Graph-shaped data (where nodes really do refer to each other) is written as an array of nodes that refer to each other by index; see the end of the reference.

Parameters are borrowed

A read-only parameter (the default) costs nothing to pass: no copy and no count update. The function reads the caller's block directly.

This is safe because of Tern's exclusivity rule: while a call runs, nothing else can change or free the value passed to a read-only parameter. The callee can't change it (that is why parameters are read-only), and the caller can't either, because the caller is waiting for the call to return and can't pass the same variable with & in the same call. Rust gets the same effect with a borrow &T; Tern infers it for every read-only parameter.

A mut parameter is the caller's variable itself. Writes go straight to the caller's value, so a function that changes an array in place never copies it (unless the array was already shared with another variable, in which case the first write copies it once, like any other write):

fn normalize(xs: mut [float]):
    top = 0.0
    for x in xs:
        top = max(top, x)
    for i in 0..len(xs):
        xs[i] = xs[i] / top

fn main():
    levels = [2.0, 5.0, 10.0]
    normalize(&levels)
    print(levels)
Output
[0.2, 0.5, 1.0]

Moves: take and push

Sometimes a function wants to own a value: to change it and return it, or to store it. With a read-only parameter, the function has to copy it first:

fn with_footer(lines: [str]) [str]:
    out = lines           # a copy of the caller's array...
    out.push("-- end")    # ...made here, at the first write
    return out

fn main():
    lines = ["alpha", "beta"]
    lines = with_footer(lines)
    print(lines)
Output
["alpha", "beta", "-- end"]
-- memory: 2 allocations, 2 freed, 0 leaked, 1 copy-on-write copies; no GC

A take parameter moves the value in instead. The caller gives up its variable, so the function holds the only reference and can change it in place:

fn with_footer(lines: take [str]) [str]:
    lines.push("-- end")  # the function owns `lines` now: no copy
    return lines

fn main():
    lines = ["alpha", "beta"]
    lines = with_footer(lines)
    print(lines)
Output
["alpha", "beta", "-- end"]
-- memory: 2 allocations, 2 freed, 0 leaked, 0 copy-on-write copies; no GC

(A mut parameter, fn add_footer(lines: mut [str]) called as add_footer(&lines), also avoids the copy. Use take when the function builds something new from the value, or stores it somewhere.)

After a move, the variable is gone, and using it is a compile error. Pass copy(x) to keep your own copy; copy is lazy too, so it costs nothing until one side is written:

Does not compile
fn with_footer(lines: take [str]) [str]:
    lines.push("-- end")
    return lines

fn main():
    lines = ["alpha", "beta"]
    report = with_footer(lines)
    print(len(lines), report)
Compiler output
8: error: `lines` was handed to a `take` parameter earlier and is gone (pass `copy(lines)` to keep it)

xs.push(v) is not a take: it copies v the way = does, and moves it only when v isn't used afterwards. Pushing the same variable on every pass of a loop takes a snapshot each time, sharing the block until state is next written:

fn main():
    history: [[int]] = []
    state = [0, 0, 0]
    for step in 0..3:
        state[step] = 1
        history.push(state)
    print(history)
Output
[[1, 0, 0], [1, 1, 0], [1, 1, 1]]
-- memory: 4 allocations, 4 freed, 0 leaked, 2 copy-on-write copies; no GC

Two copies for three snapshots: the first write happens before anything shares state.

When copies actually happen

A copy happens only when a block is written while another holder shares it. These were measured with TERN_STATS=1:

CodeReal copies
ys = xs then only reads0
ys = xs then ys[0] = 11, of the whole array
m2 = m then m2["k"] = 11, of the whole map
p = team[0] then p.name = "zed"0 (the struct's fields were copied; the string is replaced, not written)
team[i].scores.push(0)0 (writes the element in place)
p = team[i], p.scores.push(0), team[i] = p1 per element (p.scores is shared with team[i] at the push)
a read-only parameter, read0
a read-only parameter copied to a local, then written1 per call
a mut or take parameter, written0
returning a local array0
b = Bag(items), then items[0] = 9 and b.items[1] = 81 (after the first write, each side is unique)
xs[1..], xs[..n]a new array every time (slices are copies)

Two details of the current compiler are worth knowing:

  • A variable is released at the end of its block, not right after its last use. So ys = xs followed by a write to ys copies even if xs is never read again. When you mean to hand a value over, say so with take (or change it through mut).
  • The compiler proves many arrays are never shared (a local created by a literal or [v] * n that never escapes, or a mut parameter written in a loop) and then leaves out the copy-on-write check, or does it once before the loop instead of on every write. This changes speed, never behavior.

Performance tips shows how to find and remove the copies that matter.

Immortal values

Some blocks are never freed. They are marked "immortal" in their count word, so holding them costs no count updates:

  • String literals, which are part of the program's data, not the heap (with a terminating NUL, so C can read them in place); on WebAssembly they are made when the program starts.
  • All 256 one-byte strings, so s[i] never allocates.
  • The empty array, string, and map, which are one shared block (so memory filled with zeros reads as [] or "").
  • Named functions used as values.
  • Any block with more than about 16 million holders at once: instead of overflowing, its count saturates and the block simply stays alive until the program ends.

Immortal blocks aren't leaks, and TERN_STATS doesn't count them as leaked.

Where memory lives, and its limits

  • One heap region, then arenas. Heap blocks start out in one reserved 32GB address range. Inside structs and arrays, a reference to another block is a 64-bit offset from the region's start, so once the region is full, blocks go on in more address space the runtime maps as needed: the heap can grow as far as the machine allows, as in Go and Rust. The native runtime reserves the region at a fixed address. The portable runtime (libraries, iOS, Android, --portable) reserves it wherever the OS allows, halving the size until the reservation succeeds, down to 256MB. On WebAssembly, where memory is at most 4GB anyway, references stay 32-bit (offsets in 8-byte units) and the region grows with linear memory.
  • Small blocks (up to 512 bytes) come from per-thread free lists in 8-byte size classes: no locks on the common path. Surplus freed memory moves between threads in batches, so memory freed on one thread is reused on others.
  • Big blocks (arrays and strings over 512 bytes) come from power-of-two buckets. An array that is the last block in the region grows in place when you push, with no copy. Fresh blocks of 4KB or more start a few cache lines apart, so that the headers of many same-sized arrays (the rows of a grid) don't all compete for the same cache sets.
  • Freed memory is reused, not returned to the OS, except big blocks of 64KB or more: their pages are given back once they leave a short list of recently freed blocks (the last 8, up to 64MB), which a program reallocating the same size (a snapshot per step) reuses first.
  • Sizes. An array holds at most about 4 billion elements, and a string at most 4GB.
  • Stacks. Every thread that runs Tern code reserves a 64MB stack.
  • Running out of heap prints out of memory and exits with status 3.

Reading TERN_STATS

Set TERN_STATS=1 when the program is compiled (run compiles and runs in one step). The counters are compiled in only then, so normal builds pay nothing for them.

$ TERN_STATS=1 tern run prog.tn
-- memory: 2 allocations, 2 freed, 0 leaked, 1 copy-on-write copies; no GC
  • allocations: heap blocks created. (On WebAssembly every program starts with 256, the one-byte strings, plus one per string literal it uses.)
  • freed: blocks freed.
  • leaked: allocations minus frees minus immortal blocks. It should always be 0; the test suite requires it.
  • copy-on-write copies: shared blocks copied because one holder wrote to them. This is the number to watch when tuning.

The line goes to stderr, so it doesn't mix with the program's output. For a library, call tern_stats() from the host to print the same line (see Calling C, and Tern as a library).

Source: docs/guides/memory.md. Every example on this page is compiled and run by tern x test docs.