- Si el AST se representa no como un grafo de objetos enlazados por punteros sino con un solo arreglo e índices, se simplifican la disposición en memoria y la forma de gestionar estructuras de datos típicas de compiladores
- El ejemplo en Rust implementa un AST aplanado con cambios pequeños: sustituir
Box<Expr> por ExprRef y añadir add/get a ExprPool
- En un microbenchmark que crea e interpreta de inmediato cerca de 100 millones de nodos AST, la implementación normal tarda 3.1 segundos y la aplanada 1.3 segundos, lo que la hace 2.4× más rápida
- La diferencia de rendimiento proviene de la localidad por memoria contigua, referencias más pequeñas usando índices de 32 bits en lugar de punteros de 64 bits, asignación barata y liberación por pool
- Si se aprovecha la propiedad de que en el arreglo los hijos aparecen antes que el padre, un recorrido recursivo del árbol puede convertirse en una ejecución lineal, acercándose a la forma de un intérprete de bytecode
La idea básica del aplanamiento
- Los arena o region se usan ampliamente en implementaciones modernas de lenguajes, y el enfoque tratado aquí es el aplanamiento de estructuras de datos, donde un arena que contiene un solo tipo se usa como si fuera un arreglo simple
- Es una técnica que reemplaza punteros por índices de arreglo en estructuras de datos con muchos punteros; el ejemplo central es el AST, pero también puede aplicarse a otras estructuras de datos de compiladores
- El código de ejemplo está en el repositorio flatcalc, y la diferencia entre la implementación normal y la aplanada puede verse en la comparación de ramas
- Aunque el cambio de código es pequeño, en el microbenchmark aparece una mejora de 2.4×, y además hay ventajas en usabilidad del código aparte del rendimiento
Representación típica de un AST
- El lenguaje de ejemplo es un lenguaje muy simple de expresiones aritméticas que solo soporta literales enteros y cuatro operadores aritméticos binarios
- Algunos programas posibles son
42, 0 + 14 * 3 y (100 - 16) / 2
- La representación en Rust se compone de los enums
BinOp y Expr
Expr::Binary(BinOp, Box<Expr>, Box<Expr>)Expr::Literal(i64)
- En Rust,
Box<Expr> corresponde a un puntero que apunta a Expr, con un papel parecido al de Expr* en C
- El parser, el formateador de salida y el intérprete tienen una estructura típica, y el intérprete está escrito como un método recursivo sobre
Expr
- La semántica aritmética está construida para que todas las expresiones se evalúen finalmente a
i64
- La suma, resta y multiplicación usan operaciones wrapping
- La división entre 0 se maneja con
checked_div para devolver 0
- Se usa un generador aleatorio de programas con semilla fija de PRNG para medir el rendimiento de manipulación del AST sin costo de parseo ni de impresión
Cambiar el AST por un arreglo e índices
- El aplanamiento consiste en dos cambios
- Los objetos
Expr no se asignan individualmente en el heap, sino que se almacenan en un solo arreglo contiguo
- Los nodos hijo se referencian con índices dentro del arreglo en lugar de punteros
- En el ejemplo de Rust,
ExprPool se define como un newtype de Vec<Expr>
struct ExprPool(Vec<Expr>);
- El papel del puntero anterior lo asume
ExprRef, basado en un entero de 32 bits
struct ExprRef(u32);
- El cambio principal de tipos es reemplazar los campos hijo de
Binary, pasando de Box<Expr> a ExprRef
enum Expr {
Binary(BinOp, ExprRef, ExprRef),
Literal(i64),
}
- A
ExprPool se le agregan utilidades add para insertar un nuevo Expr y get para buscar un Expr a partir de ExprRef
- El parser ya no devuelve
Expr directamente, sino que añade nodos a ExprPool y devuelve ExprRef
- El intérprete también pasa de ser un método de
Expr a un método de ExprPool, y antes del pattern matching desreferencia con self.get(expr)
- En conjunto, los cambios son pequeños: básicamente sustituir
Box<Expr> por ExprRef y colocar add y get donde haga falta
Ventajas de rendimiento
- Una ventaja representativa del AST aplanado es la localidad de memoria
- Un
Expr normal basado en punteros corre riesgo de fragmentación de memoria
- Un
Expr aplanado queda concentrado en una región contigua, lo que puede ayudar a que el caché de datos y el prefetcher funcionen mejor
- Un asignador de memoria lo bastante inteligente podría lograr un efecto similar, pero usar un arreglo compacto reduce la incertidumbre
- El tamaño de las referencias también se reduce
- Un puntero normal es de 64 bits en arquitecturas modernas
- Si no se necesitan más de 4,294,967,295 nodos AST, una referencia de 32 bits es suficiente
- Se puede ahorrar 50% de espacio por referencia, y en AST con muchos punteros esto puede reducir el uso total de memoria
- Si la estructura es más pequeña, incluso podrían usarse referencias de 16 bits o 8 bits
- El costo de asignación baja
- Ya no hace falta llamar a
malloc por cada nodo
- Si se reservó suficiente memoria por adelantado, se puede crear espacio para un nuevo
Expr con bump allocation aumentando un tail pointer
- La liberación puede hacerse por pool
- Se asume que no hace falta liberar cada
Expr individualmente
- En muchas implementaciones de lenguajes, el AST suele crearse junto y desaparecer junto
- Mientras que un AST normal debe liberar cada nodo siguiendo punteros, un AST aplanado puede liberar todo
ExprPool de una sola vez
- En introducciones a arena allocation suele destacarse la liberación barata como motivo principal, pero en el contexto de compiladores el AST puede vivir hasta el final de la compilación, así que liberar quizá sea el motivo menos importante
Ventajas en usabilidad del código
- El aplanamiento simplifica la gestión de lifetimes
- Un AST con n nodos puede pensarse como un solo lifetime del AST en lugar de n lifetimes
- En Rust, esta simplificación afecta directamente cómo se expresan los lifetime en el código
- En vez de gestionar los lifetime de
&Expr, puede pasarse ExprRef, que es un u32, y depender del lifetime de ExprPool
- La misma simplicidad también puede aplicarse en lenguajes con gestión manual de memoria como C++
- El arreglo aplanado facilita implementar deduplicación
- Puede evitarse crear expresiones idénticas mediante
hash consing o con métodos más simples
- Por ejemplo, podrían reservarse las primeras 128 posiciones de
ExprPool para expresiones Literal de uso frecuente entre 0 y 127
- Cuando se necesita el literal entero
42, en vez de crear un nuevo Expr se puede devolver ExprRef(42)
- En una representación basada en punteros también se puede hacer algo parecido, pero probablemente requerirá estructuras auxiliares
Resultados del microbenchmark
- El benchmark genera un programa aleatorio con cerca de 100 millones de nodos AST y lo pasa de inmediato al intérprete
- No incluye parser ni formateador de salida
- Genera un solo programa y lo ejecuta enseguida, así que no es un benchmark realista
- Las condiciones del experimento tienen varias limitaciones
- Se reserva de antemano suficiente espacio en
Vec<Expr> para contener todo el programa
- En un entorno real habría que estimar mejor el tamaño del arena
- Como casi no hay trabajo aparte de generar y ejecutar, las ventajas de asignación y liberación baratas podrían quedar exageradas
- El programa es tan grande que una fracción pequeña cabe en la caché de CPU, así que el efecto de localidad podría quedar subestimado
- Con Hyperfine se comparó el promedio de 10 ejecuciones en una laptop
- El entorno fue M1 Max de 10 núcleos a 3.2GHz, 32GB de memoria, macOS 13.3.1 y Rust 1.69.0
- La implementación normal tardó 3.1 segundos y la aplanada 1.3 segundos, mostrando una mejora de 2.4×
- Para aislar el costo de liberación, se hizo una versión que omite deallocation en ambas implementaciones
- En la implementación aplanada, el tiempo del modo no-free y el de la versión estándar fueron casi iguales, así que el tiempo de liberación no era grande
- En la implementación normal, bajó de 3.1 segundos a 1.9 segundos, lo que indica que alrededor de 38% del tiempo se iba en liberar memoria
- Incluso comparando entre versiones no-free, la implementación aplanada seguía siendo 1.5× más rápida que la normal
Un intérprete que aprovecha directamente la representación aplanada
- Al principio, el aplanamiento se usó como un cambio interno de implementación para sustituir asignación normal y punteros, pero también puede aprovechar directamente las propiedades de la representación en arreglo
- Si
Expr es inmutable, primero deben crearse los nodos hijo y luego el nodo padre
- Al construir
a * b, a y b quedan antes en ExprPool que el * que los referencia
- Las flechas de referencia en el arreglo siempre apuntan de atrás hacia adelante, mientras que el flujo de datos avanza hacia adelante
- Aprovechando este invariante, puede construirse un intérprete que escanee
ExprPool de principio a fin, en vez de bajar recursivamente desde la raíz
- El recorrido siempre visita los hijos antes que el padre
- El resultado de cada expresión se guarda en un vector
state
- Las expresiones binarias obtienen sus valores consultando
state con los índices ExprRef de sus hijos
- Al final se devuelve el resultado correspondiente al
root solicitado
- Este intérprete “extra-flat” no tiene costo de manejo de stack por llamadas recursivas y puede recorrer
ExprPool linealmente
- A cambio, necesita acceso aleatorio a un vector
state grande, lo que puede perjudicar la localidad
- Como resultado, el intérprete extra-flat tardó 1.2 segundos y el intérprete aplanado recursivo 1.3 segundos, una mejora de 8.2%
Conexión con intérpretes de bytecode
- Un comentario de Bob Nystrom en Reddit observa que este enfoque, en la práctica, vuelve a descubrir la idea de un intérprete de bytecode
- La estructura
Expr funciona como una instrucción de bytecode, y las referencias a variables entran codificadas como referencias u32
- Si la tabla
state simple se cambia por una estructura tipo stack, el resultado ya casi no se distingue de un intérprete de bytecode diseñado desde el inicio
- Solo cambiando la estructura de datos del AST, se pasa de manera natural del recorrido de árboles al estilo de bytecode
Material relacionado
- Material relacionado con aplanamiento en contexto de compiladores
- Ideas parecidas también aparecen en áreas orientadas a rendimiento fuera de la implementación de lenguajes
- El artículo sobre un lenguaje calculadora de juguete en Rust de Inanna Malick también aplica esta técnica junto con ideas de recursion schemes del mundo de Haskell
1 comentarios
Comentarios en Hacker News
Blender (software de modelado 3D) es un caso interesante de este enfoque. Para hacer que la carga/guardado de archivos sea rápida y sin pérdidas, usa la misma representación en disco y en memoria
Es decir, todo está dentro de una arena, y guardar/cargar se parece a hacer
memcpyde toda la arena. Considerando la complejidad potencial del proyecto Blender y los problemas de serialización/deserialización, parece un diseño excelenteLa desventaja es que, como también debe poder abrir archivos de versiones antiguas, el diseño de las estructuras de datos tiende a quedar congelado
Estas conversiones solo se ejecutan al cargar datos de versiones antiguas de la app, y después se pueden guardar de inmediato en disco con la versión actualizada, así que no hay que volver a pagar ese costo
https://www.inkandswitch.com/cambria/ creado en el contexto de CRDT es un ejemplo de implementación de esta idea, y aunque no aplique directamente, puede servir como buena inspiración
Te gustara o no el framework de E/S, serializaba las estructuras tal cual, así que siempre había que diseñar las estructuras de datos pensando en el futuro, sabiendo que quedarías atado a esa forma para siempre. Fueron tiempos oscuros
Por eso escribir convertidores se volvió un gran problema, y recuerdo que había que descifrar estructuras de datos internas de Word que no estaban documentadas
Si alguien podía modificar los archivos en disco, eso ya significaba que había tomado control del dispositivo. Gracias a eso, la carga era absurdamente rápida: leíamos todo a memoria y luego solo parchábamos las ubicaciones de los punteros a la dirección real donde se había cargado
Me gustan los árboles de sintaxis abstracta aplanados. En particular, me encanta el enfoque usado para procesar marcado en línea en pulldown-cmark. Hay una explicación breve en https://fullyfaithful.eu/pulldown-cmark/
La entrada cruda se divide en una secuencia de nodos, y algo como
*se convierte en un nodoMaybeEmphasis, porque podría terminar siendo énfasis o, si queda sin pareja, quedarse como textoEn la siguiente etapa, se usa una pila para recorrer los nodos en orden y buscar posibles parejas. Cuando se encuentra una pareja, el nodo
MaybeEmphasisse reemplaza por el nodo de énfasis correspondiente, y toda la secuencia de nodos entre el nodo de apertura y el de cierre se recorta para convertirla en el subárbol del nuevo nodoEsta transformación del árbol es bastante inusual, así que una implementación ingenua puede fácilmente volverse O(n), pero con una representación de AST aplanado se puede hacer en O(1), sin importar la cantidad de nodos ni la profundidad de la pila
La representación detallada del árbol está en https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6..., y básicamente mantiene índices
childynextjunto con el cuerpo del nodo. El código de cirugía del árbol durante el emparejamiento de énfasis está en https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6...El rendimiento es excelente. Puede que pulldown-cmark no sea el parser de CommonMark más rápido en términos absolutos, pero es lo bastante competitivo y, por ejemplo, mucho más rápido que un enfoque que asigna memoria por cada nodo)
Me hizo recordar una charla de la GDC que elogiaba a Rust. Decía que Rust, por culpa del borrow checker, o te vuelve loco o te empuja a estructurar el código con un sistema de componentes de entidades
En casos reales con problemas complejos de lifetimes, es curioso que el valor del borrow checker termine siendo que te hace buscar la manera de meterlo todo en arreglos y referenciarlo por índices para esquivarlo lo más posible
Como los objetos ya no se referencian directamente entre sí, la utilidad del sistema de tipos se reduce bastante y se vuelve muy difícil razonar sobre el código. Puedo creer que sea útil en sistemas muy grandes, pero en el programa pequeño que yo estaba escribiendo era más un estorbo
Eso incluye juegos, bases de datos, sistemas embebidos, trabajos por lotes de computación de alto rendimiento e incluso compiladores
Claro, siguen existiendo restricciones de aliasing, así que no habrá data races, pero todavía pueden aparecer bugs esencialmente iguales a los que surgen con punteros crudos
En ese proceso, quien toma prestado siempre vive menos que el dueño y solo puede acceder a la memoria asignada mientras está en posesión de ella. Cuando el dueño muere, se libera, y después de eso nadie puede usarla ni volver a liberarla, así que se evitan los use-after-free, las dobles liberaciones y el acceso a memoria no asignada
Incluso hay afirmaciones extrañas de que las arenas resuelven problemas de seguridad de memoria en C, cuando según el programa pueden igual provocar dangling pointers o use-after-free
El mismo problema aparece tanto en C/C++ como en Rust, solo que de maneras un poco distintas
Mi comentario en este post de hace dos meses: https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
En resumen, las ventajas son muy reales, pero también hay que hablar de las desventajas. Las arenas postergan la seguridad de memoria y la propiedad puede volverse complicada; además, las mutaciones y agregar listas/vectores también se complica, mientras que la representación con punteros es más amigable para el depurador
Abajo de este artículo está enlazada mi página de wiki, que agradecí porque tiene código real y mediciones: https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
Los términos de Prolog también se representan así en el heap de la Warren Abstract Machine (WAM). Si el término de Prolog
+(*(a,b), c), como en el ejemplo del artículo, se escribe en notación de operadores, queda asíexpr(E) :- E = a*b + c.Entonces se crea una representación aplanada en la pila global de la máquina virtual. En Scryer Prolog se pueden ver las instrucciones WAM con
?- wam_instructions(expr/1, Is), maplist(portray_clause, Is).El resultado sale como
put_structure(*,2,x(3)).,set_constant(a).,set_constant(b).,put_structure(+,2,x(2)).,set_value(x(3)).,set_constant(c).,execute(=,2).Ambos términos compuestos se linealizan y en el heap quedan con el functor seguido de sus argumentos, y cada uno ocupa exactamente una celda de memoria de la WAM. Los argumentos pueden apuntar a otras celdas de memoria
El heap es un arreglo de estas celdas, y todas las celdas tienen el mismo tipo concreto. Por ejemplo, Scryer Prolog usa 8 bytes por celda, lo que hace que acceder y modificar celdas sea muy eficiente en arquitecturas de 64 bits
“En lugar de asignar objetos
Exprpor todos lados en el heap, meterlos en un solo arreglo contiguo y hacer que los hijos se refieran por índices de ese arreglo en vez de punteros” se parece más a una representación alternativa del heap que a un verdadero aplanamiento. La forma del AST en sí no cambióEs algo que ya se ha hecho en muchos lenguajes, como en la familia Lisp, donde se meten cons cells y otros objetos en arreglos y se usan asignación tipo bump e índices como punteros
Si los objetos están en un arreglo, al recolector de basura le resulta más fácil recorrerlos en la fase de barrido después de marcar. La fase de marcado recorre el grafo buscando objetos alcanzables, y la fase de barrido pasa por el arreglo plano limpiando los bits de GC y marcando los objetos inalcanzables para reutilizarlos
Sería difícil encontrar una implementación de Lisp mínimamente seria que haga una llamada separada a
mallocpor cada cons cell. Si se hiciera así, necesitaría meterlos en una lista enlazada global para la fase de barrido del GC, o bien en un arreglo global que solo contenga punterosEn proyectos de Lisp de juguete hechos en un fin de semana, sí he visto al menos dos veces cons cells hechos con
malloc, con fugas de memoria y dejando el GC como un TODO gigantescoIncluso si las celdas vienen de un heap de arreglo compacto, al final puede aparecer un arreglo global. Por ejemplo, al implementar recolección generacional de basura con un asignador no copiador, se puede agregar una estructura auxiliar para juntar objetos jóvenes y barrerlos en ciclos rápidos de GC, y ese arreglo representaría el nursery
Es un buen texto, pero hay dos trampas
También se puede usar una unión etiquetada, pero hay que manejar el uso de memoria con inteligencia
La técnica de “memoria virtual” permite unir regiones fragmentadas de memoria física en una región continua de memoria virtual. Si el espacio de direcciones virtuales hubiera estado segmentado, no se habría fragmentado desde el principio, y cualquier región de memoria podría crecer siempre en su lugar sin chocar con otra
Entonces una implementación de
realloc()podría eliminar la ruta dememcpy(), qué lástimaPor dentro no sería segura, pero sí parece posible una interfaz segura de solo lectura. Liberar sería O(n), pero aun así sería mucho más rápido que un árbol
Me sorprendió que todavía quedaran dos punteros (“referencias”) en el nodo, aun sabiendo que el primer puntero siempre apunta exactamente al siguiente nodo
He visto que https://github.com/rswier/c4 usa ese enfoque. Claro, la legibilidad del código no es buena, pero es más pequeño y más rápido
Cuando se habla de arena en gestión de memoria, me hace pensar más en un asignador de arena que en “aplanamiento”
Cuando asignas muchos elementos con la misma vida útil, los asignas de forma más eficiente desde uno o más bloques grandes de memoria, y cuando termina esa vida útil común, liberas el bloque grande en lugar de los elementos individuales
Como solo necesitas consumir secuencialmente el espacio del bloque padre, no hace falta una lista libre como en un asignador de heap de propósito general, así que la asignación también puede ser más eficiente
En este contexto, el “aplanamiento” de usar índices en vez de punteros también puede verse como usar punteros relativos con respecto al bloque padre, es decir, offsets
Usé este tipo de estructura AST compacta al implementar V7(https://github.com/cesanta/v7), un parser e intérprete de JavaScript para entornos embebidos con memoria extremadamente limitada
Más adelante lo cambié por una etapa que compila del AST a bytecode, pero durante un tiempo recorrí directamente un AST implícito mientras interpretaba
También hice algo parecido en mi compilador de Yaml to Sql en https://yaml2sql.netlify.app
El proceso de aplanamiento es un poco raro, pero es divertido, y al final valió la pena el esfuerzo invertido
Por ejemplo, aplanar expresiones booleanas es un buen ejercicio para quien quiera intentarlo: https://github.com/revskill10/yaml2sql/blob/main/app/query.r...