Flattening ASTs and other compiler data structures (2023)

157 点作者 aw16211074 个月前

16 条评论

jgrowl4 个月前

I thought a reddit comment on this article had an interesting point:<a href="https://www.reddit.com/r/rust/comments/1d3b356/my_new_favorite_way_to_represent_asts_or_any/l6al1q8/" rel="nofollow">https://www.reddit.com/r/rust/comments/1d3b356/my_new_favori...</a>[–]Timzhy0 3 points 7 months agoBtw I think one can go a step further than the author, there is no need to keep two explicit ExprRef baked in a binary node (lhs, rhs). You can exploit locality, basically the AST, seen it the LISP way, is just an arbitrarily nestable list, where elements are atoms or other lists. Hence all you need to know is where each list ends (and if it's an atom you can assume it spans one node) and actually one bit to know if it is the last entry in the list is quite ergonomic as well (because then you can distinguish whether moving next slot in the AST means there is a sibling). Basically it's easier to keep it sync while constructing and takes up less memory per node. I pay 40 bits per node, stored interleaved for best cache locality (some unaligned accesses but I think it's still worthwhile), 8 bits for the tag, 32 for the data, if data is bigger, 32 is an index into some auxiliary segment (basically a ptr).

评论 #42667928 未加载

dmagyari4 个月前

"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: <a href="https://github.com/ziglang/zig/blob/master/lib/std/zig/Ast.zig#L13">https://github.com/ziglang/zig/blob/master/lib/std/zig/Ast.z...</a>

评论 #42664068 未加载

评论 #42662156 未加载

torginus4 个月前

I guess Rust's contribution to high performance programming is that its borrow checker is so loathsome that it pushes people into using ideas like ECS or arenas just to not have to bother with it.

kazinator4 个月前

> 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 consingOK, it's not a case of L-ignorance, just willful neglect.

评论 #42661057 未加载

评论 #42668052 未加载

Agraillo4 个月前

About 10 years ago working with AST trees I (re)invented a flat structure representing trees in a flat array. It reminds me of what is described here but not exactly. In my case I needed only two indices per node: total sub-region length of all the children and sub-children and parent index (so no need to have indices of all children). Total sub-length basically can be interpreted as the index of the next sibling. With such a structure it's easy/cheap to execute FindFirstChild/FindNextSibling.Later the theory behind such structures was revealed as "Nested set model" [1]. The article seems to not mention the internal representation, but I think that the implementation should use something like my solution, so fixed number of references per node[1] <a href="https://en.wikipedia.org/wiki/Nested_set_model" rel="nofollow">https://en.wikipedia.org/wiki/Nested_set_model</a>

cardanome4 个月前

Amazing 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.

userbinator4 个月前

Rediscovering techniques that were somewhat well-known in the 70s and 80s.See also: <a href="https://en.wikipedia.org/wiki/Binary_heap" rel="nofollow">https://en.wikipedia.org/wiki/Binary_heap</a>

评论 #42664354 未加载

评论 #42665130 未加载

emptysea4 个月前

Rust-analyzer uses a similar technique for parsing <a href="https://github.com/rust-lang/rust-analyzer/blob/master/crates/parser/src/event.rs">https://github.com/rust-lang/rust-analyzer/blob/master/crate...</a> which then gets fed into <a href="https://github.com/rust-analyzer/rowan">https://github.com/rust-analyzer/rowan</a> (lossless syntax tree)

评论 #42662028 未加载

Tarean4 个月前

Twee (an equational theorem prover in Haskell used by quickspec) has an interesting take on this. Terms are slices of arrays, but you get a normal interface including pattern matching via synonyms. It can also be nice to use phantom types of your references (array offsets), so if you project them into flat view types you can do so type safelyRequires the language to have something equivalent to pattern synonyms to be as invisible as twee, though.In twee a TermList is a slice of a bytearray (two ints for offset/length plus a pointer).And a term is an int for the function symbol and an unpacked TermList for the arguments.The pattern match synonyms load a flat representation from the array into a view type, and the allocation of the view type cancels out with the pattern matching so everything remains allocation free.<a href="https://hackage.haskell.org/package/twee-lib-2.4.2/docs/Twee-Term.html" rel="nofollow">https://hackage.haskell.org/package/twee-lib-2.4.2/docs/Twee...</a>

评论 #42668812 未加载

ww5204 个月前

This 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.

评论 #42664523 未加载

ndesaulniers4 个月前

Cool! 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!

评论 #42666939 未加载

评论 #42661320 未加载

pfdietz4 个月前

One advantage to this is the ease with which it handles ephemeral annotations.Suppose you want to attach additional information to some of the nodes of the AST. Different algorithms on the AST will attach different information; you don't necessarily need them all at the same time or know ahead of time what you'll need.With nodes, you have to have some sort of node/value hash table, or hang a key/value map off each node. But with this flattened representation, each datum gets its own flat array as well, which can be independently allocated and deallocated.One other thing I noticed about this flat representation is that it throws static typing into a cocked hat! All you have to refer to other nodes is indices. All different kinds of nodes are stored in the same array.

hencq4 个月前

As 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.

评论 #42662165 未加载

jonstewart4 个月前

You can also be smart about memory with lexing for great winnage. Have a struct for your tokens that has an enum for your token type and either pointer or indices or a string_view (or a &str but lol lotsa luck with the borrow checker). You can then have a vector of your token structs for fast allocation and iteration and you have a slice for the token back into the original input, no substring copying.

评论 #42666352 未加载

dang4 个月前

Related:Flattening ASTs and other compiler data structures (2023) - <a href="https://news.ycombinator.com/item?id=42181603">https://news.ycombinator.com/item?id=42181603</a> - Nov 2024 (2 comments)Flattening ASTs and other compiler data structures - <a href="https://news.ycombinator.com/item?id=36559346">https://news.ycombinator.com/item?id=36559346</a> - July 2023 (81 comments)

efitz4 个月前

Did the author just reinvent Forth?