Chapter 6

Where Values Live

In C, the question "where does this value live?" has three answers: in a register or on the call stack, in static data, or on the heap. Goose keeps the first two and replaces the third. This chapter explains what replaces it, and the three consequences that everything else in the language builds on: freeing is free, nothing moves, and copies are always visible.

#Three kinds of size6.1

Every Goose type falls into one of three size classes:

Fixed-size values live where they do in C: in registers, on the native call stack, and in static data. Nothing about them is surprising. They are copied when you assign them, passed by value, and returned by value.

Variable and resizable values are where Goose is different.

#Data stacks6.2

A running Goose program has the native call stack, its static data, and a small number of data stacks. A data stack is a large reservation of address space, gigabytes of it, with a pointer to its current top. Reserving address space costs nothing until the memory is touched, so the size of the reservation is not a real cost.

Every value that is not fixed-size lives on a data stack, and is owned by the variable that declared it. Two rules make this work:

  1. Values are pushed onto a stack in the order of their lifetimes, and freed all at once when the scope that owns them ends. Freeing them means setting the stack's top pointer back to where it was: one store.
  2. A growable value is always the topmost thing on its stack, for as long as it lives. So growing it is a pointer bump, with no capacity check and no reallocation, and it never moves.

Rule 2 sounds very restrictive until you notice the plural in "data stacks". If three growable arrays are alive at the same time, they get three different stacks:

stack 0 nest top reserved stack 1 shelf top reserved stack 2 crate top reserved stack 3 scratch top reserved an inner scope's scratch: gone when the scope ends each growable array is the top of its own stack
Every growable array is the topmost value on a data stack of its own, so it can grow in place. When an inner scope ends, its stack's top drops back.

The compiler works out how many stacks a program needs, and which value goes on which stack, from the program's structure. A stack is reused as soon as the scope that used it has ended. You never write any of this down; there is no syntax for a stack anywhere in the language. You can ask the compiler what it decided, though:

fn main() {
    var nest: i64[>..] = [];
    var shelf: i64[>..] = [];
    var crate: i64[>..] = [];
    for i in 3 { nest.push(i); shelf.push(i * 10); crate.push(i * 100); }
    print(nest, shelf, crate);
}

$ goose check --stacks crates.goose

data stacks: 2 GB reserved per stack, 1 MB guard gap, 32 TB budget: 16376 regions, GS_MAX_STACKS 1024
main program: 4 data stacks + 0 global stacks = 4 regions
thread cap: none, no workers
fn main: 4 own, 4 with callees

Three of the four stacks are for the three arrays. The fourth holds the text that print builds before writing it.

#Leaving a scope frees everything6.3

Here is a loop that builds a scratch buffer of a thousand bytes on every iteration:

fn main() {
    for round in 3 {
        var scratch: u8[>..] = [];
        for i in 1000 { scratch.push((i % 256) as! u8); }
        print("round ", round, ": ", scratch.len, " bytes");
    }
}

round 0: 1000 bytes
round 1: 1000 bytes
round 2: 1000 bytes

At the closing brace of each iteration, scratch's stack has its top reset to where it was before the iteration started, so each round starts with an empty stack and reuses the same memory. No destructor runs, no free list is updated, and nothing walks over the bytes. In a C program the equivalent is a malloc and a free per round, or a buffer you manage by hand. In Goose it is the default.

The same is true of every scope, not just loop bodies: a function's body, an if branch, a bare { … } block. When the scope ends, everything it owned is gone.

#Nothing moves6.4

Because a growable array is always on top of its stack, it never has to be moved to make room. Its elements stay at the same addresses for as long as the array lives, so a reference into a growing array stays valid:

struct Goose { name: u8[..12], honks: i32 }

fn main() {
    var flock: Goose[>..] = [];
    let leader .= flock.push(Goose { name: "Ada", honks: 0 });
    for i in 100000 { flock.push(Goose { name: "", honks: 0 }); }
    leader.honks = 7;
    print(flock.len, " geese; ", flock[0]);
}

100001 geese; Goose { "Ada", 7 }
flock: Goose[>..] Ada room to grow push writes here: nothing below it ever moves leader a reference stays valid however much is pushed
The elements of a grow-only array never move, so a reference to an element stays valid after any number of pushes.

push returns a reference to the element it just built, and .= binds leader to that reference. After a hundred thousand more pushes, writing through leader still writes flock[0].

This is the single most important property of the memory model. A std::vector, an Odin [dynamic]T or a Rust Vec<T> reallocates when it outgrows its capacity, which invalidates every pointer into it. That is why C and Odin programmers keep indices into arrays instead of pointers, and why the Rust borrow checker refuses to let you hold a reference into a vector while you push to it. In Goose you can hold a typed reference, and the compiler only has to check that the reference does not outlive the array.

#Copies are visible6.5

Fixed-size values are copied when you assign them, exactly as in C:

struct Egg { weight: f32, day: i32 }

fn main() {
    var first = Egg { 61.0, 1 };
    var second = first;          // a copy
    second.day = 2;
    print(first.day, " ", second.day);
}

1 2

Non-fixed values are different. Copying one costs time proportional to its size, so Goose never does it behind your back. Wherever a growable array would be implicitly copied, it is bound by reference instead, or the program is rejected:

fn main() {
    var eggs: i64[>..] = [61, 72, 58];
    let same = eggs;             // no copy: `same` names the same array
    same.push(66);
    var mine = copy(eggs);       // an explicit, visible copy
    mine.push(70);
    print(eggs, " ", mine);
}

[61, 72, 58, 66] [61, 72, 58, 66, 70]

let same = eggs; did not copy anything: same is a reference to eggs, and pushing through it pushes onto eggs. copy(eggs) made a real copy, which lives on its own stack.

Where a declaration's type says it needs a value of its own, a plain assignment from another variable is an error, and the error tells you the two ways out:

fn main() {
    var eggs: i64[>..] = [61, 72, 58];
    var mine: i64[>..] = eggs;
}

error: eggs is not fixed-size and is not copied implicitly (§4.1): pass copy(eggs) for a copy, or bind it by reference

The same rule applies at calls. Passing a growable array to a function passes it by reference, whatever the parameter looks like, and a function that wants its own copy calls copy itself.

#Built in place6.6

If copies are never implicit, how does a function return a new array? It does not copy one. Every non-fixed value is constructed directly in its final location:

struct Egg { weight: f32, day: i32 }

fn lay_week() -> Egg[>..] {
    var eggs: Egg[>..] = [];
    for d in 7 { eggs.push(Egg { 60.0 + d, d as i32 }); }
    return eggs;
}

fn main() {
    var week = lay_week();
    print(week.len, " eggs, the last one ", week[6]);
}

7 eggs, the last one Egg { 66.0, 6 }

When main calls lay_week, the compiler knows where the result is going: into week. It compiles lay_week so that its local eggs is week from the start, and every push goes directly into main's variable. return eggs copies nothing.

The same thing happens when the destination is an element being pushed, the field of a struct being built, or the argument of another call. str, which formats its arguments as a new string, writes its text directly into the new element here, with no temporary string in between:

fn main() {
    var log: u8[][>..] = [];
    for day in 3 { log.push(str("day ", day + 1, ": ", day * 2 + 1, " eggs")); }
    for line in log { print(line); }
}

day 1: 1 eggs
day 2: 3 eggs
day 3: 5 eggs

The practical upshot is that returning a value is as cheap as filling in an out-parameter, so Goose code rarely has out-parameters. Write the function that returns the value.

#Globals6.7

Globals are declared at the top level, like constants, but with var. A global is initialized before main runs and lives for the whole program. A global growable array owns the bottom of a data stack for the program's lifetime, which makes it a natural program-wide arena:

var registry: u8[][>..];         // a var with only a type starts out empty

fn register(name: u8[:]) { registry.push(name); }

fn main() {
    register("Ada");
    register("Grace");
    print(registry.len, " geese registered: ", registry);
}

2 geese registered: ["Ada", "Grace"]

name is a slice, a view of bytes that belong to the caller. The elements of registry are u8[], finished strings with bytes of their own, so push builds a new element by copying the bytes that name views, directly into place. That is a copy you can see coming: the type of the element says it owns its bytes. Chapter 9 covers the different kinds of string.

#Design note: why no heap?6.8

A general-purpose heap answers a question most programs never ask: "give me memory whose lifetime I will decide later, in an order I cannot predict". Answering it costs a lot. It needs an allocator with free lists and size classes, fragmentation, a header on every block, a pointer to every block, and either a programmer who frees each block correctly, a garbage collector, or a type system that proves the frees correct.

Most data does not need that flexibility. A request handler's scratch buffers live exactly as long as the request. A compiler's syntax tree lives exactly as long as the compilation of one file. A frame's draw list lives for one frame. Arena allocation has always been the fast way to handle these cases, and Odin programmers use it routinely. Goose's bet is that arena allocation, done automatically and checked by the compiler, covers nearly all of a program's data. For the rest, the data whose lifetimes really do not nest, Chapter 14 introduces pools, which reuse slots without ever freeing memory.

Getting rid of the heap also gets rid of pointers inside data. A Goose array of strings is one block, not a tree of blocks. That makes it faster to build and to walk, and it means a value can be copied, saved to disk or sent to another thread as a single run of bytes.

#Exercises6.9

  1. Write a function squares(n: i64) -> i64[>..] that returns the first n square numbers, and print squares(6). Where does the array returned by the function actually live?

  2. Predict the output of this program, then run it:

goose check fn main() { var a: i64[>..] = [1]; let b = a; var c = copy(a); b.push(2); c.push(3); a.push(4); print(a, " ", b, " ", c); }

  1. Use goose check --stacks on the program from exercise 2. How many data stacks does main need, and why?