A list of numbers that may be none, with no collector
A number that may be none travels with a flag: int or none is a
number and a bit that says whether the number is there. A slot of a
list holds 64 bits, and the number fills it, so a list keeps such an
item in a small box of its own and holds the box's address, or NULL
for none. With no collector nothing freed those boxes, and until
0.8.0 zeno build --no-collector refused the list:
error: a list of numbers that may be `none` keeps each item in a small block of its own, and `zeno build --no-collector` leaves the collector out, so nothing would free them. ...
Now the list owns its boxes, as it owns its copies of text:
function average(readings: list[float or none]) -> float or none {
var sum = 0.0
var count = 0
for r in readings {
if r is not none {
sum += r
count += 1
}
}
if count == 0 {
return none
}
return sum / count
}
var readings: list[float or none] = [21.5, none, 22.0]
readings.append(none)
readings.append(23.5)
readings[1] = 21.0
print(readings, average(readings))
let last = readings.pop()
print(last, len(readings))
cargo run -- build --no-collector --memory gaps.zeno
./gaps
[21.5, 21.0, 22.0, none, 23.5] 22.0
23.5 4
memory: 7 blocks made (128 bytes), at most 112 bytes in use at once, no collector, 0 blocks left at the end
pool: 248 bytes taken, in a pool of 32768
text: at most 61 bytes in use at once, in a room of 1024
zeno run prints the same two lines, and so does every other build
and every target. The reasons for each choice are in 56.14 of
decisions.md. It is part 9.6 of
plan-9-14.md.
Only with no collector
Nothing changes in any other build. With a collector the boxes are the collector's, as they always were, and the C of such a program is what 0.7.0 wrote. Only a build that refused the list before builds it in a new way.
The rule
With no collector, a list owns the box of each number that may be
none, as it owns its copy of each text.
Each thing a list does follows from that:
| Written | What happens to the box |
|---|---|
[1, none], append, insert |
a new box in the pool for each number; none needs none |
xs[i] |
the number is read out; the box stays |
xs[i] = v |
a new box for v, and the old box is freed |
pop(), take xs[i] |
the number is read out, and the box is freed |
clear(), and the end of the list |
every box is freed |
a + b, a * 3, slice, filter, map |
the new list gets boxes of its own |
for x in xs |
the loop walks a copy with boxes of its own, so the body may change xs |
find, in |
the number looked for sits in a box in the text room, given back when the statement is over |
The same is true of float or none, bool or none and the sized
numbers, such as u8 or none.
What it costs
Each number that is there takes one block of the pool: 8 bytes for the
number, and the pool's own few bytes beside it. none takes nothing.
The list's own row of slots is a block of the pool too, as it is for
any list. In the pool of 32,768 bytes a build has by default, a
list[int or none] filled from empty holds 679 numbers; the 680th stops the
program with the message every full pool gives:
error: the memory pool is full (ZENO_POOL is 32768 bytes)
--pool gives a build a bigger pool, or the exact one --memory
names (pool-size.md).
On a small board, where every block counts, two lists cost less:
- A number that stands for "nothing", in a plain
list[int]:-1for a reading that never came, when no reading is ever-1. The number sits in the slot itself, with no block. - An enum with a case for the missing value,
MissingandValue(n: int). Its values are blocks too, butMissingtakes none, and the type says what the missing value means.
In the C
runtime.c is not changed. A program that has such a list gets the
functions it uses, written for it:
static void *zeno_box_keep_float(zeno_opt_float value) {
if (!value.present) return NULL;
double *box = (double *)zeno_alloc_raw(sizeof(double));
*box = value.value;
return box;
}
static zeno_opt_float zeno_box_take_float(void *box) {
zeno_opt_float value = zeno_unbox_float(box);
zeno_free(box);
return value;
}
static void zeno_list_drop_boxes(zeno_list *list) {
if (list == NULL) return;
for (int64_t i = 0; i < list->len; i++) zeno_free(list->items[i].p);
zeno_list_drop(list);
}
and uses them where the list keeps, gives up or ends:
zeno_list_append(z_readings, (zeno_slot){.p = zeno_box_keep_float((zeno_opt_float){true, 23.5})});
zeno_slot t2 = (zeno_slot){.p = zeno_box_keep_float((zeno_opt_float){true, t1})};
zeno_slot *t3 = zeno_list_at(z_readings, 1, 19, 1);
zeno_free(t3->p);
*t3 = t2;
...
z_last = zeno_box_take_float(zeno_list_pop(z_readings, 21, 12).p);
...
zeno_list_drop_boxes(z_readings);
zeno_list_keep_boxes_float gives a list just made (by +, *, a
slice or a loop's copy) a box of its own for each item. The LLVM build
writes the same functions in IR, as zeno.box.keep.float and the rest.
How it is tested
- Both compilers:
a_list_of_numbers_that_may_be_none_every_waybuildstools/targets/edge-none-list.zenowith no collector through C and LLVM, which give the same memory report with 0 blocks left. It is also built in the ordinary and firmware builds of both. The program has: - lists of ints, floats, u8s and bools that may be
none, withnonefirst and last; append,insert, a store,pop,pop(0),take,find,reverse,clear,+,*andslice;mapthat gives a number that may benone,filterandreduce;- such a list in a field and in a list;
- a loop whose body adds to the list it walks;
- six hundred numbers stored and replaced.
The same test reads the C of the helpers, checks that a build with a collector writes what it wrote before, and fills the pool with five thousand numbers, which stops with the message of a full pool through C and LLVM. - The targets run the same program.
Things to try
- Build
gaps.zenowith--no-collectorand opengaps.c. Findzeno_box_keep_float. Why doesnonenot callzeno_alloc_raw? - Build it again without
--no-collectorand search forzeno_box_keep_float. Why is it not there? - Add
readings.clear()before the lastprint, and build with--memory. How many blocks are made, and how many are left? - Fill a
list[int or none]with a thousand numbers in a loop and build with--no-collector. What does the pool say? Then make the same list withnonein every other place. Why does it fit? - Write an enum
ReadingwithMissingandValue(n: int), make the same list of it, and compare the two memory reports. - Loop over
readingsand append to it inside the loop. Why does the loop not see the new items, and what does the copy it walks cost?
This page is docs/none-list.md in the language repository.