Stacky Heap

A new memory management approach

I recently implemented garbage collection for Orchard, a self-hosted programming system with immutable values.

A straightforward solution would have been reference counting: You store a counter at every object of how many references point to it and you free the memory when that counter reaches zero. Reference counting is a good fit for languages with immutable values and eager evaluation; because values can only refer to previously created values, there are no cycles, avoiding the major weakness of reference counting. Even better, some languages like Koka use the reference count to opportunistically mutate values while keeping immutable semantics if the count is 1.

However, reference counting has downsides: The operations for adjusting the counter can be expensive. And exception handling becomes complicated because if you only executed part of some function, the reference counters might be in an inconsistent state.

I want to support exceptions in Orchard, so I took another approach: A stacky heap.

In the beginning, I allocate a big area of memory. Whenever you need memory for a new value, I give out some of that memory, from left to right. This way of giving out memory is well-established and usually called "bump allocation" or "arena allocation".

Now comes the cool part: Because the immutable objects can only refer to previously created objects, pointers inside the heap only ever point to the left. This enables partial garbage collection! When you call a function that does allocation-heavy work, but produces a small value, you can garbage-collect only the values allocated by that function.

The way this is surfaced in the language is through a built-in collect_garbage function. It's a higher-order function that takes a lambda without arguments. It just runs the lambda and returns its value, but it frees all intermediary objects that are not referenced by the return value.

input = ...
output = (collect_garbage (\ () (expensive_operation input)))

Partial garbage collection

Let's say some values are allocated on the heap:

Let's say we want to call a function with a and c and garbage collect all its intermediary allocations. To do that, we remember the current size of the heap. Then, we just call the function, which may allocate lots of objects:

Let's say k is the return value. We can do a standard mark-and-sweep garbage collection on everything after the call boundary: Starting at k, we do a depth-first traversal of all dependencies, marking them as needed. If we cross the call boundary (the blue line), we stop marking.

Then, starting at the call boundary, we go over the objects. We keep only marked objects, compacting them together and overwriting the other ones.

What even is this?

In Borrow checking, RC, GC, and the Eleven (!) Other Memory Safety Approaches, Evan Ovadia describes how several memory safety approaches can be blended together. My stacky heap combines aspects of several techniques:

• My entire heap is basically a stack of nested arenas or regions, which is also my preferred memory management strategy in Zig. Like some parts of Ada/SPARK, my pointers can only point left and objects can't outlive dependencies on the left.

• I use tracing garbage collection to condense a function call's allocations to its return value. Generational garbage collection has multiple buckets of objects that can be garbage-collected independently with different frequencies. If you squint your eyes a bit, it's like every call of collect_garbage starts a new, nested generation that is only collected once.

• Like with manual memory management, you decide when you want memory to be collected. You are responsible to call collect_garbage at functions that do a lot of internal work, but only return small amounts of data.

So, there you have it: I created a new memory management approach that combines aspects from arena allocation, tracing garbage collection, and manual memory management. I'm curious how this adventure continues.