Re:Flattening ASTs (and Other Compiler Data Structures)
by kazinator on Sunday July 02, 2023 @12:25PM
(#36562946)
> 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.
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.