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, anfstring,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.
Every block is written in a table as it is handed out.
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.
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.
Build
memory.zenowith--memoryand change the number of ticks. Which numbers in the report grow, and which do not?Write a loop that builds a text with
+a thousand times, and build it with--memory. Then build the same text once withjoin. Compare the reports.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.