Chapter 6

Memory

Rill has no garbage collector. The compiler inserts reference-count operations following ownership rules (Perceus-style), so memory is freed the moment the last reference dies — deterministically, with no pauses. Nullary constructors (Nil, None) are static singletons and never allocate; small objects come from a pooled allocator.

When a match takes a box apart and nothing left can reach it by name, the next constructor of exactly that shape is built in that box rather than in a fresh one — so map, filter, reverse and split walk a list without allocating anything, writing each link over the link they read it from.

A type with one constructor and nothing but numbers and booleans in it — a pair, a point, a body with seven coordinates — is not a box at all: it lives in registers, passed and returned by value, with no count and no allocation. (q, r) = divmod(a, b) costs what returning two numbers costs in C. Such a value is boxed only when it is put into a map or sent down a channel, which store words, and read back out on the other side.

A pipeline over a range — range(1, n) |> filter(p) |> map(f) |> sum, and len and fold the same way — is generated as one loop with no list in it, when the functions are written in place as lambdas and the elements are numbers or booleans. The prelude's map and filter are what is recognized; a program that defines its own gets what it wrote.

A binding whose last use is a call is handed to the call rather than copied into it — the reference goes with the argument, no count taken and none given back — when the call is on the statement's unconditional path and the name is not spoken again. And a function may ask what that leaves it holding: unique(x) is true when this frame holds the only reference to x. The two together are what lets an operation write its answer into an operand's own storage when the operand was a temporary: lib/num/grid.rill makes a * 2.0 + 1.0 one grid and not two by asking unique of what it was given. A value that is asked about is passed owned, so a caller still using it keeps a reference of its own and the answer is false; a compile-time constant is never unique; a value with no count — a flat record, a number — cannot be asked.

Reference counting cannot let go of a ring — a value that, through what it holds, holds itself — and a program of immutable values can make one in exactly one way: a value is built from what exists before it, so only storage can come to hold what holds it. m[k] = v where v holds m — a closure over m, a record with m in it — is refused where it is written, naming m; so is a channel sent a value that holds it. A ring made through two maps, each holding what holds the other, is not seen at compile time; it is what the report below is for.

Run any program with RILL_DEBUG_ALLOC=1 to have the runtime print the number of live allocations at exit. Built with --parallel and run with RILL_ALLOC_CHECK=1 as well, it says which functions made the blocks that were never let go — 3000 block(s) made in make — which is where a ring was closed.

Which of these rules fired where is not visible in the source, and does not have to be guessed: rill explain file.rill is the code generator's own account, written down as it generates, for the file's own functions.

fn total(xs, acc)   # line 6
  `xs` is borrowed: never kept or given away here, so the caller's reference is enough

fn main()   # line 15
  line 16: `Cons(..)` allocates a box with 2 field(s)
  line 17: `xs` is retained for the call: it is spoken again later, or this call is not on the statement's own straight path
  line 19: `P(..)` is a flat value: in registers, no box and no count
  line 22: this pipeline is one loop: no list is built

It says which parameters are borrowed and which owned, which constructor calls reuse the box a match took apart and which allocate, which bindings are handed to a call and which retained, which pipelines became loops, and what each closure holds. A number that came out slower than expected is usually a retain where a hand-over was meant, and the report says which binding and why.

List or Buf

List(a) is a cons list: Cons in front is free, and everything else is a walk. Building one in order means accumulating it backwards and turning it round, which the prelude does for you and which costs a second pass — the reuse above makes it allocate nothing, but it is still a pass.

Buf(w) is storage: a counted, mutable, bounds-checked array of a fixed width, indexed in constant time and appended to by keeping your own length.

Reach for Buf when the program is really building an array — a growing sequence read by index, or anything a C version would realloc. Reach for List when the program is really consing: recursion over a structure, a stack, a queue of work. The JSON parser in benchmarks/tokens/ is the honest example of the difference: it builds arrays as lists, and that one choice is half of what it still gives away to the C it is measured against.

Maps

Map(k, v) is a hash table, and the other thing in the language that is storage rather than a value. It is written like a buffer and read like an Option:

counts = map_new()
counts["cat"] = 2            # insert, or replace what was there
counts["cat"]                # Some(2)
counts["dog"]                # None — the key may not be there, and that is
                             # an Option here as it is everywhere else
#counts                      # 1 — entries, not slots

Both type arguments are inferred; unlike a buffer's width they are ordinary types, so nothing has to be annotated. Anything with structural equality may be a key — a number, a string, a tuple, a data type, nested as deep as you like — and the compiler works out how to hash it from the type, exactly as it works out how to print it. A function or a channel cannot be a key, and says so where the key is written.

A map is reference counted like a string, and what it holds is released with it: nothing frees a table, and nothing leaks when the last reference goes. A table crosses a channel like any other value, and — being storage, with nothing locking it — should be one strand's at a time on a --parallel build, exactly as a buffer should.

Three things are worth knowing. Order is the table's: map_keys and its two siblings hand back entries in whatever order the hashes put them in, which is stable within a run and nothing to depend on across one — a program that needs an order asks for the keys it wants, in the order it wants them. map_or allocates nothing where unwrap_or(m[k], 0) builds a Some to take apart again, which a loop doing it a million times can feel. And a table is storage, so println(m) and m == n are refused the way they are for a buffer; map_items(m) is the same table as a value, and prints and compares like one.

The one place a type has to be said out loud is a read whose base is otherwise unknown: fn get(m) = m[1] settles m as a string, because that is what [] has always meant on an unannotated base. Write fn get(m: Map(Int, Str)) = m[1], or use map_get(m, 1), which needs nothing. A write has no such ambiguity — a buffer would have been annotated and a string is not storage — so fn put(m, k, v) = m[k] = v is a map function without being told.

Reach for a Map when the program is really looking things up by name, and for a List or a Buf when it is walking or indexing. Lookup is one hash and a short probe: a million Int keys go in in about 26 ms and come back out in about 22 on an M4, against 61 and 23 for Go's own map, and peak at 73 MB against Go's 85.

An entry costs seventeen bytes. One is a control byte — whether the slot holds anything, and if it does, seven bits of the key's hash; the other sixteen are the key and the value, side by side. A probe walks the control bytes, which for two million slots is two megabytes and stays in cache while the slots themselves cannot, and touches a slot once, for the one key it believes it has found. Keeping the whole hash beside the key would answer the same question and cost eight bytes an entry to do it; the price of not keeping it is that growing hashes every key again, which is about a tenth of the time it takes to fill a table. The table is kept under three quarters full, counting deleted slots, and grown by doubling.