Flattening ASTs (and Other Compiler Data Structures)
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.
Hasnain says:
“My favorite observation about this technique, due to a Reddit comment by Bob Nystrom, is that it essentially reinvents the idea of a bytecode interpreter. The Expr structs are bytecode instructions, and they contain variable references encoded as u32s. You could make this interpreter even better by swapping out our simple state table for some kind of stack, and then it would really be no different from a bytecode interpreter you might design from first principles. I just think it’s pretty nifty that “merely” changing our AST data structure led us directly from the land of tree walking to the land of bytecode.”
Posted on 2024-06-02T06:41:27+0000