Part IV · Memory Management — garbage collection and the alternatives

Automatic memory management asks one question — *when is a piece of memory no longer reachable, and who reclaims it?* — and the answers split a language's entire performance, latency, and ergonomics profile. This chapter maps the field: the tracing-GC family, the reference-counting renaissance, mark-region collectors, and the approaches that avoid a runtime collector altogether. The decision for Koda lives in stack-RFC-034; this is the ground it stands on.

---

1. The tracing family (reachability from roots)

A tracing collector periodically finds what is reachable from a set of roots (stack slots, registers, globals) and reclaims the rest.

• Mark-sweep — mark reachable, sweep the rest. Simple; fragments the heap.
• Mark-compact / copying (semi-space) — moves live objects together, eliminating

  fragmentation and enabling bump-pointer allocation (fast). Cost: it moves objects, so it needs precise roots (know exactly which words are pointers) to update references.

• Generational — the weak generational hypothesis: most objects die young. Collect a

  small young generation often (cheap) and promote survivors to an old generation collected rarely. A write barrier records old→young pointers. This is the workhorse of managed runtimes and the family Koda currently implements (young-gen copying + precise roots, #845#730#834).

• Concurrent, low-pause — the modern frontier: collect while the program runs, keeping

  pauses sub-millisecond even on TB heaps.

  • Azul C4 — the pioneer of continuously-concurrent compaction.
  • ZGC (OpenJDK) — colored pointers + load barriers, region-based, concurrent

    compaction; generational ZGC landed in JDK 21 (2023).

  • Shenandoah (Red Hat) — concurrent evacuation via load-reference barriers.
  • Go GC — concurrent tricolor mark-sweep, non-moving, write barriers; trades

    compaction for simplicity and short pauses.

The cost of this family: barriers on loads and/or stores — real throughput overhead and deep implementation complexity.

Precise vs conservative roots. A conservative collector guesses which stack words are pointers (can't move objects safely; can leak). A precise collector knows exactly — a prerequisite for any moving/compacting scheme, and the substrate the reference-counting approaches below also want. (Koda's migration from conservative to precise roots is exactly this enabling investment.)

---

2. The reference-counting renaissance

Each object carries a count of references; when it hits zero, it is freed. For decades RC was dismissed as "slow and can't collect cycles." That verdict is out of date:

• Deferred / coalesced / biased RC made the counting cheap (batch and skip redundant

  updates).

• Perceus (Reinking, Xie, de Moura, Leijen — PLDI 2021): the compiler *nserts precise

  inc/dec at compile time, specializes drop, and — the key idea — does reuse analysis: when an object's refcount is provably 1, a "functional" update is compiled into an in-place mutation ("functional but in-place", FBIP). This makes RC competitive with or faster than tracing, and deterministic (no stop-the-world). Used in Koka and Lean 4 (a performance-critical theorem prover) and Roc*

• LXR (Zuo, Blackburn et al. — PLDI 2022): RC + a backup Immix trace for cycles.

  Beats production tracing collectors (e.g. G1) on latency and throughput simultaneously — arguably the strongest GC result of recent years.

• Nim ARC/ORC, Swift, Python — production imperative languages built on RC; ORC

  adds a cycle collector to ARC.

The catch: plain RC leaks cycles. Modern RC pairs with a backup cycle collector (LXR, ORC) or leans on ownership/uniqueness to make cycles rare. And Perceus's reuse magic is strongest in functional settings; in imperative/OOP languages the RC core still transfers cleanly (Swift/Nim prove it) but the automatic FBIP upside is partial and must be measured.

---

3. Mark-region and pluggable frameworks

• Immix (Blackburn & McKinley — PLDI 2008): a mark-region collector — coarse regions

  with fine lines, great locality, and opportunistic evacuation to defragment. The basis of a large fraction of modern GC research (and of LXR's backup trace).

• MMTk (Memory Management Toolkit, reimplemented in Rust): a framework that lets a runtime

  plug in different collectors behind one interface. Being integrated into OpenJDK, V8, Ruby, and Julia. The model to copy if a language wants to experiment with collectors without rewriting its runtime — but a heavy dependency to stand up.

---

4. Beyond GC — compile-time and ownership approaches

Some languages avoid a runtime collector by resolving lifetimes statically:

• Ownership + borrow checking (Rust) — single-owner values freed deterministically at

  scope end; the borrow checker proves aliasing safety at compile time. Zero GC, zero pauses, predictable. Cost: real programmer burden (the borrow checker's learning curve).

• Regions / arenas — allocate into a region, free the whole region at once. Manual in

  Zig/Odin; inferred in MLKit (Tofte-Talpin region inference) and Cyclone. Arena speed with no per-object bookkeeping.

• Linear / affine types — types that enforce "use exactly once / at most once", enabling

  the compiler to insert deterministic frees. Austral, and the higher-RAII layer of Vale.

• Generational references (Vale) — a genuinely different bet: cheap liveness checks via

  per-object generation numbers plus regions and single ownership, targeting memory safety without GC and without Rust's borrow checker. Promising but research-stage — not production-proven at scale.

---

5. How to choose

There is no universally "best" collector — the axes trade against each other:

The greenfield-language angle. A brand-new language with full control of its compiler is the ideal place for compile-time-assisted memory management: the modern cohort of compiler-controlled languages did not choose tracing GC — Lean 4 and Koka chose Perceus RC + reuse, Rust chose ownership, Vale chose generational references. Tracing generational GC is the model of mature dynamic runtimes (Ruby, early Go), retrofitted where the compiler can't help. For a new language that also needs to beat a systems language on a hot path, this distinction is decisive.

---

Koder Stack anchor (D6 — decision lives elsewhere). Koda's own choice on this axis is not made in this compendium. It is recorded in stack-RFC-034 — Koda memory-management axis (engineering canon): tracing generational GC as the bridge to self-hosted-green, with Perceus-style precise RC + reuse as the long-term north-star, gated on a measured win against the self-hosted-first G2 performance gate (Koda ≤ Rust × 1.05 on a hot path). This chapter is the reference; that RFC is the decision — one fact, one home.