We need to flatten everything. Thanks for the great write up
Super-Flat ASTs
21–27 of 27 posts
Re: Super-Flat ASTs
#22I want to find some way to link this work to Sea of Nodes representations, but I'm a bit out of my depths to try to do so.
https://v8.dev/blog/leaving-the-sea-of-nodes
Re: Super-Flat ASTs
#23Personally 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.
> This is a common argument about Rust.
Because it is a correct one. std::vector can do this in debug mode, Zig and a bunch of other languages do as well. But that's not the point of why memory safety's important. You opt out of all aliasing and lifetime checks this way, which means an easy off-by one indexing bug (which would be a compiler error otherwise), silently propagates through the system, and you can reference wrong nodes, invalid nodes, uninitalized nodex.
It's even worse in some aspects that a dangling pointer, because you can quickly tell a dangling pointer contains garbage data, but here, the stuff looks plausible.
I am not sure this is a critique of Rust - this certainly goes against the grain of how the language has been designed - which in the case of Rust, might make things easier, since lifetimes are not checked for individual elements, but also less safe.
Re: Super-Flat ASTs
#24Earlier quoted context omitted.
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…
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 t…
> What you need is a unique handle type per container instance.
You can do this with path-dependent types in Scala, or more verbosely with modules in OCaml. The hard part is keeping the container name in scope wherever these handle types are used: many type definitions will need to reference the container handle types. I'm currently trying to structure code this way in my pet compiler written in OCaml.
Re: Super-Flat ASTs
#25Earlier quoted context omitted.
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.
> This is a common argument about Rust. Because it is a correct one. std::vector can do this in debug mode, Zig and a bunch of other languages do as well. But that's not the point of why memory safety's important. You opt out of all aliasing and lifetime checks this way, which means an easy off-by one indexing bug (which would be a compiler error otherwise), silently propagates through the system, and you can referen…
I don't think this argument is useful to rehash here. That said:
> you can reference wrong nodes, invalid nodes, uninitalized nodex.
No, you cannot access uninitialized nodes in safe Rust.
Re: Super-Flat ASTs
#26It 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.
Another small trick is to use a "reversed" bump allocator, that starts handing out the memory from the end with the larger addresses. Since AST structures are almost always created bottom-up, children before the parents, the root node at the very end on the return from parseProgram/parseModule/etc. function, you will end up with the AST that has most its pointers pointing forward. This means that during AST walks, you'll be going from lower addresses to the higher ones which I think is actually somewhat faster than the reverse order.
Re: Super-Flat ASTs
#27Why Mike Acton's data oriented programmmign has not caught up outside game dev and niche languages?