- Compartilhamento das estratégias de projeto e implementação de um lexer ultrarrápido feito do zero para a linguagem purple-garden, junto com dados reais de desempenho medido
- Aplicação de várias técnicas de otimização, como threaded lexing (baseado em tabela de salto), strings em janela com cópia zero, interning e bump allocator
- Maximização da velocidade de parsing por meio de hashing de tokens e comparação de hash pré-calculado para dicionário de palavras-chave; a tabela de salto supera um
switch simples em eficiência de cache da CPU
- mmap do arquivo inteiro e minimização de alocação dinâmica para reduzir drasticamente o custo de IO e gerenciamento de memória em entradas grandes
- Demonstração de velocidade de processamento mais de 10x maior em comparação com lexers famosos existentes (por exemplo, flex, handcoded), com números de microbenchmark por etapa de parsing/runtime
Visão geral do pipeline de lexing e compilação
- O lexer (tokenizador) converte a string de entrada em uma lista de tokens significativos, que depois é recebida pelo parser para gerar a AST (árvore sintática abstrata)
- O projeto de tokens na linguagem purple-garden mantém uma estrutura mínima, guardando apenas o enum TokenType e informações de string/tipo
Projeto de um lexer mínimo e exemplos de código
- A struct do lexer armazena apenas a string de entrada e a posição atual
- Geração de tokens conforme cada caractere usando
switch
- Uso de array de mapeamento tipo-string e inicialização por tipo para depuração
Threaded Lexing (baseado em tabela de salto)
- Em vez de
switch, o processamento de distinção de tokens é feito com jump table (computed goto)
- Em um array de 256 bytes, cada valor de caractere é usado como índice para mapear o rótulo de tratamento correspondente
- Na ramificação real do código, a macro
JUMP_TARGET executa o salto imediatamente
- Vantagens:
- Execução mais rápida com menos cache miss e otimização de previsão de desvios, entre outros ganhos
- Desvantagens:
- Sem suporte no MSVC (apenas Clang e GCC) e depuração mais difícil
Gerenciamento de memória e abstração de allocator
- Definição de interface para várias estratégias de alocação de memória, como bump allocator (struct
Allocator)
- A macro
CALL simplifica logs verbosos e o repasse de contexto
- São apresentados exemplos de código e estruturas para alocação/liberação reais e estatísticas
Cópia zero e processamento de strings baseado em janelas
- Introdução da struct Str (ponteiro, comprimento, hash) para processamento eficiente em C
- Implementação direta de slice, concat, eq, hashing e conversão numérica, entre outros
- Slices de string são criados instantaneamente apenas movendo o ponteiro, sem alocação de memória
- A conversão numérica também usa um algoritmo próprio de conversão caractere-inteiro
Hashing de tokens e comparação de palavras-chave com hash pré-calculado
- Cálculo do hash (FNV-1a) na criação do token para otimizar comparações repetidas e interning
- Palavras-chave constantes como
true/false são comparadas imediatamente por hash para ramificação mais rápida
is_alphanum (detecção de letras/números/caracteres especiais) também é otimizado com operações de bit e lookup
Otimização do parsing numérico e transferência para a etapa de compilação
- No lexer, apenas a janela e o hash do token numérico são armazenados; a conversão real para inteiro/ponto flutuante é feita uma única vez na etapa de compilação, sem duplicação
- Foi confirmada uma melhora de mais de 64% no throughput total ao fazer parsing repetido de valores numéricos duplicados
Aceleração de IO para arquivos grandes
- Em vez do método tradicional
fread, o arquivo inteiro é mapeado diretamente na memória com mmap
- A função
IO_read_file_to_string faz mmap de toda a entrada, mostrando melhora de 6x a 35x em arquivos grandes
Benchmarks práticos e comparação de desempenho
- Em laptop: 44 ms apenas para tokenização com entrada de 25 MB e mais de 1.000.000 de linhas
- Em desktop: 30 ms para a mesma entrada (até 848 MB/s)
- Em comparação com outros lexers, desempenho mais de 10x superior (
0.3s vs 2~13s)
- Nos microbenchmarks, o efeito de cada otimização é quantificado (ex.: adoção de bump allocator
1.58x, strings com 0 alloc 1.4~1.5x, mover o parsing numérico para a etapa de compilação 2.8x, etc.)
Resumo da estratégia de implementação
- Ramificação direta baseada em tabela de salto (threaded lexing)
- Estrutura de token em janela com cópia zero
- Interning de tokens constantes
- Gerenciamento de memória com bump allocator
- Hashing de tokens e comparação com hash pré-calculado
- Parsing tardio e interning de tokens numéricos e de string
- Processamento de arquivos grandes com mmap
- Como próximos passos, são sugeridos uso de SIMD, algoritmos de hash mais rápidos, alinhamento de memória e prefetch e otimização da tabela de salto por tipo de entrada
Ainda não há comentários.