Dense Arena Interning: Der Motor der Compiler-Performance
Dense Arena Interning: The Engine of Compiler Performance
Compiler verbringen enorme Zeit damit, Namen und Strukturen zu vergleichen. Aiko Schurmann zeigt, wie ein Dense Arena Interner Strings und Strukturen in dichte Ganzzahlen umwandelt, sobald sie erzeugt werden. Dadurch wird die teure Hash-Berechnung nur einmal in der Lexer-Phase bezahlt, während alle nachfolgenden Phasen von O(1)-Array-Zugriffen und Pointer-Vergleichen profitieren. Der Artikel erklärt die Implementierung im Detail: von der Arena-Allokation über die Interner-Logik bis zur Integration in den Lexer. Besonders hervorzuheben ist die Nutzung dichter IDs für flache Symboltabellen, die die Auflösung von Variablen auf eine einzige Speicher-Offset-Berechnung reduzieren. Ein Muss für alle, die Compiler-Performance verstehen und optimieren wollen.
Wir zahlen die Hash-Kosten im Voraus während des Lexens oder der Typkonstruktion. Im Gegenzug kann sich jede nachfolgende Phase des Compilers vollständig auf O(1)-Array-Indizierung und Single-Instruction-Pointer-Vergleiche verlassen.