Stephen Dolan on Memory Management, Garbage Collection, and OCaml

Stephen Dolan — compiler engineer at Jane Street and creator of the command-line tool jq — joins host Ron Minsky for a tour of how programs manage memory, why OCaml’s garbage collector works the way it does, and the language extensions now under development to give OCaml programmers finer-grained control over memory without sacrificing the ergonomics that make the language distinctive.

Key ideas

1. Every program must decide where to put its data, and the two basic answers are the stack and the heap. The stack (think of a pile of trays in a cafeteria) holds short-lived local variables: when a function returns, its tray slides off and the memory is immediately free. The heap handles everything with a more complicated lifetime — data that outlives a single function call — and requires a separate mechanism to decide when that memory can be reclaimed.
2. Garbage collection automates heap reclamation, and the two main techniques trade different costs. Tracing collectors periodically follow every live pointer from known roots (global variables, active function frames) to find all reachable objects; anything unreached is garbage. Reference counting instead tracks how many pointers point to each object and reclaims it the moment the count reaches zero — but struggles with cycles and can be slow under multithreading. OCaml uses a tracing collector with two levels: a fast ‘minor’ heap for short-lived allocations (reclaimed cheaply by scanning only the small new region) and a larger ‘major’ heap for longer-lived data, swept incrementally to avoid long pauses.
3. Prefetching cut OCaml’s marking phase two- to three-fold by hiding memory latency. The garbage collector’s marking phase is essentially a pointer-chasing marathon — exactly the pattern that causes the most cache misses, where the CPU waits hundreds of cycles for each new memory location. Dolan and Will Hasenplaugh added a small queue in front of marking: instead of fetching each object and immediately processing it, the collector issues a hardware prefetch for an incoming object, adds it to the queue, and processes an object fetched ten steps earlier — so ten prefetches are in flight at once, approaching the machine’s raw memory bandwidth rather than serialising every cache miss.
4. Safe stack allocation, via ‘local types’, avoids heap allocation for temporary data without requiring Rust-style lifetime annotations. In Rust, safe stack allocation is expressed through explicit lifetime variables in types, which is powerful but forces programmers to annotate higher-order functions and disables type inference in those cases. OCaml’s local-types design instead marks functions as ‘non-capturing’ — the compiler knows they will not squirrel a reference away into a global — which lets callers safely pass stack-allocated values without any lifetime variables appearing in types, preserving OCaml’s signature property that code can be written without type annotations.
5. Unboxed types allow compact, pointer-free memory layouts for primitives and structs. OCaml currently represents almost everything — including a 32-bit integer — as a pointer to a heap-allocated block, keeping the runtime uniform but wasteful. Unboxed types let values such as a character, an integer pair, or a struct exist without any heap allocation at all, living directly in registers or on the local stack. A kind system (think: a type of a type) tracks which layouts are compatible with polymorphic functions, preserving separate compilation whilst opening the door to C-style dense memory layouts.

Content

The stack, the heap, and what can go wrong

Dolan opens with the two-part foundation of runtime memory. The stack works because function calls are naturally last-in-first-out: each call pushes a frame, the return pops it, and the memory is reused immediately with no bookkeeping. The heap handles everything else — data whose lifetime does not align neatly with a single call — and is where the hard problems live.

In C, heap memory is managed manually with malloc and free. Any slip — freeing memory twice, or reading it after it has been freed — is not a minor inconvenience but an exploitable security vulnerability. Dolan draws a sharp distinction between that unsafe style and what Rust provides: the same low-level control, but with the compiler verifying statically that all memory management is correct, so no mistake can go undetected. He is candid that Rust’s approach suits low-level code where layout matters, but becomes burdensome for higher-level work — linked tree structures, type checkers — where explaining to the compiler why each reference is safe costs more than a garbage collector would.

Tracing versus reference counting

The two main automatic strategies differ in what they traverse. A tracing collector walks all live objects; a reference counting collector walks all dying objects. Ron Minsky notes the common misconception that reference counting is faster: in a multithreaded setting, updating a reference count requires atomic operations (operations the CPU must complete without interruption, which are expensive), and when the last reference to the root of a large tree disappears, the whole tree must be traversed synchronously to decrement every count — potentially a large, unpredictable pause. A well-implemented tracing collector, by contrast, can divide its work into millisecond slices.

The genuine advantage of reference counting is determinism of when objects are freed — useful for managing non-memory resources such as GPU buffers. Dolan qualifies this: you only know an object is freed when its count reaches zero, but you cannot easily guarantee from the caller’s side that the count is zero, since some hidden code path may have retained a reference.

OCaml’s generational collector and the prefetch breakthrough

OCaml’s collector is generational — based on the empirical observation, confirmed across radically different programming languages, that recently allocated objects tend to die young. New objects land on a small minor heap and are collected cheaply by scanning only that region; survivors are promoted to the major heap, which runs an incremental mark-and-sweep collector. Incremental means the marking and sweeping work is sliced into short bursts so no single pause is visible to users.

The marking phase is structurally the worst case for hardware caches. It chases pointers to random locations across a heap that may be gigabytes large, while the CPU’s fast cache is only kilobytes: every pointer follow is likely a cache miss costing around 300 cycles. Modern processors can, however, sustain roughly ten such requests in parallel if the software is written to take advantage of this. Dolan and Hasenplaugh inserted a small ring buffer into the marking loop: each newly discovered object is prefetched and queued; the object processed is one that was queued ten items ago, by which time its data has very likely arrived from memory. The result was a two- to three-fold speedup on the marking phase of a 20-year-old, well-regarded collector — a result that surprised even its authors. Dolan attributes part of the outsized gain to OCaml’s tagging scheme: each pointer-width word on the heap has its low bit set to zero if it is a pointer and to one if it is an integer, so the collector can classify fields without consulting any side table, reducing the number of memory accesses that must be made during marking.

Local types: safe stack allocation without lifetime variables

Stack allocation has obvious appeal — the memory is reused immediately, is guaranteed to be in the CPU’s fast cache, and contributes nothing to the next garbage-collection pause. The challenge is safety: a stack-allocated value must never be referenced after its stack frame is freed, yet OCaml programmers frequently pass values into functions they did not write.

Rust solves this with lifetime variables: every reference type carries a lifetime annotation, and the compiler verifies that nothing outlives its allocation scope. The cost is that higher-order functions — functions that accept other functions as arguments, common in OCaml — must declare that their callback is polymorphic over lifetimes, which requires a feature called higher-rank types that defeats type inference.

OCaml’s local-types design takes a narrower path. Rather than naming lifetimes, it marks functions as non-capturing: the type system records that a function will not store its argument in any persistent location. A caller can then safely pass a stack-allocated value to such a function, and the compiler enforces the guarantee without any lifetime variable appearing in the source code. The trade-off is expressiveness: Rust’s lifetime variables can encode complex multi-argument lifetime relationships that local types cannot; but because OCaml still has a garbage collector for those cases, the narrower mechanism covers the common case cleanly.

Dolan also describes how ‘smart constructors’ — helper functions that allocate on the caller’s behalf — fit into the design. By separating the code stack (function return addresses) from the data stack (local allocations), a constructor can leave its allocation in place when it returns, so the caller finds the value exactly where a direct allocation would have put it, without any copying.

Unboxed types and the cost of uniformity

OCaml’s current memory model is deliberately uniform: every value is either an immediate (a tagged integer fitting in one machine word) or a pointer to a heap block. This uniformity makes generic functions like List.map possible without specialisation — the function need not know the concrete type of list elements, because every element, whatever its actual content, is represented as a single word. The price is that a 32-bit integer occupies a three-word heap block (header, tag, and the integer itself), and passing two values to a function requires boxing them into a heap-allocated tuple.

Unboxed types dissolve this by extending the kind system — the level above types, describing memory layout — to include layouts beyond ‘one word on the heap’: eight-bit characters, 32-bit integers, unboxed tuples living purely in registers. A function polymorphic over ‘all types of layout value’ behaves exactly like today’s OCaml; functions polymorphic over ‘all types of layout immediate’ or ‘all types of layout unboxed-float’ are new, and can operate on compactly represented data without heap allocation. Separate compilation is preserved because kinds, not concrete types, determine calling conventions.

Dolan also describes how the kind system solves a 20-year puzzle in OCaml: the option type (representing a value that may or may not be present) currently requires a heap allocation even for string option, because the runtime must distinguish Some None from None in nested options. With a kind of ‘non-nullable’ types, the compiler can guarantee that no nested nulls arise and use a null-pointer representation instead, eliminating the allocation.

The interface between automatic and manual memory

A thread running through the conversation is how difficult it is to mix automatic and manual memory management gracefully. Each approach optimises for a different workload — reference counting reclaims a large buffer immediately; tracing collection keeps immutable functional data structures cheap — and the seam between the two tends to surface awkward corner cases. Dolan holds that this is an inherently harder design problem than either extreme, and that OCaml’s value is in threading that needle: garbage collection by default, opt-in stack and unboxed allocation when layout matters, without requiring programmers to annotate most of their code.

Related

• Stephen Dolan — speaker
• Ron Minsky — host
• The Future of Software Engineering — theme; the conversation situates OCaml’s memory-management evolution within the broader question of what control programmers should have over runtime behaviour