Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Super-Flat ASTs

jhwlr.io

Post reply on HN
Print view View original

11–20 of 27 posts

Re: Super-Flat ASTs

#11

Post by benhoyt »

munificent wrote: post #6

It looks like, overall, this design gets the parser about twice as fast as a simple one that creates tree-like ASTs. That's not nothing. But a parser is rarely the most time-intensive part of a production compiler. And the parser does get iterated on a lot in languages that are evolving and adding new syntax. Given that, I'd be inclined to take the performance hit and stick with a simpler AST representation if that y…

That's a good caution. However, traversing a flat AST (iterating a "struct of arrays" rather than a pointer-based tree) is also going to be faster. So the next steps of the compiler, say type checking and code emitting, will also be faster. But how much, or whether it's worth it even then, I'm not sure.

Re: Super-Flat ASTs

#12

Post by loeg »

FWIW I think Clang IR does something like this in a lot of places. It is relatively common to see child nodes stored inline following parent nodes. The APIs more or less abstract this away from consumers like static analysis tools, though.

E.g., https://github.com/llvm/llvm-project/blob/62e00a03fba029f82d...

and

https://github.com/llvm/llvm-project/blob/62e00a03fba029f82d...

Re: Super-Flat ASTs

#13

Post by loeg »

pedrozieg wrote: post #5

What I like about this writeup is that it surfaces a tension most “let’s build a compiler” tutorials skip: the AST is both a data structure and a UX boundary. Super-flat layouts are fantastic for cache and memory, but they’re hostile to all the things humans care about (debuggable shapes, easy instrumentation, ad-hoc traversals, “just print this node and its children” in a debugger). A lot of production compilers qui…

What about this representation is hostile to humans and ad-hoc traversals? Don't convenience "getters" basically solve usability?

Re: Super-Flat ASTs

#14

Post by torginus »

Personally I think this is a neat trick to organize memory, but don't these kinds of objects packed together in flat buffers bypass the entire lifetime and safety mechanism of Rust?

I mean if you do an off by one error on indices, essentially you are readin the pointer of another node.

Re: Super-Flat ASTs

#15

Post by munificent »

benhoyt wrote: post #11
munificent wrote: post #6

It looks like, overall, this design gets the parser about twice as fast as a simple one that creates tree-like ASTs. That's not nothing. But a parser is rarely the most time-intensive part of a production compiler. And the parser does get iterated on a lot in languages that are evolving and adding new syntax. Given that, I'd be inclined to take the performance hit and stick with a simpler AST representation if that y…

That's a good caution. However, traversing a flat AST (iterating a "struct of arrays" rather than a pointer-based tree) is also going to be faster. So the next steps of the compiler, say type checking and code emitting, will also be faster. But how much, or whether it's worth it even then, I'm not sure.

True, but that does also depend on where you store semantic information. Zipping past a nicely packed AST won't buy you much if for every node you have to look up its type or other semantic information somewhere else in memory through some slow process.

Re: Super-Flat ASTs

#16

Post by shoo »

It'd also have been interesting to see some overall profiling data of the initial program & some discussion of which optimisations to investigate based on that profiling data.

When investigating performance issues its often very helpful to run with profiling instrumentation enabled and start by looking at some top-down "cumulative sum" profiler output to get a big picture view of which functions/phases are consuming most of the running time, to see where it may be worth spending some effort.

Getting familiar with linux's perf [1] tool is also helpful, both in terms of interpreting summary statistics from perf stat (instructions per cycle, page faults, cache misses, etc) that can give clues what to focus on, but also being able to use it to annotate source line by line with time spent.

I'm not familiar with rust, but e.g. the rustc compiler dev guide has a tutorial on how to profile rustc using perf [2]

[1] Brendan Gregg's Linux perf examples is an excellent place to start https://www.brendangregg.com/perf.html [2] https://rustc-dev-guide.rust-lang.org/profiling/with_perf.ht...

Re: Super-Flat ASTs

#17

Post by uaksom »

munificent wrote: post #6

It looks like, overall, this design gets the parser about twice as fast as a simple one that creates tree-like ASTs. That's not nothing. But a parser is rarely the most time-intensive part of a production compiler. And the parser does get iterated on a lot in languages that are evolving and adding new syntax. Given that, I'd be inclined to take the performance hit and stick with a simpler AST representation if that y…

(author here) I agree that it's a lot of complexity, and I acknowledge this in the article: You can get quite far with just a bump allocator.

I didn't go into this at all, but the main benefit of this design is how well it interacts with CPU cache. This has almost no effect on the parser, because you're typically just writing the AST, not reading it. I believe that subsequent stages benefit much more from faster traversal.

(By the way, I am a huge fan of your work. Crafting interpreters was my introduction to programming languages!)

Re: Super-Flat ASTs

#18

Post by uaksom »

loeg wrote: post #13
pedrozieg wrote: post #5

What I like about this writeup is that it surfaces a tension most “let’s build a compiler” tutorials skip: the AST is both a data structure and a UX boundary. Super-flat layouts are fantastic for cache and memory, but they’re hostile to all the things humans care about (debuggable shapes, easy instrumentation, ad-hoc traversals, “just print this node and its children” in a debugger). A lot of production compilers qui…

What about this representation is hostile to humans and ad-hoc traversals? Don't convenience "getters" basically solve usability?

(author here) If you run the parser under a debugger like lldb, then attempt to inspect the AST of a program, it appears as an array of u64. Not very useful, unless you work on special support for debuggers (such as a python script to unpack it in lldb). Compare that to a tree of pointers, you can "expand" nodes without any extra effort.

Re: Super-Flat ASTs

#19

Post by loeg »

uaksom wrote: post #18
loeg wrote: post #13

Earlier quoted context omitted.

What about this representation is hostile to humans and ad-hoc traversals? Don't convenience "getters" basically solve usability?

(author here) If you run the parser under a debugger like lldb, then attempt to inspect the AST of a program, it appears as an array of u64. Not very useful, unless you work on special support for debuggers (such as a python script to unpack it in lldb). Compare that to a tree of pointers, you can "expand" nodes without any extra effort.

I guess that makes sense. But I don't ever look at AST in a debugger, and if I needed to, I'd just write some python helpers.

Re: Super-Flat ASTs

#20

Post by loeg »

torginus wrote: post #14

Personally I think this is a neat trick to organize memory, but don't these kinds of objects packed together in flat buffers bypass the entire lifetime and safety mechanism of Rust? I mean if you do an off by one error on indices, essentially you are readin the pointer of another node.

This is a common argument about Rust. Unlike pointer confusion, with index confusion, you still get bounds checking in the containing collection, and you also avoid type confusion (the wrong index element will still have the same type as the object you intended to access). So there are still some benefits.
Post reply on HN