Flattening ASTs and other compiler data structures (2023)
1–10 of 52 posts
Re: Flattening ASTs and other compiler data structures (2023)
#2This is a fantastic idea. AST works well in an array based allocation block since it has no need for freeing individual nodes. It’s an add-only allocation.
Re: Flattening ASTs and other compiler data structures (2023)
#3"Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array."
Zig compiler pipeline (AST, Zir, Air, Sema) does exactly this on all layers. Not only contiguous, but instead of array-of-structs it is struct-of-arrays, so walking the tree is even more cache friendly. For AST see: https://github.com/ziglang/zig/blob/master/lib/std/zig/Ast.z...
Re: Flattening ASTs and other compiler data structures (2023)
#4Amazing article, very good advice to keep your data structures flat.
Adding to that, it also makes editing the AST vastly more efficient.
I have discovered that principle on my own when I worked on an editor that directly operated on the AST instead of text. I found manipulating the tree-style AST so painful, constantly traversing the tree and all. Once I made it flat, my life was a hell lot easier. You can just directly index any part of AST in linear time.
Re: Flattening ASTs and other compiler data structures (2023)
#5Rust-analyzer uses a similar technique for parsing https://github.com/rust-lang/rust-analyzer/blob/master/crate... which then gets fed into https://github.com/rust-analyzer/rowan (lossless syntax tree)
Re: Flattening ASTs and other compiler data structures (2023)
#6Cool! Carbon is doing exactly this. I had asked leads if there was a paper on this approach, but they didn't have anything for me. I'll send them this post!
Re: Flattening ASTs and other compiler data structures (2023)
#7> Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array.
This happens naturally if you bump-allocate them in a garbage-collected run-time, particularly under a copying collector. Free lists also tend to co-locate because they are produced during sweep phases of GC which run through heaps in order of address.
Don't make me bring out the L word for the billionth time.
> A flat array of Exprs can make it fun and easy to implement hash consing
OK, it's not a case of L-ignorance, just willful neglect.
Re: Flattening ASTs and other compiler data structures (2023)
#8> Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array. This happens naturally if you bump-allocate them in a garbage-collected run-time, particularly under a copying collector. Free lists also tend to co-locate because they are produced during sweep phases of GC which run through heaps in order of address. Don't make me bring out the L word for the billionth tim…
FWIW I did acknowledge this in the article:
> A sufficiently smart memory allocator might achieve the same thing, especially if you allocate the whole AST up front and never add to it
> Again, a really fast malloc might be hard to compete with—but you basically can’t beat bump allocation on sheer simplicity.
Re: Flattening ASTs and other compiler data structures (2023)
#9Cool! Carbon is doing exactly this. I had asked leads if there was a paper on this approach, but they didn't have anything for me. I'll send them this post!
Zig uses a MultiArrayList which sounds similar https://mitchellh.com/zig/parser
Re: Flattening ASTs and other compiler data structures (2023)
#10As the article mentions, this makes it quite similar to a bytecode vm. I think the traditional wisdom is that an AST walker is easy to write, but for speed you'd want a bytecode interpreter. It'd be interesting to see how close the performance gets with this flattened AST.
In practice I think there are more differences. E.g. AST interpreters tend to pass environments around while bytecode interpreters often store these on a stack (though I guess there's nothing stopping you from doing this with an AST either). I wonder if there's some goldilocks zone for ease of implementation with decent performance.