Stephen Dolan on Memory Management, Garbage Collection, and OCaml

Ron Minsky introduces Stephen Dolan of Jane Street's tools and compilers team. Dolan created jq, researched algebraic subtyping, and has worked on OCaml's multicore garbage collector and language features that give programmers more control over memory.

Dolan starts with the basic requirement: data needs memory without different values occupying the same space at once. A fixed map can suffice for tiny embedded programs, but more general programs need ways to allocate and reclaim space as their data changes.

The stack suits values whose lifetimes follow function calls. A function gets a frame and local storage; when it returns, that storage can be popped in last-in-first-out order. Data with less predictable lifetimes instead needs heap allocation and a method for deciding when the space can be reused.

In C, malloc and free put that responsibility on the programmer. Freeing twice or using memory after it is freed can lead to security vulnerabilities. Safe languages instead use mechanisms such as garbage collection or static verification of ownership and borrowing to prevent these errors.

Dolan says OCaml traditionally leans heavily toward garbage collection, although that is not always the best performance tradeoff. The team is exploring ways to give programmers more control over lifetimes while retaining safety. Minsky summarizes collection as approximating what is still needed, retaining at least all reachable data and possibly some extra.

Dolan identifies two broad families of automatic collection. A tracing collector starts from roots such as live local and global variables and follows references. Objects not reached by this traversal cannot be used through those roots and their memory can be reclaimed.

Reference counting instead maintains a count of references to each object. Creating and destroying references adjusts the count, and an object can be reclaimed when its count reaches zero. Minsky points out the classic weakness: a cycle can retain positive counts even when nothing outside it can reach it.

Dolan notes a useful comparison: tracing walks the live side of the graph, while reference counting propagates through objects that are becoming dead. To handle cycles, a reference-counted system can periodically trace, as Python does, or use weak references that do not keep objects alive; the latter requires programmer cooperation.

The familiar claim that reference counting is simply faster is misleading, Dolan says. Comparisons are difficult, and maintaining counts can be expensive, especially when multithreaded updates require atomic operations. Its advantage is often prompt reuse: dead memory may be available immediately rather than waiting for the next tracing phase.

A rough generalization is that reference counting may use less memory while tracing may run faster, but tracing offers a spectrum. Collecting more frequently can reduce memory use at the cost of more work; collecting less frequently can improve throughput while using more memory. OCaml's collector exposes a relatively simple tuning tradeoff, Dolan says.

Pause times are not a simple victory for either approach. Releasing the final reference to a large tree can force a reference-counted system to traverse the entire tree. A tracing collector such as OCaml's can split marking and sweeping into short incremental slices rather than stopping for a full traversal.

Lazy destruction or deferred count propagation can also spread reference-counting work, but may sacrifice prompt finalization while retaining counting overhead. Dolan notes a strong case for ordinary reference counting: a large buffer with no outgoing references can be freed and reused promptly without walking a graph.

Benchmark results depend heavily on workload. A tracing collector may retain many such buffers before the next cycle, and APIs in garbage-collected languages often ask callers to provide reusable buffers. Minsky notes that programs evolve toward the efficient idioms of their existing memory manager, complicating comparisons.

Prompt finalization can help manage non-memory resources such as scarce GPU memory, but Dolan cautions that reference counting does not prove the reference being dropped is the last one. Another component may have kept a reference. Ownership or uniqueness can make the point of release easier to establish locally.

Dolan distinguishes unchecked C-style manual management from a safe system such as Rust. Static checks can enforce a disciplined manual style and prevent use-after-free, but explaining lifetimes to the compiler can be burdensome for highly connected structures such as those in a type checker. A tracing collector can be easier there.

The benefit of precise control is performance, but ownership also helps prevent accidental aliasing. If a function has the only mutable reference to a value, changing it cannot unexpectedly alter another part of the program through a shared alias. This permits efficient mutation without losing modularity.

Dolan notes that programmers often defensively copy mutable structures to avoid shared-mutation bugs, even when the copy proves unnecessary. Two alternatives are type-level ownership and borrowing, as in Rust, or immutable data structures managed by a collector, as in many OCaml programs. He would like to use both approaches in one language.

Minsky observes that Rust and OCaml have related sensibilities despite their differences: shared mutation is the core problem, and one approach restricts sharing while the other restricts mutation. The speakers then turn to making automatic garbage collection faster, including work Dolan did on OCaml's collector.

OCaml's collector is generational. Dolan first describes its major collector, which periodically starts from roots, marks reachable objects by following references, and then sweeps unmarked objects back into the allocator. This is a mark-and-sweep design.

The major collector is incremental: it divides marking and sweeping into small slices and preserves its state between them. Minsky notes why that matters for latency-sensitive applications; Dolan adds that even an interactive program can be unpleasant if a full collection of a large heap pauses it for seconds.

The generational hypothesis observes that recently allocated objects are especially likely to die young, while objects that have already survived tend to live longer. Dolan says this pattern has held across many languages and styles of programming, making a separate young generation useful.

The minor heap allocates objects in a contiguous region with a bump pointer, a very cheap operation. When the region fills, a minor collection finds live objects and promotes or otherwise preserves them; the rest can be discarded together. Often 90% or more of allocations disappear before needing the more expensive major allocator.

At the time of the discussion, OCaml's existing collector used a single lock around a shared heap; Dolan had also worked on a multicore design being pushed upstream. Minsky turns to another surprising result: work by Dolan and Will Hasenplaugh made the marking phase roughly two to three times faster.

Dolan explains why pointer chasing is slow. A processor can stream sequential data from an array at high bandwidth, but following a linked list requires a new, dependent memory request for each element. In his example a cache miss can take around 300 cycles, so latency dominates despite high available bandwidth.

Minsky compares a computer's memory subsystem to a distributed system: bandwidth may be high, but dependent round trips are expensive. Garbage-collector marking is a particularly difficult workload because it follows pointers to scattered locations and can spend much of its time waiting for cache misses.

Modern processors can have multiple cache misses in flight. Dolan's change uses prefetch instructions and a small queue: when the collector discovers an object, it requests the memory early and delays processing it while working on other queued objects. The marking order is flexible, so several requests can overlap.

Each individual miss still has its latency, but ten concurrent requests can greatly increase the rate at which useful cache lines arrive. The queue makes better use of memory bandwidth while traversing a large, scattered heap. The improvement surprised both speakers in a mature, well-regarded collector.

Dolan suggests two possible reasons for the strong result: newer processors support more memory-level parallelism, and OCaml's tagged representation makes it inexpensive to distinguish integers from pointers without separate layout lookups. He explicitly calls the comparison with other collectors speculative.

Minsky asks whether programmers should use software prefetching more generally. Dolan says it can help, but timing matters: a request made too late has not finished when needed, while one made too early may be evicted from cache. Garbage collection is unusually convenient because its traversal order can be rearranged.

In list.map, for example, prefetching the next list node might be too late when the mapped function is trivial, or too early and wasteful when it is slow. The next element may itself point to more data that was not prefetched. A library cannot always know the timing and data layout of every caller.

Minsky calls this a lack of composability in performance: an optimization can help one context and hurt another. Dolan adds that cache behavior changes discontinuously. A small change can move an access from a cache hit to a far more expensive miss, producing a large performance difference.

The conversation moves from improving the collector to giving programmers more control. Dolan explains that many temporary structures live only briefly, yet ordinary OCaml allocates them on the minor heap. Even cheap allocations consume space and bring the next minor collection closer.

A stack-like allocation can be reclaimed by restoring a pointer rather than waiting for collection. It also reuses recently touched memory that is likely still in cache. Minsky contrasts a larger minor heap, which avoids premature promotion, with a smaller one, which can improve cache locality; local allocation can capture benefits of both.

Dolan contrasts Go's largely best-effort escape analysis with the desire to express non-escape in an interface. The safety problem is passing a reference to local data into another function: if the callee stores it globally and the local region ends, the saved reference would dangle.

Rust addresses this with lifetime variables attached to references. A function that accepts references of any lifetime cannot save one in a global requiring a static lifetime. The type system checks relationships among lifetimes so a caller can safely pass stack-allocated data.

Higher-order functions complicate the story. A callback passed to a function may need to work for any lifetime created inside that function, requiring higher-ranked types. Rust supports such mechanisms, but Dolan says they are substantial type-system machinery and can limit inference, requiring annotations.

For OCaml, where users expect extensive type inference, the proposed local design instead expresses directly that a function does not capture an argument. A caller can pass local data to such a function without lifetime variables or higher-rank polymorphism in the common case.

That choice is less flexible than Rust's lifetime system, which can express intricate relationships among several arguments and results. But OCaml would keep its garbage collector for difficult cases. Both speakers want a default that remains easy to use, with more control available where it is valuable.

Minsky asks about smart constructors that allocate a local value in a helper and return it to the caller. A conventional call stack makes this awkward because the callee's frame disappears on return, and the caller may not know the size needed in advance.

The proposed design separates the call stack from a region for local allocations. Usually their lifetimes align, but a constructor can leave an allocation in the local region for its caller while returning through the call stack. This avoids copying the object across a return-address boundary.

By default, local allocation regions follow function calls. A function that creates an allocation intended to outlive its own frame needs an annotation. Dolan says the team rejected simply putting everything on the local stack automatically: values could then remain there too long and make the stack grow excessively.

Minsky turns to the heap. OCaml's uniform representation is simple, but data can be scattered across many pointer-linked allocations, and small values may occupy full machine words. The proposed unboxed types aim to give programmers more control over representation.

Dolan describes inlining one record inside another so its fields sit together instead of requiring a separate block and pointer. He also gives the example of an OCaml int32 represented through a pointer to a larger block: uniformity helps the runtime, but it is expensive for applications processing many 32-bit integers.

Unboxed representations can reduce indirection and sometimes remove a heap allocation altogether. Today, passing two values under one tuple name can require a heap block, whereas passing them as separate arguments avoids it. The desired feature would let one logical value carry multiple machine-level parts.

This interacts with polymorphism. A generic List.map can take an element of an unknown type and pass it to a function without generating a separate implementation for every type, because ordinary OCaml values share a uniform calling representation. A float or multiword structure can fit that convention by being boxed behind one pointer.

Minsky asks whether whole-program specialization could solve the problem. Dolan says specialization or monomorphization works in many designs but becomes harder with polymorphic record fields and first-class modules, where a polymorphic function can be stored and later called at different types. It also increases code size and compilation work.

Separate compilation and incremental builds are valuable in practice. Dolan also describes just-in-time specialization as another point in the design space: it generates versions when needed, but introduces compilation pauses at runtime. He sees no universally superior approach, especially alongside advanced modular features.

Their proposed design keeps generic implementations and separate compilation but adds a way to express that a polymorphic function works over types with a particular layout. A function might support all types fitting an integer register or all of a suitable floating-point layout rather than every conceivable representation.

Minsky identifies this as a kind system: kinds classify types by properties such as layout. Dolan says the existing uniform representation corresponds to a kind called value, while new kinds can describe immediate values or unboxed tuples of a particular width. Polymorphism can remain generic within one layout.

An unboxed tuple of two integers can behave like two local machine-level values rather than one pointer to a heap object. Passing it uses multiple argument slots and returning it can return multiple parts without an intermediate allocation. Kinds help determine the calling convention and register requirements.

Dolan connects the idea to work on kinds and calling conventions. Functions with compatible kinds can use a uniform convention, while different layouts may require different registers. The aim is not only to pack heap objects better, but also to avoid heap representation where it is unnecessary.

Unboxed data can be boxed when a heap object is needed, but the collector imposes restrictions. In the design discussed, it expects a block either to contain fields it knows how to scan or no pointers at all. A mixed pointer-and-float tuple can be passed unboxed but cannot necessarily be stored together in a heap block.

Minsky notes that an unboxed value has no single stable location to mutate. Dolan explains that a mutable outer structure can nonetheless support operations that look like changing inner fields. At the time, some combinations would produce a compiler error; lifting collector restrictions would be separate work.

Variants raise further questions. Dolan describes inlining one variant into another as relatively straightforward, while returning an unboxed variant is harder: cases may have different sizes and require different classes of registers. The compiler backend discussed did not yet support a result layout that varies by case.

Those difficulties helped motivate local allocation as a simpler alternative for some cases. A locally allocated variant keeps the ordinary representation but is reclaimed cheaply. Minsky notes that local allocation can reuse existing types and code, while unboxed layouts may require separate types and limit polymorphism.

For an option, an efficient nullable representation is tempting: Some value otherwise needs an extra block. But nested options must distinguish None from Some None. Minsky notes that such nesting can arise naturally behind an abstract type, so collapsing the cases would break meaningful distinctions.

Dolan sketches a proposed nullable type allowed only when the underlying type is known not to be nullable. A non-nullable kind could enforce that constraint and reject nesting of the specialized nullable representation, avoiding ambiguity while allowing common cases to use a distinguished value.

Minsky remarks that the efficient representation of options has been discussed for decades. Dolan describes the tradeoff between finding a compact representation for every case and arranging the type system so a problematic case cannot arise. The closing theme is the difficulty of combining automatic convenience and explicit control safely in one language.