Você pode superar a busca binária

• A verificação de pertencimento em arrays ordenados pode ser feita de forma mais rápida do que a busca binária clássica de livro-texto, e o SIMD Quad foi mais rápido que std::binary_search em todas as condições medidas
• O SIMD Quad divide um array ordenado de inteiros sem sinal de 16 bits em blocos de 16 elementos e faz busca por interpolação quaternária nos limites dos blocos, com comparações paralelas via SIMD dentro de cada bloco
• ARM 64 bits moderno e x64 (Intel/AMD) conseguem comparar 8 inteiros de 16 bits com uma única instrução, reduzindo a necessidade de seguir literalmente a estrutura da busca binária que examina um valor por vez
• O benchmark foi executado com 100.000 arrays ordenados de tamanho 2 a 4096 e 10 milhões de consultas de pertencimento; o modo cold simula falhas de cache e o modo warm simula acertos de cache
• Na Intel, com cache warm, o SIMD Quad foi mais de 2x mais rápido que a busca binária; na Apple, com cache cold, foi mais de 2x mais rápido; e, em arrays grandes com cache cold na Intel, a abordagem quaternária aproveitou melhor o paralelismo em nível de memória

---

O gargalo da verificação de pertencimento em arrays ordenados

• A forma mais simples de verificar se um valor existe em um array ordenado é a busca linear, percorrendo os valores um a um; em C++, o mesmo efeito pode ser obtido com std::find
• Em arrays grandes, a busca binária é mais rápida e repete o processo de descartar a metade superior ou inferior com base no valor do meio da faixa de busca até encontrar o valor ou chegar a uma faixa vazia
• Em C++, std::binary_search retorna um booleano indicando se o valor existe
• O formato Roaring Bitmap usa arrays de inteiros de 16 bits com tamanho de 1 a 4096 e usa busca binária para verificar a existência de valores

O ponto de partida do SIMD Quad

• A maioria dos processadores modernos possui instruções de paralelismo de dados, ou SIMD, e ARM 64 bits e x64 (Intel/AMD) conseguem comparar 8 inteiros de 16 bits com o valor alvo em uma única instrução
• Por causa dessa característica, não é necessário continuar descendo com a busca binária até blocos menores que 8, e também é barato comparar 16 elementos ou mais
• A busca binária examina um valor por vez, mas processadores recentes conseguem carregar e testar vários valores de uma só vez e também têm bom paralelismo em nível de memória
• Em vez de dividir o array em duas partes, é possível tentar uma busca quaternária, dividindo em quatro; mesmo que o número de instruções aumente um pouco, o gargalo pode não estar na quantidade de instruções

Estrutura do algoritmo SIMD Quad

• O SIMD Quad é um algoritmo de busca para arrays ordenados de inteiros sem sinal de 16 bits, combinando busca por interpolação quaternária com SIMD
• O array é dividido em blocos de tamanho fixo com 16 elementos, e o último bloco pode ser uma exceção
• O último elemento de cada bloco é usado como chave de interpolação para restringir a busca a um único bloco com maior probabilidade de conter o valor alvo; em seguida, os 16 elementos desse bloco são testados simultaneamente com SIMD
• O fluxo central é uma busca em camadas: menos comparações com busca por interpolação nos limites dos blocos e comparações paralelas via SIMD dentro do bloco
• As etapas de funcionamento são as seguintes
  • Se o número de elementos for menor que 16, faz uma busca linear simples no array inteiro
  • O array de tamanho cardinality é dividido em blocos de 16 elementos consecutivos, e o número total de blocos é num_blocks = cardinality / 16
  • Os últimos elementos dos blocos nas posições 16-1, 32-1 etc. são usados como chaves, comparando os pontos de 1/4 da faixa de busca atual com o alvo pos e ajustando base
  • Com base no resultado da interpolação, escolhe-se o índice de bloco apropriado lo
  • Se o bloco for válido, no ARM usa-se NEON e no x64 usa-se SSE2 para carregar 16 elementos e fazer comparações de igualdade em paralelo com o valor alvo; se houver correspondência, retorna true
  • Os elementos restantes que não entram em um bloco completo de 16 são verificados com busca linear

Metodologia do benchmark

• Para cada tamanho de array entre 2 e 4096, o benchmark gerou 100.000 arrays ordenados de inteiros sem sinal de 16 bits
• Para cada tamanho, foram executadas 10 milhões de consultas de pertencimento em dois modos
  • Modo cold: cada consulta pesquisa um array diferente, simulando falhas de cache
  • Modo warm: as consultas são agrupadas por array e o mesmo array é pesquisado 100 vezes seguidas, simulando acertos de cache
• A métrica medida foi o tempo médio por consulta, e os algoritmos comparados foram busca linear (std::find), busca binária (std::binary_search) e SIMD Quad
• Os sistemas de medição foram Apple M4 com Apple LLVM e processador Intel Emerald Rapids com GCC

Resultados das medições

• Na comparação entre busca linear e busca binária, a busca binária vence conforme o array cresce
• Com cache cold, a busca linear é relativamente mais prejudicada, porque mais acessos a dados aumentam as falhas de cache
• Depois de a busca binária se mostrar superior à busca linear de forma geral, ela foi comparada com o SIMD Quad
• Os resultados nas plataformas Intel e Apple foram claramente diferentes
  • Na plataforma Intel, com cache warm, o SIMD Quad foi mais de 2x mais rápido que a busca binária
  • Na plataforma Intel, com cache cold, o ganho foi menor
  • Na plataforma Apple, ao contrário, o SIMD Quad foi mais de 2x mais rápido com cache cold, e o ganho foi mais limitado com cache warm
• Em todos os casos, o SIMD Quad foi mais rápido que a busca binária
• A parte SIMD reduz o trabalho com instruções especiais e usa menos instruções e desvios, o que torna o ganho de velocidade fácil de entender

O efeito da busca quaternária

• Também foi comparada uma versão SIMD binary que mantém a otimização com SIMD, mas troca a busca por interpolação quaternária pela busca binária padrão
• Na plataforma Apple, o efeito da abordagem quaternária foi pequeno
• Na plataforma Intel, em arrays grandes com cache cold, a abordagem quaternária foi uma otimização significativa
• Nos servidores Intel, a busca quaternária aproveitou melhor o paralelismo em nível de memória

Pontos centrais da implementação

• A função simd_quad recebe um array uint16_t, o número de elementos cardinality e o valor a procurar pos, retornando um booleano
• gap é fixado em 16, e se cardinality < gap, a busca é feita com um loop simples
• O loop de busca por blocos, enquanto n > 3, lê os valores finais dos blocos nos pontos de 1/4, 2/4 e 3/4, compara com pos e move base pela soma dos três resultados de comparação
• Depois disso, enquanto n > 1, são feitas comparações com base na metade para reduzir a faixa restante e, por fim, seleciona-se o bloco lo
• O bloco selecionado é comparado em duas metades de 16 elementos usando vceqq_u16 no ARM NEON ou _mm_cmpeq_epi16 no x64 SSE2
• Na faixa de elementos restantes, retorna-se se v == pos no ponto em que v >= pos; se não aparecer até o fim, retorna false

Conclusão e materiais

• A busca binária clássica de livro-texto é um algoritmo razoável, mas pode ser tornada significativamente mais rápida na prática
• Muitos algoritmos padrão não foram projetados assumindo o alto grau de paralelismo dos computadores atuais
• O SIMD Quad é uma abordagem que tenta explorar tanto o paralelismo em nível de memória quanto o paralelismo de dados
• Algoritmos ainda melhores podem ser possíveis, e abordagens mais criativas são necessárias
• Código-fonte
• Interseções mais rápidas entre arrays ordenados com shotgun

[GN⁺]

Comentários do Hacker News

• Independentemente da discussão do Daniel Lemire sobre otimizações de hardware de baixo nível, binary search e suas variações de implementação só são a melhor opção quando a única coisa que se sabe é que os dados estão ordenados/são monotônicos
  Se houver conhecimento prévio sobre a distribuição dos dados, dá para usar essa informação e projetar algoritmos muito mais rápidos. Por exemplo, em um dicionário de papel, uma pessoa consegue pular para um conjunto de páginas apropriado mais rápido do que com uma binary search puramente ideal
  Matematicamente, buscar em uma lista ordenada é quase como inverter uma função monotônica com um algoritmo de controle em malha fechada, e também seria possível usar uma função de custo adequada com gradient descent ou variantes aceleradas
  De forma mais geral, para resolver um problema de maneira mais eficiente, o melhor costuma ser usar mais informações sobre o problema específico que você quer resolver, em vez de recorrer a uma solução excessivamente abstrata. Isso pode dar ganhos escaláveis de ordens de grandeza, maiores do que melhorias por fator constante obtidas ao usar melhor o hardware
  • Já pensei bastante sobre binary search, mas não consegui superar esta implementação: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
    1. verifica em O(1) se é uma lista densa, 2) verifica o limite superior, 3) usa binary search com número fixo de iterações
       O número fixo de iterações é bom para o branch predictor, e o loop principal também é otimizado de forma bem agressiva para o hardware-alvo, evitando multiplicações. Todas as tentativas de deixá-lo mais esperto acabaram piorando o loop e não compensaram o custo. É um formato array-of-structs de tamanho 12, e o N também costuma ser pequeno, o que dificulta ainda mais
  • A frase “é melhor usar mais informações sobre o problema específico que você quer resolver” é óbvia e profunda ao mesmo tempo. Quanto mais informação você já tem, mais informação você já tem
  • Lembro de ter lido um artigo sobre treap em que, em vez de balancear a árvore, usavam os pesos para Huffman encode a profundidade de busca e assim reduzir o tempo médio de acesso quando as frequências de acesso variam
    Não salvei nos favoritos, então acabo procurando de novo umas duas vezes por ano
  • Sim, mas o ponto principal é que muitas vezes você não conhece melhor os dados
    É por isso que B-tree é o padrão em bancos de dados. Os dados podem ser qualquer coisa, e se você importar muitas linhas novas de uma vez, as propriedades podem mudar bastante a qualquer momento
    Você até pode tentar projetar algo para acelerar lookup com algoritmos como gradient descent, mas a B-tree já é muito rápida, tem desempenho de pior caso e exigências de I/O previsíveis, além de muitas vantagens como range scan, ordered traversal e condições de prefixo
    Dá para criar algoritmos de lookup mais eficientes para distribuições específicas de dados, mas muitas vezes eles perdem propriedades importantes. Mesmo que outro algoritmo dê uma estimativa inicial mais próxima, ele pode acabar sendo mais lento para encontrar o item final, e pode ter média melhor mas pior caso terrível, o que dificulta o uso na prática
    Mesmo num dicionário de papel, depois da primeira estimativa quase sempre se usa binary search, e isso só reduz alguns movimentos. Quando você chega às páginas mais ou menos corretas, acaba fazendo uma busca linear além do necessário; uma binary search estrita talvez fosse mais rápida, mas é preciso equilibrar isso com o tempo de virar páginas
  • Fritz Henglein fez um trabalho interessante sobre ordenação/agrupamento rápido. O artigo principal parece ser Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1]
    Ed Kmett refinou a ideia na biblioteca discrimination[2] para Haskell, e uma apresentação técnica relacionada[3] também foi muito interessante
    [1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
    [2]: https://hackage.haskell.org/package/discrimination
    [3]: https://www.youtube.com/watch?v=cB8DapKQz-I
• “quaternary” parece mais um unrolling de um passo do loop de binary search, não? No fim, ainda é preciso fazer aproximadamente o mesmo número de comparações para descobrir em qual partição o item está; só que em vez de processar 2 de cada vez, processa 4, então imagino que loop unrolling produza algo parecido
  • É mais complicado do que isso. Processadores modernos fazem speculative execution, então eles chutam o resultado da comparação e continuam seguindo um dos branches até descobrir que erraram ou atingir algum limite interno
    Se erram, descartam esse trabalho especulativo, pagam alguns ciclos de penalidade e recomeçam de outro ponto
    Isso significa que, do ponto de vista do processador, todo loop já é em certa medida desenrolado, e o principal custo da binary search é buscar dados da memória ou do cache. Então o verdadeiro jogo é emitir o quanto antes os pedidos dos dados que serão necessários depois, para reduzir a latência
    Quad search e buscas de ordem ainda maior fazem prefetch raso de todos os casos possíveis, em vez de fazer prefetch profundo só de um lado de cada branch. Assim, garantem que o prefetch que realmente será necessário seja emitido, e também reduzem um pouco a bandwidth gasta com dados que não serão usados no caminho de execução real
    “Número de comparações” quase não serve como métrica para prever desempenho real em algoritmos de busca. O gargalo não é a quantidade de comparações, mas sim usar ao máximo a bandwidth de memória e de cache. Levando em conta o comportamento de branch em processadores modernos, até dá para enxergar como loop unrolling
  • Dá para ver como um certo loop unrolling. O ganho de desempenho não vem de reduzir muito o número de instruções ou leituras de memória, mas de aliviar a dependency entre operações, para não ficar numa execução puramente serial. Também dá para pensar como uma execução especulativa dos dois lados do branch
  • Quaternary search efetivamente faz ao mesmo tempo a comparação da iteração atual e as duas comparações possíveis da próxima iteração. É um pouco mais complexo que um simples loop unrolling
    De todo modo, as duas buscas são O(log N), mudando só a constante. Em aulas de algoritmos, a constante importa menos, mas no mundo real ela pode importar bastante
  • Em parte sim, mas também está eliminando a data dependency entre etapas desenroladas
  • Porque o processador não funciona do jeito ingênuo que as pessoas imaginam
• Recentemente também escrevi um artigo[1] sobre Exponential Search[2]. É outro algoritmo útil quando você precisa repetir binary search em um array no qual os próprios elementos buscados já estão ordenados
  No nosso workload, ele trouxe ganho de 8x em velocidade
  [1] https://lalitm.com/post/exponential-search/
  [2] https://en.wikipedia.org/wiki/Exponential_search
  • Exponential search é útil em APIs REST que endereçam recursos por IDs sequenciais quando você precisa do último ID, mas não há endpoint dedicado para isso
    HEAD /users/1 -> 200 OK
    HEAD /users/2 -> 200 OK
    HEAD /users/4 -> 200 OK
    ...
    HEAD /users/2048 -> 200 OK
    HEAD /users/4096 -> 404 Not Found
    Depois disso, basta fazer binary search entre 2048 e 4096 para achar o usuário mais recente e, de quebra, o número de usuários. É uma informação bastante útil ao investigar empresas concorrentes de SaaS
• A CPU sempre acessa de uma vez uma cache line de 64 bytes inteira, então dá para pesquisar a cache line toda. Depois que os dados entram na CPU, isso fica praticamente de graça
  Por isso, eu queria tentar uma busca “binária” em que se verifica todos os valores da “cache line do meio” e, se não estiver ali, vai para a esquerda/direita. A busca na cache line poderia ser feita com uma única instrução SIMD de 512bit
  Uma cache line tem 64 bytes, ou seja, 32 inteiros de 16 bits, então esse tipo de busca poderia ser quase 32 vezes mais rápida que uma binary search simples. Pelo menos os acessos à memória cairiam em 32x, e na maioria dos programas reais isso é o fator dominante
  • Num binary search tree implementado como sorted vector, comparar a cache line inteira do topo com o alvo dificilmente vai dar correspondência. Em vez disso, é preciso usar os dados extras dentro da linha para reduzir a busca, e aí você chega em B-Tree/B+tree
    Com chave de 4 bytes e child pointer ou índice de array de 4 bytes, um internal node ocupa exatamente uma cache line de 64 bytes com 7 chaves, 8 child pointers e 1 next pointer. Em uma árvore com 1 milhão de entradas, a profundidade cai de algo como 20 para algo como 7, e os níveis superiores provavelmente ficam no cache
    Também dá para aplicar SIMD no nó da B-tree para acelerar a busca interna do nó, mas a dependência de dados é muito alta
• Para arrays pequenos, busca linear com sentinel value no final já é difícil de bater. Só que “pequeno” é um qualificador muito vago, então a afirmação acaba sendo menos intuitiva do que poderia
  • Pelos ótimos benchmarks deste artigo, a busca linear começa a ficar para trás por volta de 200~400 elementos, então não é uma observação tão trivial assim
    No geral, gostei muito do artigo por explorar perfeitamente uma dúvida que eu tinha com um estudo de ablação bastante útil
• Fiz alguns experimentos de busca em arrays pequenos, de 16 a 32 itens, e binary search foi uma das piores abordagens, por causa dos muitos branches
  O mais rápido em arrays pequenos foi linear branchless search. Ou seja, em vez de sair do loop no meio, ela percorre todos os elementos. Por exemplo, se você só quer saber se um número está no array, pode fazer OR lógico dos resultados das verificações de todos os itens
  Não usei SIMD, mas em arrays pequenos o custo de branch é tão alto que costuma ser mais rápido simplesmente verificar todos os elementos sem branch
  • Fico curioso se isso é mais rápido por causa do padrão que o prefetcher gosta
• A explicação do algoritmo me deixou um pouco confuso
  A parte de SIMD só aparece no estágio final, na busca dos últimos 16 elementos
  A parte “quad” consiste em verificar 3 pontos para criar 4 caminhos, mas não está procurando apenas a chave exata; está procurando o bloco correto
  Os detalhes são interessantes: o autor usa o último elemento de cada bloco para a quad search. Fiquei curioso sobre como o algoritmo mudaria se usasse o primeiro elemento de cada bloco, ou um elemento arbitrário
• A intuição central daqui, de fazer comparações SIMD com vários elementos, parece aplicável não só à etapa final, mas também em escala maior
  A ideia geral seria: 1) usar gather para buscar vários elementos em 16 posições igualmente espaçadas, 2) comparar em paralelo com instruções SIMD, 3) focar no bloco correto, 4) se o bloco ficar pequeno, trocar para busca linear; caso contrário, repetir o ciclo de gather/compare
  A instrução gather lê memória não contígua e lê mais do que uma binary search comum, mas permite comparação multiway e elimina quatro etapas de binary search, então pode valer a pena em tabelas grandes
  Porém, nem todo tipo de dado permite comparação 16-way completa. Busca em float64 fica limitada a 8-way mesmo com AVX-512, enquanto int32 e float32 permitem comparação 16-way
  • gather é extremamente lento. Quem busca eficiência vai evitá-lo
    Aposto que binary search acaba sendo mais rápida na prática do que uma abordagem baseada em gather
• Os algoritmos clássicos da ciência da computação foram basicamente “projetados” para CPUs sem paralelismo. Sem múltiplos cores, sem Hyper-threading, sem instruções no estilo SIMD, e num modelo em que todo acesso à memória tem o mesmo custo, sem diferenças de latência como L1/L2/L3 cache. Também se assume que os dados são genéricos e aleatórios
  Se qualquer uma dessas suposições deixa de valer, aparecem vários ajustes para obter desempenho melhor
  A vantagem dos algoritmos clássicos é que eles oferecem um excelente ponto de partida para desenvolver soluções mais eficientes e otimizadas quando você conhece melhor uma determinada forma de dados ou características/quirks de uma CPU específica
  Na fronteira da otimização, normalmente você passa a olhar como os dados são armazenados e acessados na memória, e se mudanças para melhorar isso não prejudicam etapas posteriores. Num emprego antigo, alguém passou muito tempo otimizando uma parte específica do código, mas essa otimização expulsava mais informação útil do cache depois, e a aplicação como um todo acabou ficando mais lenta
  Isso provavelmente ecoa a quinta regra de programação do Rob Pike, ou indo mais para trás, algo que Fred Brooks disse em The Mythical Man Month. Referência: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
• Quando eu era adolescente, passei um fim de semana inteiro pensando que, se binary search é boa porque reduz pela metade o espaço de busca a cada etapa, então ternary search não seria melhor por dividir em três a cada etapa?
  Em vez de comparar só com o valor do meio, compara com o valor no ponto de 1/3 e, se for baixo demais, compara com o valor no ponto de 2/3
  Mas achei que, em cada etapa, em vez de reduzir o espaço de busca para 2/3 em comparação com 1/2 da binary search, você reduz para 1/3 em vez de 1/2, só que faz em média 3/2 vezes mais comparações, então no fim seria equivalente
  Correção: como respondeu zamadatix, na prática são 5/3 comparações. No caso dos 2/3, é preciso comparar duas vezes
  • Essa abordagem ternária não faz em média 3/2 comparações por nível
    O primeiro terço exige 1 comparação, o segundo terço exige 2, e o terceiro terço também exige 2, então a média é (1+2+2)/3 = 5/3. É fácil se enganar achando que é “1 ou 2 comparações, então 50% para cada”, mas na verdade a chance de parar na primeira é 1/3 e a de fazer 2 comparações é 2/3
    Por isso, ternary search é um pouquinho pior em número médio total de comparações. 5/3 * Log_3[n] = 1.052... * Log_2[n]
    Ou seja, o número de níveis cai, mas em média você faz mais comparações para chegar ao fim. Isso vale de modo geral para buscas com número de divisões maior que 2, sob algumas hipóteses padrão como distribuição uniforme do valor buscado e custo de operação idealizado. As diferenças do hardware real discutidas no texto entram justamente aqui
  • Havia algo ali na intuição daquele adolescente
    Só não como versão ternária do algoritmo de binary search. Isso não seria uma ternary search de verdade, mas algo mais próximo de uma binary search enviesada. Comparações são intrinsecamente binárias, então algoritmos de busca baseados em comparação são, de certo modo, um tipo de binary search, e escolher algo diferente do elemento central é menos eficiente em termos de complexidade algorítmica. Claro que no hardware real pode ser melhor em certas condições. Para fazer uma ternary search de verdade, a operação básica precisaria ser uma 3-way comparison
    A parte interessante aparece ao pensar em radix efficiency[1], onde a melhor escolha é o número natural mais próximo de e, isto é, 3. Isso também se relaciona com busca em árvores, e uma ternary tree pode ser melhor que uma binary tree
    [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
  • Em armazenamento como disco, onde não dá para fazer seek rápido, você pode usar por exemplo uma B-tree de 128 vias. O custo de buscar 128 chaves não é muito maior do que buscar 1 chave, mas isso evita mais 7 fetches
  • Depois disso, fico curioso se você chegou a imaginar uma CPU com comparador ternário
  • Desde a época em que você era adolescente, as CPUs ficaram dramaticamente mais largas tanto em execution width quanto em capacidade vetorial. O aumento de throughput mudou o equilíbrio na direção de gastar mais operações para reduzir dependency chains
    Aquela ideia talvez fosse impraticável nas CPUs da época, mas pode ser mais realista nas CPUs atuais