Memory and reference counting

Pepper frees memory for you, without a garbage collector and without ownership annotations. Every struct object keeps a count of the references to it, and the object is destroyed the moment that count drops to zero. Because the rules are simple and the same everywhere, you can always tell when an object will be destroyed and its destructor will run.

If you know C++, the whole model fits in one sentence: every struct value behaves exactly like a std::shared_ptr<T> passed by value.

Values and references

Numbers, bool, and the other primitive types are plain values: assigning one copies it, as in C. So is a tuple, whose elements are copied the way each element would be on its own, and so is a struct or enum marked [Value], such as Optional<T> and Result<T> (see value enums).

Everything else, including your own structs, String, Array, HashMap, and function values, is a reference to an object on the heap. Assigning a reference, passing it to a function, or storing it in a field or an array shares the object. Nothing is copied.

struct Account {
    var balance: int = 0;
}

# The parameter is another reference to the caller's object, so changes to
# its fields are visible to the caller.
deposit(account: Account, amount: int) {
    account.balance += amount;
}

# Rebinding the parameter itself only changes this function's reference.
replace(account: Account) {
    account = Account();
    account.balance = 999;
}

main(): int {
    var mine = Account();
    var yours = mine;               # shares the object; nothing is copied
    yours.balance = 50;
    assert(mine.balance == 50, "assignment shares the object");

    deposit(mine, 25);
    assert(mine.balance == 75, "a function can change the shared object");

    replace(mine);
    assert(mine.balance == 75, "rebinding a parameter does not affect the caller");

    # To get an independent object, make a new one and copy the fields.
    var copy = Account();
    copy.balance = mine.balance;
    copy.balance = 0;
    assert(mine.balance == 75, "the copy is a separate object");
    return 0;
}

• var yours = mine; makes a second reference to the same Account. Changes through either name are visible through both.
• A parameter is one more reference to the caller’s object. The function can change the object’s fields, but assigning a new object to the parameter only changes the function’s own reference.
• To get an independent object, create a new one. Pepper does not copy structs for you; some library types offer a method for it, such as Array’s clone().

A struct-typed variable or field that has not been given a value, such as var next: Account;, is null: it refers to no object. Reading a field or calling a method through a null reference crashes the program. Use === or !== to check whether two references name the same object, or whether one is null (next === __null). A struct is not a condition by itself, so if (next) is an error unless the struct declares the truth test !! (see Truth tests and conditions). For a value that may be absent, prefer Optional<T>, whose type says so.

When objects are destroyed

A reference is held by whatever stores it: a local variable, a parameter, a field, an element of a container, or a temporary value in the middle of an expression. Each of those releases its reference exactly once, when it goes away. When the last reference is released, the object is destroyed: its destructor runs, and then its fields release their own references, which may destroy further objects in turn.

import async;

# A module-scope counter: const, and changed through an Atomic.
const destroyed = async.Atomic<int>(0);

struct Tracked {
    var name: String;
    construct(this.name = "") {}
    destruct {
        destroyed.fetch_add(1);
    }
}

struct Holder {
    var item: Tracked;
}

make(name: String): Tracked {
    var t = Tracked(name);
    return t;                   # the caller receives the object
}

main(): int {
    # 1. A local is released when its scope ends.
    {
        var a = Tracked("a");
    }
    assert(destroyed.load() == 1, "a was destroyed at the end of its block");

    # 2. While another reference exists, the object stays alive.
    var b = Tracked("b");
    var also_b = b;
    b = Tracked("b2");          # b lets go of the first object...
    assert(destroyed.load() == 1, "...but also_b still holds it");
    also_b = b;                 # the last reference moves away
    assert(destroyed.load() == 2, "the first object is destroyed now");

    # 3. Fields and containers hold references too.
    var holder = Holder();
    {
        var c = Tracked("c");
        holder.item = c;
    }
    assert(destroyed.load() == 2, "holder.item keeps c alive after its scope");
    holder = Holder();          # the old Holder dies and releases c
    assert(destroyed.load() == 3, "releasing the holder released its field");

    var list = Array<Tracked>();
    list.append(Tracked("d"));
    assert(destroyed.load() == 3, "the array holds d");
    list.clear();
    assert(destroyed.load() == 4, "clearing the array released d");

    # 4. Returned objects belong to the caller; unused results are
    #    destroyed right away.
    var e = make("e");
    assert(destroyed.load() == 4, "e is alive in main");
    make("temporary");
    assert(destroyed.load() == 5, "a result nobody keeps is destroyed immediately");
    return 0;
}

Concretely, a reference is released when:

• A local variable goes out of scope, at the closing brace of the block that declared it, or when the function returns.
• A variable or field is overwritten. b = Tracked("b2"); releases the object b held before, after taking the new one. Assigning a variable to itself (a = a) changes nothing.
• A parameter’s function returns. The function held its parameters for as long as it ran.
• The object that holds a field is destroyed, or a container removes an element (clear(), overwriting list[i], and so on). remove_at() and pop() are the exception: they hand the container’s reference to the caller, so var x = list.remove_at(0); leaves the count unchanged.
• A temporary is no longer needed. A result that is not stored anywhere, like the one from make("temporary");, is released at the end of the statement. The same goes for a call result passed straight to another function, and for the object in make().name.

Returning a local hands its reference to the caller, so the object survives the function. Calling a method on an object does not add a reference to it: inside the method, this refers to the caller’s object.

Cycles leak

Reference counting cannot free a cycle: objects that refer to each other, directly or through a chain, keep each other’s counts above zero even after nothing else refers to them. Their destructors never run and their memory is never freed.

import async;

# A module-scope counter: const, and changed through an Atomic.
const destroyed = async.Atomic<int>(0);

struct Person {
    var name: String;
    var friends: Array<Person>;

    construct(this.name = "") {
        friends = Array<Person>();
    }

    destruct {
        destroyed.fetch_add(1);
    }
}

main(): int {
    # Two people who list each other as friends form a cycle: each keeps
    # the other alive, so neither is ever destroyed.
    {
        var ann = Person("Ann");
        var bob = Person("Bob");
        ann.friends.append(bob);
        bob.friends.append(ann);
    }
    assert(destroyed.load() == 0, "the cycle leaked both objects");

    # Break the cycle before letting go, and both are destroyed.
    {
        var cat = Person("Cat");
        var dan = Person("Dan");
        cat.friends.append(dan);
        dan.friends.append(cat);
        dan.friends.clear();    # Dan no longer holds Cat
    }
    assert(destroyed.load() == 2, "without the cycle, both were destroyed");
    return 0;
}

To avoid a cycle, make one direction of it a weak reference (next section), or break the cycle yourself before the last outside reference goes away: clear the container, or overwrite the field, that closes the loop.

A closure holds a reference to every struct it captures, including this, so a closure stored inside an object it captures closes a cycle too. The compiler reports the direct case, a method storing a closure that captures this in a field of this.

Weak references

A Weak<T> points at an object without keeping it alive. Use it for back pointers: a child’s parent, a document’s folder, an observer’s subject. The owner holds strong references down the tree, and everything that points back up holds a Weak<T>, so there is no cycle.

import async;

# A module-scope counter: const, and changed through an Atomic.
const destroyed = async.Atomic<int>(0);

struct Folder {
    var name: String;
    var files: Array<Document>;

    construct(this.name = "") {
        files = Array<Document>();
    }

    destruct {
        destroyed.fetch_add(1);
    }
}

struct Document {
    var title: String;
    # A weak back pointer: the folder owns its documents, not the other way
    # round, so there is no cycle.
    var folder: Weak<Folder>;

    construct(String title, Folder folder) {
        this.title = title;
        this.folder = Weak<Folder>(folder);
    }

    destruct {
        destroyed.fetch_add(1);
    }

    String path() {
        with (var f = folder) {
            return f.name + "/" + title;
        } else {
            return "(deleted)/" + title;
        }
        return "";
    }
}

main(): int {
    var kept = Document("draft", Folder("none"));
    {
        var home = Folder("home");
        var notes = Document("notes", home);
        home.files.append(notes);
        assert(notes.path() == "home/notes", "the folder is alive");
        kept = notes;
    }
    # The folder went away with `home`; the weak pointer did not keep it.
    assert(kept.path() == "(deleted)/notes", "the folder is gone");
    assert(kept.folder.expired(), "and the weak reference knows it");
    return 0;
}

• Weak<T>(object) makes the weak reference. It does not change the object’s reference count.
• A with block reaches the object: with (var f = folder) { ... } binds f to an ordinary strong reference for the length of the block. When the object has already been destroyed, the body is skipped and the else block runs. See Scoped blocks with with.
• expired() reports whether the object has been destroyed.
• T may be a trait: Weak<Shape> upgrades to a Shape (see Weak references and atomics).
• The object is destroyed on time. When its last strong reference goes, its destructor runs and its fields are released, even if weak references remain. Only the object’s small header stays allocated until the last weak reference is gone.

In C++ terms, a struct value is a std::shared_ptr<T> and Weak<T> wraps the built-in __weak<T>, a std::weak_ptr<T>: Weak<T>(object) is weak_ptr(object), and entering it with with is lock(). Inside a constructor, this already holds the object’s first reference, like the shared_ptr that make_shared fills in: a constructor may pass this to a function or store it, and a weak reference made from it upgrades, without the object being destroyed when those copies are dropped.

References and threads

Reference counts are plain, fast increments, so a struct’s objects must stay on one thread. A struct declared [Shared] has atomic counts instead, and its references can be copied and dropped on any thread. The compiler requires such a struct’s fields to be const and thread-safe. See What threads can share.

Function values follow the same split: a plain function type such as () => void has plain counts and stays on one thread, and a shared function type such as shared () => void has atomic counts.

Copying a value with copy

copy(value) makes a copy of a value that shares no object that is not thread-safe with the original, so the copy can go to another thread: pass copy(x) to a channel to send a value you keep using.

var names = Array<String>();
names.append("ada");
var copied = copy(names);
copied[0].append(" lovelace");   # names[0] is still "ada"

• Every struct object the value reaches is copied once. An object referenced twice is copied once and stays shared inside the copy, and a cycle becomes the same cycle among the copies.
• Thread-safe objects are not copied: a [Shared] struct or a shared function value in the original is the same object in the copy. For a thread-safe value, copy returns the value itself.
• A weak reference to an object that was copied points at its copy. A weak reference to an object outside the copied value becomes null.
• A struct is copied field by field, without running its constructor.

A struct with a destructor or a raw pointer (__ptr<T>) field is not trivially copyable: copying its fields would share what it owns, such as a buffer it frees. Such a struct says how to copy itself by implementing Copyable<T>, with a copy(): T method that builds the copy and copies each value it holds with copy(value). String, Array, HashMap and HashSet implement it. String.copy() also copies a single String; it replaces the deprecated clone(). Array.clone() is unchanged: it copies the Array but shares its elements.

# A struct with a destructor is not trivially copyable, so it implements
# `Copyable<T>` to say how `copy` copies it.
struct Buffer {
    __ptr<u8> data;
    ulong size;
    String label;

    construct(size: ulong) {
        data = _pep_malloc(size);
        this.size = size;
        label = "buffer";
    }

    destruct {
        _pep_free(data);
    }

    copy(): Buffer {
        var made = Buffer(size);
        var i: ulong = 0;
        while (i < size) {
            made.data[i] = data[i];
            i = i + 1;
        }
        # The free function `copy`: it continues the running copy.
        made.label = copy(label);
        return made;
    }
}

extend Buffer with Copyable<Buffer>;

struct Message {
    Buffer body;
    Buffer again;
}

main(): int {
    var message = Message();
    message.body = Buffer(4);
    message.body.data[0] = 9;
    message.again = message.body;

    var copied = copy(message);
    copied.body.data[0] = 1;
    copied.body.label.append(" (copy)");
    assert(message.body.data[0] == 9, "the original buffer is unchanged");
    assert(message.body.label == "buffer", "the original label is unchanged");
    # The buffer appears twice, so its copy is one object.
    assert(copied.again === copied.body, "one copy of the shared buffer");
    return 0;
}

Inside copy(), the call copy(label) is the free function, not the method: a bare call in a method names the struct’s own method only when one by that name takes those arguments. While a copy runs, copy(value) continues it rather than starting another, so an object the outer copy already made is reused and sharing is kept. That is why a Copyable value is copied with copy(x): calling x.copy() directly still works, but each copy(value) inside it is then a copy of its own. A value whose contents can lead back to it calls register_copy(this, made) before copying them, so the cycle finds the copy being built.

The copy(copies: Copies): T form of Copyable<T>, which took the copy’s context as an argument and copied with copies.copy(value), still works in this release, with a warning at Copies.

Copying a value that reaches a struct that is not trivially copyable and does not implement Copyable<T> is an error at the copy call. It names the struct, shows each field on the way to it, says why it cannot be copied, and shows a Copyable<T> to fill in (the editor offers to insert it):

main.pep:14:13: error: cannot copy 'Log' because it contains 'Handle', which is not trivially copyable
   14 |     var c = copy(log);
      |             ^~~~
main.pep:9:5: note: 'Log' reaches it through field 'out'
    9 |     Handle out;
      |     ^~~~~~
main.pep:1:8: note: 'Handle' has a destructor, so copying its fields would release what it owns twice
    1 | struct Handle {
      |        ^~~~~~
note: implement 'Copyable<Handle>' to say how to copy it:
    extend Handle with Copyable<Handle> {
        copy(): Handle {
            # Build the copy; copy each struct field with copy(field).
            panic("copying 'Handle' is not implemented");
            return this;
        }
    }

Some types cannot be copied at all: an io.File owns an operating-system handle, so the error says to send its path instead. A plain function value cannot be copied, because it may capture anything; declare it shared.

Copying trait values

copy of a trait value copies the struct behind it, as copy of that struct would, and returns the copy as the same trait type. Sharing works across the boundary: a struct reached twice, through a trait value or directly, is copied once.

# `copy` of a trait value copies the struct behind it, whichever it is.
trait Shape {
    area(): int;
    grow();
}

struct Square {
    var side: int = 1;
    construct(this.side = 1) {}
}

extend Square with Shape {
    area(): int { return side * side; }
    grow() { side = side + 1; }
}

struct Rect {
    var width: int = 1;
    var height: int = 1;
    construct(this.width = 1, this.height = 1) {}
}

extend Rect with Shape {
    area(): int { return width * height; }
    grow() { width = width + 1; }
}

main(): int {
    var shapes = Array<Shape>();
    var square = Square(2);
    shapes.append(square);
    shapes.append(Rect(2, 3));
    shapes.append(square);

    var copied = copy(shapes);
    for (var shape in copied) {
        shape.grow();
    }
    assert(shapes[0].area() == 4, "the original Square is unchanged");
    assert(shapes[1].area() == 6, "the original Rect is unchanged");

    # The Square appears twice, so its copy is one object, grown twice.
    assert(copied[0] == copied[2], "one copy of the shared Square");
    assert(copied[0].area() == 16, "the copied Square grew twice");
    assert(copied[1].area() == 9, "the copied Rect grew once");
    return 0;
}

Which struct a trait value holds is known only when the program runs, so the compiler cannot check that it can be copied. Copying a trait value that holds a struct that cannot be copied (one with a destructor and no Copyable<T>, an io.File, a MutexGuard) panics:

cannot copy the 'Owner' behind a trait value, which is not trivially copyable

Handing a reference over with move

move(x) gives up x’s reference: the call returns the same object, and x is left null. Nothing is copied and no count changes. It is how a value built in a local variable goes to a channel, a Mutex or another [Move] parameter, which takes a new value, without the cost of copy(x):

var lines = Array<String>();
lines.append("first");
var log = async.Mutex<Array<String>>(move(lines));   # lines is now null

move is an ordinary function from the prelude (runtime/copy.pep), but the compiler checks every call:

• Only a local variable can be moved (move(h.s) is an error), and only when it holds the one reference to a new value: nothing else refers to it or to anything it reaches. A parameter can be moved only when it is [Move], since the caller handed its value over.

  main.pep:8:24: error: 'a' cannot be moved: 'b' also references its value
      8 |     names.replace(move(a));
        |                        ^
  note: only a variable that holds the one reference to a new value can hand it over; pass 'copy(...)' instead
  

• A moved variable cannot be read again until it is assigned a new value, including on the next pass through a loop:

  main.pep:8:12: error: 'a' is used after its value was moved
      8 |     return a.count;
        |            ^
  main.pep:7:19: note: 'a' was moved here; assign it a new value before using it again
      7 |     names.replace(move(a));
        |                   ^~~~
  

The runtime also moves values out of raw memory (move(buffer[head])), which is a promise the compiler cannot check: only runtime files may do it. The parameter of move is marked [MoveSource], which is also only allowed in the runtime, so a hand-off always shows at the call as move(x); a function of your own that takes over its argument uses [Move].

Where objects live

Every object, String buffer and Array buffer comes from the runtime’s allocator. A block of up to 128 bytes (most objects and short strings) comes from a small block allocator: blocks are grouped by size into classes (multiples of 16 bytes up to 128, then four classes per power of two). Each class’s blocks are cut from 64 KiB spans, and a thread hands out a class’s blocks from one span at a time, so objects made one after another sit close together in memory. Allocating, and freeing on the thread that allocated, take no lock; a block freed on another thread goes back to its span with one atomic step. Larger blocks come from the C library’s calloc and go back with free. A small block’s size is rounded up to its class, so a 40-byte object takes 48 bytes.

An empty Array allocates nothing. Array<T>() makes no object until the Array is written (append, insert, reserve, …) or shared (assigned to a second variable, stored in a field or element, passed or returned): reading it (count, is_empty, contains, a for loop over it) allocates nothing. The first write or share allocates the object, so every name for the Array still sees the same appends:

struct Node {
    String name;
    # Most nodes never get children, and an empty Array costs nothing.
    Array<Node> children = Array<Node>();
    construct(name: String) {
        this.name = name;
    }
}

main(): int {
    var a = Array<int>();           # no allocation
    assert(a.count == 0 && a.is_empty, "reading allocates nothing");
    for (var x in a) {
        assert(false, "an empty Array has no elements");
    }
    var b = a;                      # allocates the Array: a and b share it
    b.append(1);                    # allocates its buffer
    assert(a.count == 1, "both names see the append");

    var leaf = Node("leaf");
    var root = Node("root");
    root.children.append(leaf);
    assert(leaf.children.is_empty && root.children.count == 1, "only root's children were allocated");
    return 0;
}

Structs that hold an Array which usually stays empty (a tree node’s children, a list of comments) cost nothing extra for it.

The environment variable PEPPER_SMALL_BLOCK_LIMIT, read when the program starts, sets the largest size the small block allocator serves, in bytes, up to 4096 (a larger value counts as 4096). 0 turns it off, and then every block comes from the C library:

PEPPER_SMALL_BLOCK_LIMIT=0 ./main      # every block from calloc
PEPPER_SMALL_BLOCK_LIMIT=512 ./main    # blocks up to 512 bytes from the classes

With it off, a program can use another C allocator, such as mimalloc, by loading it in front of the C library (LD_PRELOAD=libmimalloc.so on Linux).

Small blocks live in address space the program reserves at start (4 GiB, committed 64 KiB at a time as it is used, and never returned to the operating system); a program that fills it falls back to calloc. On WebAssembly, which cannot reserve address space, every block comes from calloc.

Summary