Achatamento de ASTs e outras estruturas de dados de compiladores

• Arenas ou regiões são uma técnica simples e eficaz para compiladores e sistemas semelhantes a compiladores.
• Usar arenas para achatar árvores de sintaxe abstrata (ASTs) pode melhorar o desempenho e oferecer mais praticidade.
• Achatamento significa empacotar nós da AST em um único array e usar índices do array em vez de ponteiros.
• ASTs achatadas oferecem benefícios como melhor localidade, referências menores e alocação e desalocação mais baratas.
• ASTs achatadas podem simplificar o gerenciamento de memória e permitir deduplicação de forma conveniente.
• Os resultados de desempenho mostram que a versão achatada do interpretador pode ser 2,4 vezes mais rápida do que a versão comum.
• É possível melhorar ainda mais o desempenho aproveitando a representação plana da AST para eliminar a recursão e usar varreduras lineares.
• Este artigo discute os ganhos de desempenho obtidos por meio do achatamento de estruturas de dados em um interpretador de linguagem de programação.
• Além disso, o interpretador achatado mostra uma melhora de desempenho de 8,2% em relação ao interpretador recursivo, com 1,2 s contra 1,3 s.
• Na prática, essa técnica reinventa a ideia de um interpretador de bytecode, com a struct Expr sendo usada como instrução de bytecode.
• Outros textos e projetos sobre achatamento de estruturas de dados são mencionados, incluindo LuaJIT, o verificador de tipos Sorbet e o shell Oil.
• Conceitos semelhantes relacionados a achatamento e otimização de localidade também aparecem em domínios como videogames, processamento de dados serializados, design orientado a dados e sistemas entidade-componente.
• O artigo recomenda também conferir a publicação de Inanna Malick, que aplica a mesma técnica a uma linguagem de "calculadora" de brinquedo implementada em Rust.
• São discutidas limitações do uso dessa técnica em Rust, incluindo a impossibilidade de incluir outras Expr inline dentro da própria struct Expr.
• A comparação de desempenho foi realizada em um MacBook Pro com processador M1 Max e 32 GB de memória, executando macOS 13.3.1 e Rust 1.69.0.

[GN⁺]

Comentários no Hacker News

• O Blender usa a mesma representação em disco e na memória para carregamento e salvamento de arquivos rápidos e sem perdas.
• Um AST achatado é usado no pulldown-cmark para fazer parsing eficiente de marcação inline.
• A representação de AST achatado permite transformações de árvore em O(1), independentemente do número de nós ou da profundidade da pilha.
• O desempenho do pulldown-cmark é excelente em comparação com outros parsers CommonMark.
• A Warren Abstract Machine (WAM) usa uma representação achatada no heap para Prolog.
• O achatamento de AST já era um conceito usado em linguagens como Lisp.
• Armazenar nós em um array redimensionável pode causar problemas de alocação de memória, mas isso pode ser mitigado com pooling em blocos do tamanho de páginas.
• É preciso ter cuidado com a forma como os nós do AST são representados no código, evitando padding desnecessário.
• Usar índices em vez de ponteiros pode gerar código menor e mais rápido.
• Memória achatada pode ser implementada com um alocador de memória personalizado, útil em cenários específicos.
• Uma estrutura de AST compacta foi usada para implementar um parser e interpretador de JavaScript em ambientes com restrição de memória.