Get the latest tech news
Flattening ASTs and other compiler data structures (2023)
This is an introduction to data structure flattening, a special case of arena allocation that is a good fit for programming language implementations. We build a simple interpreter twice, the normal way and the flat way, and show that some fairly mechanical code changes can give you a 2.4× speedup.
Our flattening setup assumes you never need to free individual Expr s. That’s probably true for many, although not all, language implementations: you might build up new subtrees all the time, but you don’t need to reclaim space from many old ones. A flat array of Expr s can make it fun and easy to implement hash consing or even simpler techniques to avoid duplicating identical expressions. For a microbenchmark, I randomly generated a program with about 100 million AST nodes and fed it directly into the interpreter (the parser and pretty printer are not involved).
Or read this on Hacker News