2 ms·
> Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array. Instead of referring to children via pointers, Ex
by kazinator 3y ago
> Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array. Instead of referring to children via pointers, Exprs will refer to their children using their indices in that array.
This isn't flattening; it's just an alternative heap representation. The shape of the AST hasn't changed. It's been done in many languages before; such as Lisps (packing cons cells and other objects into arrays, using bump allocation, and indices for pointers and such).
Objects being in an array makes them convenient for GC to traverse them in a sweep pass after the marking is done. Marking walks the graph to find the reachable objects; sweep goes trough the flat arrays to clear the GC bits, and indicate unreachable objects for recycling.
I don't think you will easily find a semi-serious Lisp implementation that just mallocs every cons cell individually. You'd have to put them into a global linked list to be able to do the sweep part of GC. Or a global array that just contains pointers. I've seen at least two toy Lisp project someone banged up in one weekend in which cons cells were malloced and leaked; GC was left as a giant TODO.
Global arrays can end up happening anyway, even if cells come from a packed array heap. E.g. if you implement generational GC in a non-copying allocator, one way to round up the baby objects so you can sweep them in a fast GC cycle is to add them into an auxiliary array; that then represents the nursery.