Flattening ASTs: Performance Wins in Compiler Data Structures

This article explores performance optimization of compiler data structures by flattening Abstract Syntax Trees (ASTs). The author builds a simple arithmetic expression interpreter, implementing it both with traditional pointers and a flattened array approach, comparing their performance. Results show a 2.4x speedup with the flattened version, attributed to improved memory locality, smaller reference sizes, and cheaper allocation/deallocation. Flattening also simplifies memory management and facilitates deduplication. The article further presents an iterative interpreter exploiting the flattened representation for additional performance gains.