ASTs e achatamento de estruturas de dados de compiladores

• Ao representar uma AST não como um grafo de objetos conectados por ponteiros, mas como um único array e índices, o layout de memória e a forma de gerenciamento das estruturas de dados típicas de compiladores ficam mais simples
• O exemplo em Rust implementa uma AST achatada com uma mudança pequena: trocar Box<Expr> por ExprRef e adicionar add/get a ExprPool
• Em um microbenchmark que cria cerca de 100 milhões de nós de AST e os interpreta imediatamente, a implementação comum levou 3,1 s, enquanto a achatada levou 1,3 s, ficando 2,4× mais rápida
• A diferença de desempenho vem da localidade proporcionada pelo layout contíguo de memória, de referências menores que usam índices de 32 bits em vez de ponteiros de 64 bits, da alocação barata e da liberação em nível de pool
• Ao aproveitar a propriedade de que, no array, os filhos ficam antes dos pais, uma travessia recursiva da árvore se transforma em execução linear, levando a uma forma próxima de um interpretador de bytecode

---

Ideia básica do achatamento

• Arena ou região é amplamente usada em implementações modernas de linguagens, e a abordagem tratada aqui é o achatamento de estruturas de dados, usando uma arena que contém apenas um tipo como se fosse um array simples
• É uma técnica que troca ponteiros por índices de array em estruturas de dados com muitos ponteiros; o exemplo central é uma AST, mas ela também pode ser aplicada a outras estruturas de dados de compiladores
• O código de exemplo está no repositório flatcalc, e a diferença entre a implementação comum e a achatada pode ser vista na comparação de branches
• A mudança no código é pequena, mas no microbenchmark houve ganho de velocidade de 2,4×; além do desempenho, há vantagens também em termos de usabilidade do código

Representação comum de AST

• A linguagem do exemplo é uma linguagem de expressões aritméticas muito simples, que só oferece suporte a literais inteiros e quatro operadores aritméticos binários
  • Exemplos de programas possíveis são 42, 0 + 14 * 3 e (100 - 16) / 2
• A representação em Rust é composta pelos enums BinOp e Expr
  • Expr::Binary(BinOp, Box<Expr>, Box<Expr>)
  • Expr::Literal(i64)
• O Box<Expr> de Rust corresponde a um ponteiro para Expr, desempenhando um papel parecido com Expr* em C
• O parser, o formatador de saída e o interpretador têm estruturas típicas, e o interpretador é escrito como um método recursivo sobre Expr
• A semântica aritmética é construída para que todas as expressões sejam avaliadas, no fim, como i64
  • Soma, subtração e multiplicação usam operações com wrapping
  • Divisão por zero é tratada com checked_div, retornando 0
• Um gerador de programas aleatórios com seed fixa de PRNG mede o desempenho de manipulação da AST sem os custos de parsing e saída

Trocar a AST por array e índices

• O achatamento consiste em duas mudanças
  • Em vez de alocar cada objeto Expr individualmente no heap, armazená-los em um único array contíguo
  • Referenciar nós filhos por índices dentro do array, em vez de ponteiros
• No exemplo em Rust, ExprPool é definido como um newtype de Vec<Expr>

struct ExprPool(Vec<Expr>);

• O papel dos ponteiros existentes é assumido por ExprRef, baseado em um inteiro de 32 bits

struct ExprRef(u32);

• A mudança central de tipo é trocar os campos de filhos de Binary de Box<Expr> para ExprRef

enum Expr {
    Binary(BinOp, ExprRef, ExprRef),
    Literal(i64),
}

• Em ExprPool, são adicionados os utilitários add, para inserir um novo Expr, e get, para localizar um Expr a partir de um ExprRef
• O parser não retorna Expr diretamente; ele adiciona o nó a ExprPool e depois retorna um ExprRef
• O interpretador também deixa de ser um método de Expr e passa a ser um método de ExprPool, desreferenciando a referência com self.get(expr) antes do pattern matching
• A mudança inteira é pequena: trocar Box<Expr> por ExprRef e inserir add e get nos pontos necessários

Vantagens de desempenho

• A principal vantagem de uma AST achatada é a localidade de memória
  • Um Expr comum, baseado em ponteiros, corre risco de fragmentação de memória
  • Um Expr achatado fica concentrado em uma região contígua de memória, permitindo que o cache de dados e o prefetcher funcionem melhor
  • Um alocador de memória suficientemente inteligente talvez consiga um efeito parecido, mas usar um array denso reduz a incerteza
• O tamanho das referências também diminui
  • Ponteiros comuns têm 64 bits nas arquiteturas modernas
  • Se forem necessários no máximo 4.294.967.295 nós de AST, uma referência de 32 bits é suficiente
  • É possível economizar 50% de espaço por referência, o que pode reduzir o uso total de memória em ASTs com muitos ponteiros
  • Para estruturas de dados menores, referências de 16 ou 8 bits também são possíveis
• O custo de alocação fica menor
  • Não é necessário chamar malloc para cada nó
  • Se memória suficiente tiver sido reservada previamente, é possível criar espaço para um novo Expr com bump allocation, apenas incrementando um tail pointer
• A liberação pode ser tratada em nível de pool
  • Parte-se da premissa de que cada Expr individual não será liberado separadamente
  • Em muitas implementações de linguagens, ASTs tendem a ser criadas juntas e desaparecer juntas
  • Uma AST comum precisa seguir ponteiros e liberar cada nó, mas uma AST achatada pode liberar o ExprPool inteiro de uma vez
• Em introduções a arena allocation, a liberação barata costuma ser destacada como o principal motivo, mas em ambientes de compiladores a AST pode permanecer até o fim da compilação, então a liberação talvez seja o motivo menos importante

Vantagens na usabilidade do código

• O achatamento simplifica o gerenciamento de lifetimes
  • Uma AST com n nós pode ser pensada como tendo um único lifetime de AST, em vez de n lifetimes
  • Em Rust, essa simplificação afeta diretamente a expressão dos lifetimes no código
  • Em vez de gerenciar os lifetimes de &Expr, pode-se passar ExprRef, que é um u32, e depender do lifetime de ExprPool
• A mesma simplicidade pode se aplicar a linguagens com gerenciamento manual de memória, como C++
• O array achatado facilita implementar deduplicação
  • É possível evitar a criação de expressões idênticas com hash consing ou até de uma forma mais simples
  • Por exemplo, expressões Literal usadas com frequência, de 0 a 127, podem ser reservadas nas primeiras 128 posições de ExprPool
  • Quando o literal inteiro 42 for necessário, pode-se retornar ExprRef(42) sem criar um novo Expr
• Algo parecido também é possível em representações baseadas em ponteiros, mas é provável que uma estrutura de dados auxiliar seja necessária

Resultados do microbenchmark

• O benchmark gera um programa aleatório com cerca de 100 milhões de nós de AST e o passa imediatamente ao interpretador
  • O parser e o formatador de saída não são incluídos
  • Como ele gera um programa e o executa imediatamente, não é um benchmark realista
• As condições do experimento têm algumas limitações
  • Reserva-se previamente espaço suficiente em Vec<Expr> para conter o programa inteiro
  • Em ambientes reais, seria necessário estimar melhor o tamanho da arena
  • Como há pouco trabalho além de geração e execução, as vantagens de alocação e liberação baratas podem ser exageradas
  • Como o programa é grande demais, a proporção que cabe no cache da CPU é pequena, então os efeitos de localidade podem ser subestimados
• Com Hyperfine, foram comparadas as médias de 10 execuções em um notebook
  • O ambiente era M1 Max de 10 núcleos a 3,2 GHz, 32 GB de memória, macOS 13.3.1 e Rust 1.69.0
• A implementação comum levou 3,1 s, e a achatada levou 1,3 s, mostrando ganho de velocidade de 2,4×
• Para observar separadamente o custo de liberação, foram criadas versões de ambas as implementações que pulam a deallocation
  • A implementação achatada teve tempos quase iguais na versão no-free e na versão padrão, então o tempo de liberação não foi grande
  • A implementação comum caiu de 3,1 s para 1,9 s, ou seja, usava cerca de 38% do tempo para liberar memória
  • Mesmo comparando apenas as versões no-free, a implementação achatada é 1,5× mais rápida que a comum

Interpretador que aproveita diretamente a representação achatada

• O achatamento foi usado inicialmente como uma mudança de implementação interna que substitui alocação comum e ponteiros, mas também é possível aproveitar diretamente as propriedades da representação em array
• Se Expr for imutável, os nós filhos precisam ser criados antes dos nós pais
  • Ao criar a * b, a e b ficam em ExprPool antes do * que os referencia
  • As setas de referência sempre apontam de trás para frente no array, e o fluxo de dados avança para frente
• Usando esse invariante, é possível criar um interpretador que escaneia o ExprPool do início ao fim, em vez de descer recursivamente a partir da raiz
  • A travessia sempre visita os filhos antes dos pais
  • O resultado de cada expressão é armazenado no vetor state
  • Uma expressão binária consulta state pelos índices ExprRef dos filhos para obter os valores
  • No fim, retorna o resultado correspondente ao root solicitado
• Esse interpretador “extra-flat” não tem gerenciamento de pilha de chamadas recursivas e consegue percorrer ExprPool linearmente
• Por outro lado, ele pode ser desfavorável à localidade, pois precisa acessar aleatoriamente um vetor state grande
• No resultado, o interpretador extra-flat levou 1,2 s, enquanto o interpretador achatado baseado em recursão levou 1,3 s, uma melhora de 8,2%

Ligação com interpretadores de bytecode

• Um comentário de Bob Nystrom no Reddit vê essa abordagem como, na prática, uma recriação da ideia de um interpretador de bytecode
• A struct Expr funciona como uma instrução de bytecode, e referências a variáveis entram como referências codificadas em u32
• Se a tabela simples state for trocada por uma estrutura parecida com uma pilha, isso fica quase indistinguível de um interpretador de bytecode projetado desde o início
• Mesmo mudando apenas a estrutura de dados da AST, a travessia da árvore se desloca naturalmente para um modelo de bytecode

Materiais relacionados

• Materiais sobre achatamento no contexto de compiladores
  • Mike Pall atribui parte do desempenho do LuaJIT a uma “IR linear e sem ponteiros”
  • Um artigo que explica o desempenho do typechecker Sorbet para Ruby destaca as vantagens de packed arrays e da troca de ponteiros de 64 bits por índices de 32 bits
  • O projeto Oil shell oferece uma coleção de links sobre representação compacta de AST
• Ideias parecidas também aparecem em áreas orientadas a desempenho fora da implementação de linguagens
  • O Gibbon, de Purdue e Indiana, é próximo de um trabalho que transfere programas que parecem código comum para uma implementação achatada
  • Andrew Kelley trata do uso de índices em vez de ponteiros em uma palestra sobre data-oriented design
  • Um artigo de visão geral sobre bibliotecas de arena em Rust aborda a usabilidade de lifetimes relacionada a arenas
  • Um artigo comparando handle vs pointer em desenvolvimento de jogos defende reunir objetos do mesmo tipo em arrays e referenciá-los por índice
  • Artigos relacionados a ECS tratam de temas ligados à localidade
• O artigo de Inanna Malick sobre uma linguagem de calculadora toy em Rust também aplica a mesma técnica e usa junto ideias de recursion schemes do mundo Haskell

[GN⁺]

Comentários no Hacker News

• O Blender (software de modelagem 3D) é um caso interessante dessa abordagem. Para tornar o carregamento/salvamento de arquivos rápido e sem perdas, ele usa a mesma representação em disco e na memória
  Ou seja, tudo fica em uma arena, e salvar/carregar é quase como fazer memcpy da arena inteira. Pensando na complexidade potencial do projeto Blender e nos problemas de serialização/desserialização, parece um excelente design
  A desvantagem é que, como ele precisa continuar abrindo arquivos de versões antigas, o design das estruturas de dados tende a ficar engessado

  • A peça que falta em “o design das estruturas de dados fica engessado porque é preciso abrir arquivos de versões antigas” é uma forma de evoluir as estruturas de dados ao longo do tempo, como em migrações de banco de dados
    Essas transformações só seriam executadas ao carregar dados de versões antigas do app, e depois bastaria salvar imediatamente em disco na versão atualizada para não pagar esse custo de novo
    https://www.inkandswitch.com/cambria/ criado no contexto de CRDT é um exemplo de implementação dessa ideia e pode servir de boa inspiração, mesmo que não se aplique diretamente
  • Já trabalhei em um grande app comercial baseado em um framework de E/S feito internamente que funcionava com um princípio parecido, e foi realmente doloroso
    Gostando ou não do framework de E/S, ele simplesmente serializava as structs como estavam, então era preciso sempre projetar as estruturas de dados pensando no futuro, sabendo que ficaríamos presos àquela forma para sempre. Foi uma era sombria
  • Acho que o Microsoft Word da antiga era do “doc” também não despejava structs diretamente no disco?
    Por isso escrever conversores virou um grande problema, e pelo que lembro era preciso decifrar estruturas de dados internas do Word que não eram documentadas
  • Um jogo de PlayStation em que trabalhei fazia exatamente isso, e tudo era assinado, então não havia nenhuma preocupação com atacantes
    Se alguém conseguia alterar os arquivos no disco, isso já significava que havia comprometido o dispositivo. Em compensação, o carregamento era absurdamente rápido: tudo era lido para a memória e depois só se ajustava a posição dos ponteiros para o endereço real onde foi carregado
  • Pelo que sei, o Microsoft Word também usou essa abordagem no começo, e isso virou uma grande dor quando o formato de arquivo evoluiu

• Gosto de árvores de sintaxe abstrata achatadas. Gosto especialmente da abordagem usada no processamento de marcação inline do pulldown-cmark. Há uma explicação simples em https://fullyfaithful.eu/pulldown-cmark/
  A entrada bruta é dividida em uma sequência de nós, e algo como * vira um nó MaybeEmphasis, porque pode representar ênfase ou, se não encontrar par, continuar como texto
  Na etapa seguinte, usa-se uma pilha para percorrer os nós em ordem e procurar pares possíveis. Quando um par é encontrado, o nó MaybeEmphasis é convertido no nó de ênfase apropriado, e toda a sequência de nós entre o nó de abertura e o de fechamento é recortada para virar a subárvore do novo nó
  Essa transformação da árvore é bem incomum, então uma implementação simples pode facilmente virar O(n), mas em uma representação de AST achatada ela pode ser feita em O(1), independentemente do número de nós ou da profundidade da pilha
  A representação detalhada da árvore está em https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6... e, basicamente, mantém índices child e next junto com o conteúdo do nó. O código de cirurgia da árvore durante o pareamento de ênfase está em https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6...
  O desempenho é excelente. O pulldown-cmark talvez não seja o parser CommonMark isoladamente mais rápido, mas é bem competitivo e, por exemplo, muito mais veloz do que abordagens que fazem uma alocação por nó

• Isso me fez lembrar de uma apresentação da GDC elogiando Rust. A ideia era que Rust, por causa do borrow checker, ou te deixa maluco, ou te força a estruturar o código com um sistema de entidade-componente
  É curioso que, em casos reais com problemas complexos de lifetime, o valor do borrow checker acabe estando em te levar a colocar tudo em arrays e referenciar por índices, encontrando formas de evitá-lo o máximo possível

  • Pela minha pouca experiência usando a engine de jogos Bevy em Rust, o sistema de entidade-componente parecia uma forma muito sofisticada de escrever código espaguete
    Como os objetos deixam de se referenciar diretamente, a utilidade do sistema de tipos cai bastante, e fica muito difícil raciocinar sobre o código. Acredito que possa ser útil em sistemas muito grandes, mas, nos programas pequenos que eu estava escrevendo, parecia mais um obstáculo
  • Sim. Os lifetimes de Rust perdem força em certas áreas de programação de alto desempenho que evitam heap ou até não usam heap
    Jogos, bancos de dados, embarcados, trabalhos em lote no estilo computação de alto desempenho e até compiladores entram nisso
    Claro, as restrições de aliasing ainda existem, então não haverá race conditions de dados, mas bugs essencialmente iguais aos que surgem com ponteiros brutos ainda podem acontecer
  • Dito de outra forma, dá para ver isso como forçar entidades de longa duração a serem donas da memória e a emprestá-la para objetos de curta duração
    Nesse processo, quem toma emprestado sempre vive menos que o dono e só pode acessar a memória alocada enquanto ela estiver possuída. Quando o dono morre, ela é liberada, e depois disso ninguém pode usá-la nem liberá-la de novo, então você evita use-after-free, double free e acesso a memória não alocada
  • Sim. Continuo vendo menções a arenas ou estruturas de árvore/grafo achatadas sem falar de segurança de memória
    Também há a alegação estranha, em C, de que arenas resolvem problemas de segurança de memória, quando, dependendo do programa, elas podem igualmente acabar causando dangling pointers ou use-after-free
    O mesmo problema aparece de formas um pouco diferentes tanto em C/C++ quanto em Rust
    Meu comentário neste post de dois meses atrás: https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
    Em resumo, as vantagens são muito concretas, mas as desvantagens também precisam ser mencionadas. Arenas deixam a segurança de memória para depois e a propriedade pode ficar complicada, além de mutações e adições a listas/vetores também se tornarem mais complexas; já a representação com ponteiros é mais amigável para depuração
    No fim deste artigo há um link para a minha página na wiki, que agradeci por trazer código real e medições: https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
  • Um ponteiro é apenas um índice para um espaço de memória. Se Rust pretende resolver problemas gerais de programação, parece que o borrow checker deveria ser capaz de lidar não só com índices especializados em espaço de memória, mas com todos os índices

• Termos de Prolog também são representados assim na heap da Warren Abstract Machine (WAM). Se o termo Prolog +(*(a,b), c) do exemplo do texto for escrito em notação de operadores, fica assim
  expr(E) :- E = a*b + c.
  Aí é criada uma representação achatada na pilha global da máquina virtual. No Scryer Prolog, dá para inspecionar as instruções WAM com ?- wam_instructions(expr/1, Is), maplist(portray_clause, Is).
  O resultado sai 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).
  Os dois termos compostos são ambos linearizados, ficando na heap na forma do functor seguido pelos argumentos, e cada um ocupa exatamente uma célula de memória da WAM. Os argumentos podem apontar para outras células de memória
  A heap é um array dessas células, e todas elas têm o mesmo tipo concreto. Por exemplo, o Scryer Prolog usa 8 bytes por célula, o que torna acesso e modificação de células muito eficientes em arquiteturas de 64 bits

• “Em vez de sair alocando objetos Expr na heap, colocar tudo em um único array contíguo e fazer os filhos referirem-se por índice nesse array em vez de ponteiros” parece mais uma representação alternativa de heap do que propriamente achatamento. A forma da AST em si não mudou
  É algo já feito em várias linguagens, como nas da família Lisp, colocando cons cells e outros objetos em arrays, com alocação bump e ponteiros por índice
  Quando os objetos estão em um array, o coletor de lixo consegue percorrê-los com facilidade na fase de varredura depois que a marcação termina. A fase de marcação percorre o grafo em busca de objetos alcançáveis, e a fase de varredura passa pelo array achatado limpando bits de GC e marcando objetos inalcançáveis para reutilização
  É difícil encontrar uma implementação minimamente séria de Lisp que chame malloc separadamente para cada cons cell. Se fizer isso, será preciso colocá-los em uma lista ligada global para a fase de varredura do GC, ou então em um array global contendo apenas ponteiros
  Já vi pelo menos duas vezes projetos de Lisp de fim de semana em que cons cells eram alocados com malloc, vazavam, e o GC ficava como um enorme TODO
  Mesmo que as células venham de uma heap em array compactado, um array global ainda pode acabar existindo. Por exemplo, ao implementar coleta de lixo geracional com um alocador sem cópia, você pode adicionar objetos jovens a um array auxiliar para varrê-los em ciclos rápidos de GC, e esse array representaria o nursery

• É um bom texto, mas há duas armadilhas

  1. Se você armazenar os nós em um array redimensionável, conforme o programa de entrada cresce o compilador passa a precisar de um bloco de memória contíguo maior. Esse bloco pode existir ou não. Dá para contornar isso alocando blocos do tamanho de páginas e usando-os como pool
  2. É preciso tomar cuidado com a forma de representar nós de AST no código. Por exemplo, se você armazenar nós como um tipo união, a união fica do tamanho do maior membro e, como nem todos os nós de AST têm o mesmo tamanho, os nós menores acabam recebendo padding desnecessário para se ajustar ao tamanho do maior nó
  • Esse ponto sobre nós menores de AST receberem padding desnecessário por causa do tamanho do maior nó de AST é realmente muito bom, e eu também mencionei isso no meu post de blog sobre tipos inteiros com largura de bits personalizada: https://alic.dev/blog/custom-bitwidth
    Uniões com tag também são possíveis, mas é preciso lidar com o uso de memória de forma inteligente
  • Às vezes eu penso que seria melhor se não tivéssemos acabado com um espaço de endereçamento plano
    A técnica de “memória virtual” permite juntar regiões fragmentadas de memória física em uma região contínua de memória virtual. Se o espaço de endereçamento virtual fosse segmentado, ele não teria se fragmentado em primeiro lugar, e qualquer região de memória poderia sempre crescer no lugar sem colidir com outra região
    A implementação de realloc() poderia então eliminar o caminho de memcpy(), uma pena
  • Isso pode ser mitigado com uma estrutura parecida com rope, dividindo o vetor em chunks de tamanho fixo e usando ponteiros reais. Assim, não seria preciso realocar
    Por dentro não seria seguro, mas parece possível ter uma interface segura somente para leitura. A liberação seria O(n), mas ainda assim muito mais rápida do que uma árvore

• Fiquei surpreso ao ver que ainda restam dois ponteiros (“referências”) no nó, mesmo já sabendo que o primeiro ponteiro sempre aponta exatamente para o próximo nó
  Já vi https://github.com/rswier/c4 usar esse tipo de abordagem. Claro, a legibilidade do código não é boa, mas fica menor e mais rápido

• Quando se fala em arena no gerenciamento de memória, eu penso mais em um alocador de arena do que em “achatamento”
  Ao alocar muitos itens com o mesmo tempo de vida, eles são alocados com mais eficiência em um ou mais grandes blocos de memória, e quando esse tempo de vida comum termina, libera-se o bloco grande em vez dos itens individuais
  Como basta usar o espaço do bloco pai de forma sequencial, não é necessária uma lista livre como em um alocador de heap de propósito geral, então a alocação também pode ser mais eficiente
  Nesse contexto, o “achatamento” de usar índices em vez de ponteiros também pode ser visto como o uso de ponteiros relativos ao bloco pai, isto é, offsets

• Usei esse tipo de estrutura compacta de AST ao implementar o V7, um parser e interpretador de JavaScript para ambientes embarcados com memória extremamente limitada (https://github.com/cesanta/v7)
  Depois mudei para uma etapa de compilação da AST para bytecode, mas por um tempo percorri diretamente uma AST implícita durante a interpretação

• Também fiz algo parecido no meu compilador Yaml to Sql em https://yaml2sql.netlify.app
  O processo de achatamento é meio estranho, mas divertido, e no fim valeu o esforço investido
  Por exemplo, o achatamento de expressões booleanas é um bom exercício para quem quiser tentar: https://github.com/revskill10/yaml2sql/blob/main/app/query.r...