The Zeno Book Zeno 0.1 zeno-lang.org

29 Memory

Numbers and bools live in the variables that hold them, and need no memory of their own. Text that is built, lists, objects, enum values that carry something, and functions that keep variables all need memory while the program runs, and somebody must give it back when the program is done with it. This chapter is about how an ordinary compiled Zeno program does that, with a garbage collector. The next three chapters are about the ways firmware can do without one.

zeno run needs none of this: the interpreter is a Rust program, and Rust frees its values for it. Everything here is about zeno build.

29.1 What takes memory

  • text that is built: a + b, an f string, text.upper();

  • every list, and every dict;

  • every object, and every enum value that carries something;

  • a function written inside another, with the variables it keeps.

Each of these is a block: a piece of memory from the C library’s malloc. The question is when to give each block back with free.

29.2 The question nobody can answer in advance

function label(reading: Reading) -> str {
    let text = f"tick {reading.tick}"
    return text
}

Is text finished with when label returns? No: the caller has it now, and may put it in a list, which goes into an object, which a function remembers. In C the programmer keeps track of all that by hand, and the mistakes are famous: freeing too early, so that the program uses memory that is now something else; freeing twice; or never freeing at all.

A collector answers a simpler question, while the program runs: can the program still reach this block? If no variable leads to it, directly or through other blocks, nothing can ever use it again, and it is safe to free.

29.3 Mark and sweep

Zeno’s collector is the oldest and simplest kind. It was invented for Lisp in 1960, and it is what MicroPython runs on microcontrollers.

  1. Every block is written in a table as it is handed out.

  2. Mark. Start from the variables, the roots. Whatever a root points at is in use: mark it. Whatever a marked block points at is in use too. Carry on until nothing new turns up.

  3. Sweep. Go through the table. A block with no mark cannot be reached: free it. Take the marks off the rest.

Two objects that point at each other, and at nothing in use, are freed like anything else: no root reaches them, so neither is marked. That is the case that defeats the other common method, counting references.

The roots are the variables at the top of the file, which the compiler lists, and everything on the C stack: the collector reads the stack from the function running now back to main, a word at a time, and asks of each word whether it is the address of one of its blocks. When unsure, it keeps, so it can never free a block in use.

29.4 Seeing it work

zeno build --memory makes a program that reports, as it ends, what memory it used. This one, from the examples folder, logs a reading every tick for 50 000 ticks, and keeps only the last few and the hottest:

memory.zeno

# memory.zeno: a program that makes far more than it keeps.
#
#     zeno run examples/memory.zeno              run it with the interpreter
#     zeno build --memory examples/memory.zeno   compile it, with a memory report
#     ./memory
#
# A logger takes a reading every tick. Each reading is an object with some
# text in it, so every tick takes a little memory. Only the last few
# readings and the hottest one are kept. The rest is garbage, and the
# garbage collector in the compiled program gives that memory back.

class Reading {
    tick: int
    celsius: float
    note: str
}

function describe(reading: Reading) -> str {
    return f"tick {reading.tick}: {reading.celsius:.1f} C ({reading.note})"
}

var recent: list[Reading] = []          # the last few readings
var hottest: Reading or none = none
var lines = 0

for tick in range(50000) {
    let celsius = 20.0 + (tick * 37 % 151) / 10.0
    let reading = Reading(tick, celsius, f"sample {tick}")

    # Start a new list every five readings. The old list, and the readings
    # only it knew about, can no longer be reached from any variable.
    if len(recent) == 5 {
        recent = []
    }
    recent.append(reading)

    if hottest is none or reading.celsius > hottest.celsius {
        hottest = reading
    }

    # Text that is made, measured and forgotten at once.
    lines += len(describe(reading).split())
}

print("words logged:", lines)
print("still held:")
for reading in recent {
    print("  " + describe(reading))
}
if hottest is not none {
    print("hottest: " + describe(hottest))
}

# Built with --memory, the program ends with a line like this one:
#
#   memory: 780027 blocks made (13222784 bytes), at most 1048576 bytes in use at once, 12 collections
#
# Thirteen megabytes were asked for. One megabyte at a time was enough.
$ zeno build --memory memory.zeno > /dev/null
$ ./memory
words logged: 300000
still held:
  tick 49995: 26.5 C (sample 49995)
  tick 49996: 30.2 C (sample 49996)
  tick 49997: 33.9 C (sample 49997)
  tick 49998: 22.5 C (sample 49998)
  tick 49999: 26.2 C (sample 49999)
hottest: tick 102: 35.0 C (sample 102)
memory: 780027 blocks made (13222784 bytes), at most 1048574 bytes in use at once, 10 collections, 60002 blocks freed without the collector

The last line is the report. The program asked for thirteen megabytes, a few bytes at a time, and never held more than one megabyte or so at once, because the collector ran when it was needed and gave the rest back. The last number counts blocks freed at a line the compiler could point to, without waiting for the collector: the old storage of a list that has just grown, and the copy that a for loop walks.

29.5 When it runs

Collecting takes time, in proportion to what is still in use, so it is not done on every allocation. The runtime counts the bytes in use and collects when they pass a limit; after each collection the limit becomes twice what survived. A program that keeps little is collected often and cheaply, and one that keeps a lot is left alone for longer. And if malloc itself says there is no more memory, the collector runs and the request is tried again. On a board with 64 KB of memory, that second trigger is the one that matters.

29.6 What it costs

  • Pauses. While the collector runs, the program does not, and the pause grows with the memory in use. A control loop that must answer within microseconds should not make blocks inside the loop. Numbers, bools and fixed text never do.

  • A few words for each block: a header and its line in the table.

  • It leans on the C compiler. Reading the stack word by word is not something the C standard describes. Every mainstream compiler and processor allows it, and the Boehm collector, Ruby and MicroPython have relied on it for decades.

Sharing, with a collector to make it safe, is what Python, Java and JavaScript programmers expect, and it lets a program be written without thinking about memory at all. Counting references cannot free a cycle and costs on every assignment. Rust’s ownership everywhere would make every Zeno program pay the hardest part of Rust. So the collector is the default, and the next chapters give firmware the other choices where it needs them. (Decision 5.7.)

29.7 Three ways to manage memory

Build Memory
zeno build shared values and a collector: this chapter
owned values one owner, freed where its block ends, in any build: Ownership
--no-collector every list and object has one owner, memory comes from a fixed pool, and there is no collector: Building with No Collector

Memory a program asks for itself with allocate is apart from all three: the collector never looks at it, and the program gives it back with free (Unsafe Code).

Built text, lists, dicts, objects, enum values that carry something and functions that keep variables take memory. A compiled program frees it with a mark-and-sweep collector, which frees whatever no variable can reach, cycles included. It runs when memory in use passes a limit, or when malloc runs out. --memory reports what a program used. The cost is pauses, a little memory per block, and a habit of C compilers that every one of them keeps.

  1. Build memory.zeno with --memory and change the number of ticks. Which numbers in the report grow, and which do not?

  2. Write a loop that builds a text with + a thousand times, and build it with --memory. Then build the same text once with join. Compare the reports.

  3. Make two objects that point at each other through fields that may be none, drop every variable that leads to them in a loop, and check that the memory in use stays low.