Adrian Sampson: 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.

Normal and flattened ASTs for the expression a * b + c . Arenas, a.k.a. regions, are everywhere in modern language implementations. One form of arenas is both super simple and surprisingly effective for compilers and compiler-like things. Maybe because of its simplicity, I haven't seen the basic technique in many compiler courses-or anywhere else in a CS curriculum for that matter. This post is an introduction to the idea and its many virtues. Arenas or regions mean many different things to different people, so I'm going to call the specific flavor I'm interested in here data structure flatten

saved by

• cynyu s

related reading

• Formally speaking, "Transpiler" is a useless word | Rachit Nigampeople.csail.mit.edu
• A Gentle Introduction to LLVM IR · mcyoungmcyoung.xyz
• A half-hour to learn Rustfasterthanli.me
• abseil / Performance Hintsabseil.io
• (Re)writing an interpreter in Rust – Danny van Kootendannyvankooten.com
• A Gentle Introduction to LLVM IR · mcyoungmcyoung.xyz
• Writing a C compiler in 500 lines of Pythonvgel.me
• Fast and Simple Rust Internermatklad.github.io
• A Tiny Compiler for Data-Parallel Kernelshealeycodes.com
• The Lost Art of Structure Packingcatb.org
• What can we learn from how compilers are designed?tedinski.com
• LLVM is Smarter Than Meblog.sulami.xyz