Dense Arena Interning: cómo convertir cadenas en enteros O(1) para acelerar compiladores

Dense Arena Interning: The Engine of Compiler Performance

Los compiladores dedican gran parte del tiempo a comparar nombres y estructuras repetidamente en cada fase. Un enfoque eficiente es el Dense Arena Interning, que convierte cadenas y estructuras en enteros densos en el momento de su creación, pagando el costo de hash una sola vez. Así, fases posteriores como el análisis de tipos y la optimización se benefician de comparaciones O(1) mediante indexación en arrays y comparación de punteros. El autor detalla su implementación en C para un compilador de un lenguaje procedural con backend LLVM, explicando cómo el interner, junto con un asignador de arena, garantiza estabilidad de punteros y deduplicación de memoria, y cómo los IDs densos permiten tablas de símbolos como arrays planos con acceso directo.