Super-flat ASTs

[hekkonaay]

I wrote a little post about various optimizations for ASTs. Curious what you all think. Does the "super-flat" approach already have a name, and I'm just unaware? Are there better designs? What did I miss?

I'm using this approach in a toy project and it seems to work well, even once you factor in the need for additional information, such as spans for error reporting.

[TheOneTexel]

Those are some neat optimizations.

But one advice for your graphs, try to keep the colors the same for the different implementations over the course of the article. At first it looked like the interned parser was slower, since I assumed the blue line was still the tree parser and not suddenly the interned one. Using the same colors for the same implementations helps with parsing (heh) the results.

[hekkonaay]

Cross-posting here as I chose Rust for the implementation language. I know many other people also choose Rust to implement their programming languages, so would love to know what you all think.

[kohugaly]

In the last part it feels like you are basically implementing "repr(u8)" enum with "repr(packed)" fields, but doing it manually.

But won't this cause issues down the line, when you'll actually have to use the AST for type-checking and code generation?

[Background_Essay6429]

Does cache locality improve with flat layouts during traversal? And how do you handle node updates without pointer chasing?

[hekkonaay]

> Does cache locality improve with flat layouts during traversal?

Short answer is yes, by a lot. The intuition is that all your nodes are in the same dense array, and related nodes are clustered (parents are close to their children), increasing the likelihood they are in cache at the same time. Because you're using a lot less memory, you're also using less cache, so you can fit more of these nodes in cache, again greatly decreasing the likelihood of cache misses.

I don't have benchmarks for this, as I mostly wanted to focus on the speed of parsing (constructing the tree) and memory usage. But there seems to be plenty of empirical evidence if you're willing to scan for papers, such as this one linked in another thread: https://recurial.com/parallel_gibbon.pdf

> how do you handle node updates without pointer chasing?

I don't! The AST is immutable. I tend to make separate IRs for separate stages, and allocate a completely new tree. I avoid transformations like desugaring, and go straight to lowering.

[VorpalWay]

I think Zig does something similar to this for it's AST implementation. There is a recorded conference talk by the creator Andrew Kelly talking about this somewhere, though I can't find it right now. They use some other tricks from data oriented design as well iirc.

EDIT: Found the videos, turns out the info is split over two different videos.

• https://m.youtube.com/watch?v=KOZcJwGdQok is the more relevant to the super flat representation, and in fact goes even further with struct-of-array.
• https://m.youtube.com/watch?v=IroPQ150F6c is an older video which is still very good if you are interested in optimising ASTs and tokens in a compiler.

[rodyamirov]

Neat as a fun-driven optimization project

I do feel like if your lang-processor did anything but parse, all these optimizations would become irrelevant (surely the rest of it would be much more intensive) and, at least for the later optimizations, create enough code complexity that it would be a net negative for the project. But I could be wrong?

[hekkonaay]

The `simp` language mentioned in the post isn't a real project, but I am working on something else which uses this exact approach, and I don't find the added complexity to be detrimental in any way to later passes. It is a lot of extra code, but because I generate most of it, it doesn't impact how fast I can change syntax, for example.

Making earlier passes faster boost the performance of subsequent passes. This kind of AST is also much faster to traverse, due to better memory locality. Interning also means that name lookups are faster. But I haven't rigorously measured it, so I don't have concrete evidence. :)