Notes
2026/11/07

Growing lists on the stack

Continuing along the lines of the sketch for mutable lists from a few weeks ago, what happens when we try to push an element onto a list that has reached its max capacity? The same question already came up in the context of an arena l:

If l is full, there are two choices: We could either grow l in place by doubling its capacity, moving the entire stack above it and shifting references accordingly, or we could simply keep x at the top of the stack, degrading to the normal mark-and-compact on return.

Growing a list or an arena in place by e.g. doubling its capacity requires moving and rewriting the entire stack above it. It's not enough to simply copy the memory, because we need to rewrite references that point below the new “gap” (if references are relative) or above it (if references are absolute).

Keeping the existing list or arena as it is and simply storing the new element at the top of the stack (together with a copy of the entire list in the case of a list) is a viable alternative in a functional language where references always point down, because existing references cannot observe the new element anyway.

But such a behavior is strange in the case of an arena, whose whole purpose is to make memory allocation and deallocation predictable: An arena at max capacity would degrade to the non-arena case for new elements.

The simplest solution is perhaps to simply double both lists and arenas whenever they would exceed max capacity and accept that the entire stack above it might move (and refs need to be rewritten). We could couple it with (optional) explicit initial capacity and a default capacity for mutable lists and arenas of maybe 8 or 16 stack slots. This keeps everything predictable and easy to implement.