How OCaml Locals Use a Separate Stack

In this installment of OCaml Unboxed, I continue exploring the local mode that my Jane Street colleagues and I are developing in an open-source compiler branch. A previous example reduced garbage-collected allocations using local annotations. Here I want to show where the memory goes and why that works.

The example’s main function, doit, loops with an iteration variable and a list. It calls init to construct the list and then counts multiples of five. First, imagine the program without local annotations and follow the allocations on the heap.

init constructs a linked list of cons cells on the heap. The list variable points to its beginning. In the next iteration init constructs another list, and list changes to point to the new one. The old cells are no longer reachable through that variable.

When garbage collection runs, the simplified picture is to trace from roots such as stack variables, mark reachable heap objects and reclaim objects that cannot be reached. The current list remains live; the old list can be collected, making space for later allocations.

Garbage collection is valuable: it supports immutable functional programming and makes programs easier to reason about and develop. But finding live data and reclaiming the rest takes work. In the mark-and-sweep picture, collection can pause program execution and touch memory that may displace more useful cached data.

Most programs at Jane Street are fine with garbage collection. For latency-sensitive cases, however, we want to avoid those pauses and other slowdowns. That performance goal motivated our investigation of locals.

Now consider the local version. The call stack still holds doit and its variables, but init allocates the list cells in a separate area I call the local stack. This is neither the ordinary call stack nor the garbage-collected heap.

init finishes and returns the locally allocated list, which doit can use to count multiples of five. The loop body is a region: local values allocated in that region cannot escape it. When the iteration ends, the analysis guarantees that those allocations are no longer needed.

The runtime can reclaim the region’s local allocations together and reuse the same memory in the next iteration. The deallocation can be as simple as changing the pointer used for the next allocation. It avoids the mark-and-sweep work described in the heap example.

The separate local stack matters because init can return before its caller finishes using the list. Values created inside an exclave can survive a function return while still being limited to their enclosing region. Function frames and regions do not always have identical lifetimes, so the local allocations cannot simply live in init’s call-stack frame.