✳flâneur — a map of the web's best reading

Adrian Sampson: Flattening ASTs (and Other Compiler Data Structures)

cs.cornell.edu · 3,418 words · saved by 1 readers

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

Explore this link on the map →

saved by

related reading