Static Search Trees: 40 vezes mais rápido que a busca binária

• Implementa uma árvore de busca estática chamada "árvore S+" para realizar buscas rápidas em dados ordenados
• Parte do código proposto em um post da Algorithmica, otimizando-o e transformando em código ideias adicionais e melhorias sugeridas
• Após analisar o código assembly, otimiza ao máximo todas as instruções possíveis para extrair o maior desempenho
• Introduz batching para processar várias consultas em paralelo e aumentar o throughput
• O objetivo é executar consultas de forma eficiente em dados ordenados por meio da árvore S+, mantendo alto throughput

1. Introdução e motivação

• Definição do problema:

  • Entrada: lista ordenada de inteiros sem sinal de 32 bits vals: Vec<u32>
  • Saída: uma estrutura de dados com tamanho mínimo que retorna o valor maior ou igual a uma consulta específica (q)
  • Métrica: número de consultas independentes processadas por segundo

• Objetivo:

  • Construir estruturas de dados eficientes em bioinformática, especialmente para acelerar buscas em suffix arrays usados na indexação de sequências de DNA
  • Maximizar o desempenho aproveitando a performance da CPU e instruções SIMD

• Materiais recomendados:

  • Estudos sobre busca binária e layout de arrays ("Array Layouts for Comparison-Based Searching")
  • Materiais introdutórios sobre árvore S+ e B-trees estáticas

2. Árvore S+ e otimizações

2.1 Busca binária e layout Eytzinger

• A busca binária da biblioteca padrão do Rust tem baixa eficiência de cache, e o desempenho cai à medida que os dados aumentam
• Layout Eytzinger:
  • Armazena a árvore de busca binária em forma de array, maximizando o uso de cache
  • Desempenho: até 4 vezes mais rápido que a busca binária para dados que ultrapassam o cache L3

2.2 Conceito de árvore S+

• S-tree:
  • Estrutura de árvore hexadecimal com 15 valores ordenados por nó
  • Mais eficiente que uma B-tree e mais compactável que o layout Eytzinger
• Árvore S+:
  • Armazena todos os dados nos nós folha, com duplicação nos nós superiores
  • Oferece busca simples e uma estrutura eficiente

2.3 Otimização da função find

• Busca linear básica:
  • Percorre os dados e retorna o valor que atende à condição (ineficiente)
• Vetorização automática:
  • Converte para código sem desvios, dobrando o desempenho com uso de SIMD
• Implementação SIMD manual:
  • Otimiza manualmente com instruções SIMD, extraindo o máximo desempenho com 5 instruções

3. Batching e prefetching

3.1 Batching

• Processa várias consultas em paralelo para compensar a latência de memória
• O aumento do tamanho do lote melhora o throughput, saturando no tamanho máximo de lote 16

3.2 Prefetching

• Traz o próximo nó para a memória antecipadamente, melhorando o desempenho com dados além do cache L3
• Em conjunto com batching, reduz o tempo de processamento de 45ns/query para 30ns/query

4. Layout de dados e otimização estrutural

4.1 Alteração do tamanho do nó

• Reduz os valores por nó para 15, simplificando operações de multiplicação e aumentando a eficiência de cache
• Há uma leve melhora de desempenho para dados dentro do cache L3

4.2 Alteração do layout de memória

• Testa armazenar o layout em ordem inversa ou com configuração que minimiza padding
• Nem o layout inverso nem a redução de padding tiveram grande impacto no desempenho

5. Particionamento de dados

5.1 Particionamento baseado em prefixo

• Separa partes com base nos bits mais altos dos dados
• Melhora o desempenho em dados pequenos, mas gera overhead de memória

5.2 Subárvores comprimidas

• Empacota cada subárvore para aumentar a eficiência de espaço
• Exige rastrear o tamanho das partes, e a velocidade de consulta cai um pouco

6. Comparação multithread

• Com 6 threads, o tempo por consulta cai de 27ns para 7ns
• A limitação de largura de banda da RAM se torna o gargalo

7. Conclusão e pesquisas futuras

• Mais de 40 vezes de ganho de desempenho em relação à busca binária (1150ns/query → 27ns/query)
• Próximos desafios:
  • Otimizar o balanceamento dos dados e reduzir acessos à RAM
  • Tratar consultas de intervalo e consultas ordenadas
  • Integrar busca em suffix arrays

[beenzinozino]

Nossa... se isso for aplicado às bibliotecas nativas de várias linguagens, parece que o impacto será bem significativo.

[GN⁺]

Comentários no Hacker News

• Observa que o Rust está sendo usado cada vez mais em conteúdo de baixo nível relacionado a algoritmos. No passado, predominavam conteúdos escritos em C(++) ou em pseudocódigo científico

  • Não conhece bem Rust, mas conseguiu entender o conteúdo escrito em Rust. É semelhante ao fato de um programador Rust conseguir entender exemplos de algoritmos escritos em C
  • Prefere que Rust se torne padronizado, e acha que seria bom se Zig também fosse usado

• A abordagem de dividir consultas em lotes não foi explorada. O principal custo está em fazer buscas em tabelas fora do cache

  • Se houver consultas suficientes, é possível resolver várias camadas da árvore de uma só vez
  • Pode surgir o problema de precisar ordenar os resultados na ordem correta de saída

• A quantidade de valores int32 não é tão grande, e o bitset completo tem 512MB. Para uma estrutura de dados genérica, recomenda Roaring Bitmaps

  • Se só forem necessárias consultas simples, vale considerar uma função de hash perfeita mínima

• Ficou surpreso com as formas de aumentar a eficiência de baixo nível em Rust. Gostaria de comparar com uma implementação em C++

• A vantagem da árvore Eytzinger é que existe uma fórmula para converter índices de nós em posições de percurso em ordem

  • É útil quando o armazenamento base das chaves é um conjunto de chaves ordenadas
  • Com Eytzinger, é possível prever com antecedência várias iterações do loop

• É surpreendente que haja um overhead de ~27ns para buscar u32 em 4GB de memória

  • Fica curioso sobre como a otimização evolui com tamanho de lote 8
  • Os resultados com multithreading também são interessantes. Ao passar de 1 para 6 threads, o overhead melhora 4 vezes

• Há muita discussão sobre Rust e C++, mas pensa em como implementar isso em Common Lisp mantendo SIMD

• Sempre que lê textos sobre otimização de baixo nível, agradece ao autor por gastar tempo economizando nanossegundos

  • Fica pensando quanto tempo a humanidade já economizou no total com o acúmulo dessas otimizações

• Acha que há um erro na figura 3 da seção 1.7. Sugere que o rótulo do eixo y da figura 1 da seção 1.3 deveria ser "taxa de retrocesso"

• Se for preciso oferecer suporte ocasional a escrita, dá para usar uma grande árvore de busca estática junto com uma pequena árvore gravável

  • Quando houver mudanças suficientes, elas podem ser migradas para uma nova versão da árvore estática