Who frees the memory?

A running program keeps its short-lived values on the stack, which tidies itself up whenever a function returns. Anything that has to outlive the function, or whose size isn’t known in advance, goes on the heap: a big shared pool where the program asks for a block and, sooner or later, has to hand it back.

The oldest answer to “who hands it back?” is you do. In C you call malloc to get a block and free to return it. Nothing checks your work. That makes it fast and completely predictable, and it makes three classic bugs possible.

Forget to free and the program leaks: it slowly eats memory until something gives. Free too early and you get a use-after-free: the old pointer now reads whatever moved in next. Free twice and the allocator’s own bookkeeping gets corrupted. Use-after-free alone is behind a large share of serious security holes in big C and C++ codebases.

who uses it C, Zig, and C++ under its smart pointers. Most operating systems, browsers, databases and game engines are built on it.

Run “free too early” to the end. Where did the PIN come from?

A tracing garbage collector flips the question round. The program just allocates and never frees. Every so often the collector starts from the roots (local variables, globals), follows every pointer it can reach and marks what it finds. Whatever it didn’t reach can’t be used again, so it’s swept away. That’s mark and sweep.

Leaks of the forgotten-free kind disappear, and so do use-after-free and double frees. Cycles are no problem either: two objects pointing at each other but at nothing reachable simply don’t get marked.

The price is paid in two currencies. Memory: a collector needs room to let garbage pile up between collections. And time: marking costs work in proportion to what’s alive, and simple collectors stop the program while they do it. Modern ones (Go’s, Java’s G1 and ZGC, .NET’s, V8’s in Chrome) do most of the work alongside the program and split the heap into young and old generations. ZGC advertises pauses under a millisecond. You still pay in CPU, you just pay in small coins.

who uses it Java and Kotlin, C#, Go, JavaScript, Ruby, OCaml, Haskell, Dart and most Lisps.

Slide headroom down to 1.2× and watch the red stripes. Then try 3×.

Reference counting takes the opposite approach. Every heap object carries a number: how many references point at it. Copy a reference and the number goes up. Drop one and it goes down. At zero, the object is freed on the spot, no collector, no pause, and you know exactly when it happens.

That promptness is why Apple chose it. Swift and Objective-C use automatic reference counting (ARC): the compiler writes the increments and decrements for you. CPython counts too, which is why a file you stop using in Python usually closes right away.

Two catches. Every copy of a reference costs a write to memory, and atomic writes if threads share the object. And a cycle is invisible to it: a person who points at a flat whose tenant points back at the person keeps both counts at one forever. Swift asks you to mark one side weak. Python and PHP run a separate cycle collector now and then, just to find them.

who uses it Swift and Objective-C (ARC), Python, PHP, Perl, C++ shared_ptr, Rust’s Rc and Arc.

Run “a cycle”, then “a cycle, one side weak”. What changed when the last line ran?

Rust asked whether the compiler could do C’s bookkeeping, correctly, before the program ever runs. Its answer is ownership. Every value has exactly one owner, and when the owner goes out of scope the value is freed, right there, with a call the compiler puts in for you.

Hand a value to someone else and ownership moves: the old name is dead, and using it is a compile error, not a crash at 3 a.m. To let code look at a value without taking it, you lend it out as a borrow, &s. The borrow checker enforces one rule: many readers or one writer, never both, and no borrow outlives the value.

The reward is C’s speed and predictability without its three bugs, and safe sharing between threads too. The cost lands on the programmer: some perfectly good designs, graphs and doubly linked lists especially, have to be reshaped to please the checker, or reach for Rc and RefCell, which bring counting back.

who uses it Rust. C++’s unique_ptr and RAII are the unchecked ancestor; Swift and Mojo have since added ownership features of their own.

Try “use after move”, then “two writers”. Both are caught before anything runs.

Lobster, a language for writing games, asked a gentler question than Rust: what if we keep reference counting, but let the compiler skip every count it can prove is pointless? It calls the result compile-time reference counting.

While it type-checks, the compiler picks one owner for each new allocation and treats every other use as a borrow, much like Rust. Borrows need no counting at all. The difference is what happens when the analysis can’t make it work: where Rust stops with an error, Lobster quietly inserts a single count update for that one use and carries on.

Its author reports that this removes around 95% of the runtime count operations. The rest stay, so memory is still freed the moment the last owner lets go, with no collector and no pauses, which is what a game running at 60 frames a second wants. Cycles still leak, so Lobster prints a cycle report when the program exits, telling you where to break them.

Miri, the GPU-first language I’m building, belongs to this family, even though its compiler calls the pass Perceus. What it actually runs is non-atomic counts on heap blocks. Parameters are lent by default, and a whole-program pass infers which ones must be owned. Locals borrow out of those owned roots, and out is the only way to get a mutable reference. It does this on its mid-level IR rather than in the type checker, which keeps the compiler’s verifiers in play, and on the workloads where it matters it removes about as many count updates as Lobster reports.

What Miri adds is the part that matters most for buffers: structs and collections have copy-on-write value semantics. Assignment shares the memory, the first write to a shared value copies it, and the uniqueness checks behind that are hoisted or deleted by later passes. As for cycles, the compiler refuses the most direct kind, an object stored into its own field.

who uses it Lobster, and Miri with copy-on-write values on top. The same goal, counting less by proving more, drives Swift’s ARC optimiser and the Perceus family of plate VI.

Turn on the analysis, then add “keep a target list”. One +1 comes back. Why that one?

Perceus, from Microsoft Research and first built for the Koka language, makes reference counting precise. The compiler writes every count update itself and drops each reference straight after its last use, not at the end of the scope. The paper calls this garbage free: at any moment, only memory that will still be used is kept.

Then comes the trick. Functional code never changes data; it builds new data from old. Mapping over a list allocates a new cell for every old one, and the old ones die. But if an old cell’s count is one at the moment it dies, nobody else can see it, so its memory is reused for the new cell, in place. Purely functional code gets the speed of mutation. The authors call it functional but in-place.

Lean 4, the proof assistant and language, uses the same family of techniques (its creator co-wrote the Perceus paper). Cycles stay reference counting’s blind spot here too: Perceus frees everything else promptly, and leaves cycles to the programmer.

Miri’s compiler names its counting pass after Perceus, but what it runs is closer to Lobster’s ownership inference, with copy-on-write values on top: that’s in plate V.

who uses it Koka and Lean 4.

Run all three modes, then tick “list is shared” and run “+ reuse” again.