Richard Eisenberg: How OCaml Locals Reduce Garbage-Collected Allocation

Richard Eisenberg demonstrates how OCaml locals can reduce garbage-collected allocation. Preventing a value from escaping a region is useful in itself, but Jane Street is also interested in the performance benefit of controlling where short-lived values are allocated.

The demonstration uses Jane Street’s experimental compiler branch. At the time of the video, the team intended to work with the community on bringing these features upstream. The example builds many small lists and counts the elements divisible by five.

The function runs a loop 10,000 times. Each iteration chooses a random length below ten, creates a list of random integers below 100 using List.init, and iterates through it, incrementing a reference when an element is divisible by five. A fixed random seed makes the result reproducible.

To see the allocation cost, Eisenberg consults the OCaml runtime documentation. Setting OCAMLRUNPARAM to v=1024 prints garbage-collection statistics at program exit, including allocated words. The initial bytecode run reports roughly 214,000 allocated words; reducing the number of iterations reduces the count.

Each list is needed only within its loop iteration. In a language with manual memory management, one might explicitly free it there; locals aim to express the lifetime without manual freeing. Every function and every loop body defines a region, and a local value must not escape its region.

Marking the list local initially produces an escape error when it is passed to List.iter. In the compiler and library version demonstrated, the standard library function does not express the required locality. Eisenberg writes a recursive iter that handles an empty list or applies a function to the head and recurses on the tail.

The custom iterator compiles, but the allocation count remains high. He switches from ocamlc, the bytecode compiler used initially, to ocamlopt.opt, which produces native code for the machine. The count falls, but it is still much higher than the near-zero garbage-collected allocation he is seeking.

To understand the iterator’s behavior, Eisenberg writes an explicit type annotation. Without that annotation, the compiler can infer that the list does not escape. A type without a local annotation gives no such guarantee, so the compiler conservatively treats it as potentially escaping and rejects the call.

Adding a local annotation to the list argument fixes that part of the type. A local list also means its elements cannot escape, so the callback must accept a local element as well; otherwise it might save the value elsewhere. With both annotations, the iterator type-checks.

Even then the program still allocates. The local variable is assigned a list made by List.init, whose result is not guaranteed to have been allocated locally. A global value may be used locally: restricting a variable so it cannot escape does not retroactively change where the value was allocated.

To make the list local from the moment of creation, Eisenberg writes a replacement init. A recursive loop takes an index and an accumulator, applies a function to each index, and conses the result onto the accumulator. It starts at length minus one and finishes when the index falls below zero.

The replacement initially compiles and produces the expected result, 8,987, once it is actually called. Without locality annotations, however, it does not solve the allocation problem. He adds a type saying that the element-producing function returns a local value and init returns a local list.

The compiler then reports that a value escapes its region. The recursive loop needs a local accumulator, but return or tail position introduces another issue. A non-tail annotation temporarily gets further, though Eisenberg wants to preserve a tail call and returns to the issue.

He gives the loop an explicit type accepting and returning a local list. A syntax error illustrates that local_ is associated with the function arrow: placing parentheses in the wrong place prevents the annotation from reaching it. Once corrected, the compiler identifies another escape at the return.

Every function defines a region, but the list being returned should be allocated outside the function’s own region. Eisenberg adds exclave, which ends the region early for that expression, and removes the temporary non-tail annotation. The outer init also needs an exclave for its local result.

With these changes, the program compiles. The local version reports roughly 90,000 allocated words, compared with about 177,000 when he switches back to List.init. The reduction is useful, but smaller than he expects, so he investigates the function arguments and closures.

Both iter and init accept functions. The function that generates a random value captures nothing from its environment, so the compiler can avoid allocating a closure for it. The iterator callback refers to the count reference, however, and captures state from its environment.

He marks the function arguments local as well. This exposes another escape issue: the recursive loop captures the local function, so the loop itself needs to be local. A local loop cannot then be used outside its region in an exclave; moving the exclave outward resolves that conflict.

At first the measurement still does not improve, because he has accidentally called List.init again. After changing the call to the custom init and recompiling, the program reports very little garbage-collected allocation: the screen shows 2,146 allocated words while the result remains 8,987.

The important distinction is that memory is still allocated for the local values. The counter is not saying the program uses no memory: it is showing far less allocation handled by automatic garbage collection. At the end of each loop region, that local memory can be reclaimed as a group, reducing work for the collector and potentially improving latency.

Eisenberg closes by pointing to the example code and says the next video will explain more about how this works and where the memory goes. The demonstration’s numbers apply to this small program and the experimental compiler used in the video.