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)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:
| Type | Stored as |
|---|---|
int, float, bool, ptr | the value itself |
| struct | its fields, side by side (a plain C struct) |
| enum | a 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])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 GCOne 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
paralleltasks and server threads, and any thread may free any block. - When
mainreturns, the program exits without releasing whatmainstill 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 withTERN_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))350-- memory: 35 allocations, 35 freed, 0 leaked, 0 copy-on-write copies; no GCWhy 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)[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)["alpha", "beta", "-- end"]-- memory: 2 allocations, 2 freed, 0 leaked, 1 copy-on-write copies; no GCA 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)["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:
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)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)[[1, 0, 0], [1, 1, 0], [1, 1, 1]]-- memory: 4 allocations, 4 freed, 0 leaked, 2 copy-on-write copies; no GCTwo 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:
| Code | Real copies |
|---|---|
ys = xs then only reads | 0 |
ys = xs then ys[0] = 1 | 1, of the whole array |
m2 = m then m2["k"] = 1 | 1, 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] = p | 1 per element (p.scores is shared with team[i] at the push) |
| a read-only parameter, read | 0 |
| a read-only parameter copied to a local, then written | 1 per call |
a mut or take parameter, written | 0 |
| returning a local array | 0 |
b = Bag(items), then items[0] = 9 and b.items[1] = 8 | 1 (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 = xsfollowed by a write toyscopies even ifxsis never read again. When you mean to hand a value over, say so withtake(or change it throughmut). - The compiler proves many arrays are never shared (a local created by a literal or
[v] * nthat never escapes, or amutparameter 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 memoryand 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).