Aplanado de ASTs y otras estructuras de datos de compiladores

• Las arenas o regiones son una técnica simple y efectiva para compiladores y herramientas similares a compiladores.
• Usar arenas para aplanar árboles de sintaxis abstracta (AST) puede mejorar el rendimiento y ofrecer mayor comodidad.
• Aplanar significa empaquetar los nodos del AST en un solo arreglo y usar índices del arreglo en lugar de punteros.
• Los AST aplanados ofrecen ventajas como mejor localidad, referencias más pequeñas y asignación y liberación más baratas.
• Los AST aplanados pueden simplificar la gestión de memoria y permitir una deduplicación conveniente.
• Los resultados de rendimiento muestran que una versión del intérprete aplanada puede ser 2.4 veces más rápida que la versión normal.
• Aprovechar la representación plana del AST permite eliminar la recursión y usar recorridos lineales para mejorar aún más el rendimiento.
• Este artículo analiza las mejoras de rendimiento logradas mediante el aplanado de estructuras de datos en un intérprete de lenguaje de programación.
• Además, el intérprete aplanado muestra una mejora de rendimiento del 8.2% frente al intérprete recursivo, con 1.2 segundos frente a 1.3 segundos.
• Esta técnica básicamente reinventa la idea de un intérprete de bytecode, donde la estructura Expr se usa como instrucción de bytecode.
• Se mencionan otros artículos y proyectos sobre aplanado de estructuras de datos relacionados con LuaJIT, el verificador de tipos Sorbet y el shell Oil.
• En dominios como los videojuegos, el procesamiento de datos serializados, el diseño orientado a datos y los sistemas entidad-componente también aparecen conceptos similares relacionados con el aplanado y la optimización de localidad.
• El artículo recomienda revisar una publicación de Inanna Malick que aplica la misma técnica a un lenguaje de "calculadora" de juguete implementado en Rust.
• Se comentan limitaciones al usar esta técnica en Rust, como que no se pueden incluir en línea otras Expr dentro de la estructura Expr.
• La comparación de rendimiento se realizó en una MacBook Pro con procesador M1 Max y 32 GB de memoria, ejecutando macOS 13.3.1 y Rust 1.69.0.

[GN⁺]

Comentario de Hacker News

• Blender usa la misma representación en disco y en memoria para cargar y guardar archivos de forma rápida y sin pérdidas.
• En pulldown-cmark se usa un AST aplanado para analizar markup en línea de manera eficiente.
• La representación de AST aplanado permite transformaciones de árbol en O(1) sin importar la cantidad de nodos ni la profundidad de la pila.
• El rendimiento de pulldown-cmark es sobresaliente en comparación con otros parsers de CommonMark.
• La Warren Abstract Machine (WAM) usa una representación aplanada en el heap para Prolog.
• El aplanamiento de AST es un concepto que ya se usaba en lenguajes como Lisp.
• Guardar nodos en arreglos redimensionables puede causar problemas de asignación de memoria, pero eso puede mitigarse agrupándolos en bloques del tamaño de una página.
• Hay que tener cuidado con cómo se representan los nodos AST en el código y evitar padding innecesario.
• Usar índices en lugar de punteros puede producir código más pequeño y rápido.
• La memoria aplanada puede implementarse con un asignador de memoria personalizado, útil en ciertos escenarios.
• Se usaron estructuras AST compactas para implementar un parser e intérprete de JavaScript en entornos con restricciones de memoria.