[HN Gopher] Super-Flat ASTs
___________________________________________________________________
Super-Flat ASTs
Author : mmphosis
Score : 72 points
Date : 2025-12-04 18:01 UTC (6 days ago)
(HTM) web link (jhwlr.io)
(TXT) w3m dump (jhwlr.io)
| mitchellh wrote:
| For a good example of this sort of pattern in the real world,
| take a look at the Zig compiler source code. I'm sure others
| might do it but Zig definitely does. I have a now very outdated
| series on some of the Zig internals:
| https://mitchellh.com/zig/parser And Andrew's old DoD talk is
| very good and relevant to this: https://vimeo.com/649009599
|
| More generally, I believe its fair to call this a form of handle-
| based designs: https://en.wikipedia.org/wiki/Handle_(computing)
| Which are EXTREMELY useful for a variety of reasons and imo
| woefully underused above the lowest system level.
| sestep wrote:
| My hypothesis is that handles are underused because programming
| languages make it very easy to dereference a pointer (you just
| need the pointer) whereas "dereferencing" a handle requires
| also having the lookup table in hand at the same time, and that
| little bit of extra friction is too much for most people. It's
| not that pointers _don 't_ require extra machinery to be
| dereferenced, it's just that that machinery (virtual memory) is
| managed by the operating system, and so it's invisible in the
| language.
|
| My current research is about how to make handles just as
| convenient to use as pointers are, via a form of context: like
| a souped-up version of context in Odin or Jai if one is
| familiar with those, or like a souped-up version of coeffects
| if one has a more academic background.
| densh wrote:
| Great summary and I think your argument is sound.
| faresahmed wrote:
| I think that it's a generic programming problem: pointers are
| easier because the type of the pointee is easy to get (a
| deref) and also its location (memory) but with index-based
| handles into containers you can no longer say that given a
| handle `H` (type H = u32) I can use it to get a type `T` and
| not only that, you've also introduced the notion of "where",
| that even if for each type `T` there exists a unique handle
| type `H` you don't know into which container instance does
| that handle belong. What you need is a unique handle type per
| container instance. So "Handle of Pool<T>" != "Handle of
| Pool<T>" unless the Pool is bound to the same variable.
|
| As far as I know no language allows expressing that kind of
| thing.
| sestep wrote:
| I think actually Scala does exactly this style of inferring
| the container instance from its type: https://docs.scala-
| lang.org/scala3/book/ca-context-parameter...
|
| But from what I understand (being a nonexpert on Scala),
| this scheme actually causes a lot of problems. I think I've
| even heard that it adds more undecidability to the type
| system? So I'm exploring ways of managing context that
| don't depend on inferring backward from the type.
| pedrozieg wrote:
| 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 quietly solve that by
| having two tiers: a nice, inefficient tree for diagnostics and
| early passes, and increasingly flattened / interned / arena-
| allocated forms as you move toward optimization and codegen.
|
| The interesting question for me is where the crossover is now
| that IDEs and incremental compilation dominate the workload. If
| your front-end is effectively a long-running service, it might be
| worth keeping a friendlier AST around and only using a super-flat
| representation for hot paths like analysis passes or bulk
| refactors. Otherwise you risk saving a few hundred MB while
| spending engineer-months making every new pass fight the layout.
| loeg wrote:
| What about this representation is hostile to humans and ad-hoc
| traversals? Don't convenience "getters" basically solve
| usability?
| munificent wrote:
| 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 yields a more hackable,
| maintainable compiler front end.
| exyi wrote:
| Usually yes, but it's still a neat trick to be aware of. For
| interpreted scripting languages, parsing can actually be a
| significant slowdown. Even more so when we start going into
| text-based network protocols, which also need a parser (is CSS
| a programming language or a network protocol? :) )
| benhoyt wrote:
| 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.
| mediumdeviation wrote:
| For anyone confused by why the text says the performance is
| improving between each graph but the lines don't seem to show
| that - the color for each key and the scale changes between
| graphs.
| loeg wrote:
| 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...
| torginus wrote:
| 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.
___________________________________________________________________
(page generated 2025-12-10 23:01 UTC)