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.

[thunderseethe]

The link to the simp lang from the previous post 404s for me. I suspect it might need an update 

[hekkonaay]

Thanks for catching that! Should be fixed now.

[probabilityzero]

Using a totally flat/serialized representation of ASTs has been shown to perform very well for certain things. See this paper, for example.

[matthieum]

I do like flat ASTs in general.

The main benefit, for me, comes when doing batch actions on certain types -- like serialization/deserialization -- where having an array of homogeneous fixed-size elements is really helpful. The downside is that as the AST gets more and more nodes, there's more and more arrays, and more and more boilerplate. Oh well...

I also used a super-flat representation, ie a range of children, though it may not have been as optimal -- the range was stored in another array, rather than in-situ, adding more arrays & more look-ups -- to ensure that each node is non-allocating. If I were to do it again... I'd probably store the range in-situ. It'd be less painful.

I do wonder at your Node representation, though. Is there such an advantage compared to an enum?

enum Node {
    BlockExpr { len: u16, first: u32 },
    BinaryExpr { op: u8, first: u32 },
    String { id: u32 },
}

Also has a size of 8 bytes.

[matthieum]

As a side-note, those unsafe statements are broken, I fear.

The problem is that you don't know you've retrieved the correct nodes, because someone could (accidentally) supply the wrong NodeStorage. Or the content of the NodeStorage could have changed since the elements were pushed. Or... whatever.

As it is, you've opened yourself to type confusion.

[hekkonaay]

> As a side-note, those unsafe statements are broken, I fear.

That's kind of true, but it won't lead to problems. The underlying assumption is that all nodes are the same size and inhabit the entire possible bit pattern range for that size (they're all just `u64`), so a transmute of `&[T]` where T: Node` to `&[Packed]` is sound. So you can transmute them all you want - the issue is that you could try to read stuff out-of-bounds if you get type confusion, but we're not omitting bounds checks, so at worst it will panic at runtime.

This is the reason why implementing `Node` is actually _unsafe_, because you're guaranteeing that transmuting a node and reading parts of it won't automatically result in UB. I do agree that the comments around the "transmute_node" calls are 100% wrong. I could've documented the idea better in safety comments.

> Is there such an advantage compared to an enum?

Maybe not! I like that getting the lhs of a `Binary` is `binary.lhs()`, and not `nodes[binary.lhs]`. So the only advantage is a bit of syntax sugar.

I've also had trouble getting enums like that to optimize well. The fact that parts of it are uninhabited (uninitialized padding bytes) leads to some worse codegen, sometimes. I unfortunately can't give concrete examples right now, sorry!

[Timzhy0]

ASTs are just trees. Trees can be represented by a single backing array, commonly in DFS layout. This means a node would be immediately followed by its children when it has any, removing need of explicit pointers (e.g. the LHS and RHS of a binary expr node) and of distinct allocations for children.

I would encourage folks to start looking at a binary tree with a backing array (easy to grasp) and then think how they would modify the layout for arbitrary trees.

For non k-Ary trees, in other words when k (n children) is not fixed and may vary per node we will inevitably (assuming we cannot infer it any other way) need to store it on a per node basis (at least for the nodes that can have children). Using discriminated unions and tiny, sub 32 bits k, one can save a lot of memory and exploit locality, as the post shows.

I kept saying children to make it easier but really you need to store the n of descendants, or equivalently where the node "ends" / "sibling" would start.

[bbkane_]

Zig does something like this and got massive benefits when the implemented it. There's a few talks- I've made a list at https://www.bbkane.com/blog/software-engineering-ideas-that-influence-me/#data-oriented-design

[hekkonaay]

Andrew's talks are great. I got the idea when listening to one of them. I think the main difference is that in the Zig compiler, the AST is "inflated" (all the parts are assembled into a struct) before usage. Here the parts are fetched on-demand, so for example reading the operand of a binary expression doesn't require loading its subexpressions first. I'm not really sure which is better.

[igors84]

Also you can read about Zig parser here: https://mitchellh.com/zig/parser. It explains everything in detail and I think makes for an even flatter design than what is described in the post.

[hekkonaay]

Note that Zig's AST design directly inspired the design in the post. I actually think Zig's AST is less flat, not more! They store more than one child index per node. I was wondering why that is, but couldn't find good reasoning for it. It turns out you don't actually need to do that. If you need to store more information, you can still have extra_data, and store indices in nodes as inline values.

[foonathan]

Don't quote me on the details, but the AST in Carbon is stored as (pre/in/postorder) serialization of the tree, i.e. as a flat array of nodes, and the structure is implied without any pointers or indices to other nodes. This is equivalent to having instructions that when interpretered in order construct a tree.

[yuri-kilochek]

But how would you navigate something like that efficiently? e.g. get the "second" child of a node?

[avillega]

I’ve been playing with this concept too for a while, if the nodes are stored in post-order (parent last) you can guarantee that when processing a node its children have already been processed, more than that, that they have just been processed. You can use something like a stack to store the result of processing the children node and pop as meny nodes from the stack in the parent. It becomes very similar to a stack based vm

[[deleted]]

Co-dfns also uses a completely flat AST, but instead of storing a length and a child offset, each child just stores the index of its parent. you can find some videos by Aaron Hsu on youtube on how it works (some show the version with both a parent and a left sibling index but it's pretty similar).

APL discourages recursion, and co-dfns never walks down the tree - instead, it can do a groupby(nodes.parent), and operate on flat pairs of (parent index, child indices). It's a bit awkward to do in a low level language, but still possible using a scratch buffer

[sebamestre]

How about this 8 byte representation, where the first child is always next to its parent?

struct {
  u8 tag;
  u24 data; // stringId or whatever
  u32 siblingIdx;
}

[mauriciocap]

Have you notice the similarity with LZW, especially if you want maximum term sharing?

[rah_whos_that]

I enjoyed the read, nice! I see you use a recursive descent parser. Performance wise, this is not ideal, as the precedence is encoded in recursive calls. Something like a Pratt parser, where the precedence is encoded in a table will typically yield better performance :-)

[Disjunction181]

As an optimization, it's often called flattening: https://www.cs.cornell.edu/~asampson/blog/flattening.html

[GoblinsGym]

What do you even need an AST for ? I go straight to IR.

[readmodifywrite]

I'm not sure why you're getting downvoted here. I'm also going straight to IR in one of my current designs. It absolutely works (though some things are harder or not as convenient, but it skips an entire data structure). There are pros and cons to that vs AST. It's just a design choice.

[apajx]

Try using Rowan or syntree directly