Dá para fazer mais rápido que a busca binária
(lemire.me)- A busca binária, comumente usada para encontrar valores em arrays ordenados, compara apenas um valor por vez, mas CPUs modernas conseguem comparar vários valores simultaneamente com uma única instrução, e aproveitar isso pode aumentar bastante a velocidade da busca
- SIMD Quad é um algoritmo de busca hierárquica que divide o array em blocos de 16 itens, depois restringe rapidamente a posição do bloco com busca por interpolação quaternária, e dentro do bloco compara 16 elementos de uma vez com instruções SIMD
- Nos benchmarks, em cache warm no Intel ele mostrou desempenho mais de 2x superior ao da busca binária, e no cache cold da Apple também foi mais de 2x mais rápido, além de superar
std::binary_searchem todas as condições medidas - Em vez de dividir a busca ao meio, fazer uma divisão em quatro partes aumenta um pouco o número de instruções, mas em arrays grandes no Intel isso aproveita melhor o paralelismo em nível de memória, melhorando o desempenho com cache cold
- Como algoritmos de livros-texto não foram projetados assumindo o paralelismo de dados e de memória das CPUs atuais, redesenhá-los com foco nas características do hardware pode trazer ganhos reais de desempenho
Ideia principal
- A busca binária tem uma estrutura que compara um valor por vez, mas processadores ARM 64-bit e x64 modernos conseguem comparar 8 inteiros de 16 bits ao mesmo tempo com uma única instrução
- Aproveitando essa capacidade do hardware, é possível mudar a unidade de busca de elementos individuais para blocos, reduzindo drasticamente o número de comparações
- Em vez de dividir o array em duas partes, usar 4 partições (busca quaternária) pode aumentar um pouco o número de instruções, mas provavelmente esse não é o gargalo, e isso também permite aproveitar melhor o paralelismo em nível de memória
Forma básica de verificar 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 por um; em C++, o mesmo efeito pode ser obtido com
std::find - Em arrays grandes, a busca binária é mais rápida, repetindo o processo de descartar a metade superior ou inferior com base no valor do meio do intervalo de busca
- Em C++,
std::binary_searchretorna um booleano indicando se o valor existe - O formato Roaring Bitmap usa arrays de inteiros de 16 bits com tamanhos de 1 a 4096 e utiliza busca binária para verificar a existência de valores
Estrutura do algoritmo SIMD Quad
- Divide um array ordenado de inteiros sem sinal de 16 bits em blocos de tamanho fixo com 16 elementos
- Usa o último elemento de cada bloco como chave de interpolação para restringir a busca a um único bloco com maior probabilidade de conter o valor alvo, e então verifica os 16 elementos desse bloco simultaneamente com SIMD
- Etapas de funcionamento:
- Se o número de elementos for menor que 16, faz uma busca linear simples no conjunto inteiro
- Divide o array em blocos de 16 elementos consecutivos, com número total de blocos
num_blocks = cardinality / 16 - Usa o último elemento do bloco como chave para comparar os pontos de 1/4 do intervalo de busca atual com o valor alvo e ajustar
base - Se o bloco for válido, no ARM usa NEON e no x64 usa SSE2 para carregar 16 elementos e fazer comparações de igualdade em paralelo
- Os elementos restantes que não entram em um bloco completo são percorridos com busca linear
Método de benchmark
- Para cada tamanho de array entre 2 e 4096, foram gerados 100.000 arrays ordenados de inteiros sem sinal de 16 bits
- Para cada tamanho, foram feitas 10 milhões de consultas de pertencimento em dois modos
- modo cold: cada consulta pesquisa um array diferente para simular cache miss
- modo warm: o mesmo array é pesquisado 100 vezes seguidas para simular cache hit
- A métrica medida foi o tempo médio por consulta, comparando busca linear (
std::find), busca binária (std::binary_search) e SIMD Quad - Os sistemas de teste foram Apple M4 (Apple LLVM) e Intel Emerald Rapids (GCC)
Resultados das medições
- À medida que os arrays crescem, a busca binária supera claramente a busca linear, e com cache cold a busca linear fica ainda mais em desvantagem por exigir mais acessos aos dados
- Plataforma Intel: com cache warm, SIMD Quad foi mais de 2x mais rápido que a busca binária; com cache cold, o ganho foi menor
- Plataforma Apple: com cache cold, SIMD Quad foi mais de 2x mais rápido; com cache warm, o ganho foi mais limitado
- Em todos os casos, SIMD Quad foi mais rápido que
std::binary_search - A parte SIMD reduz o trabalho por meio de instruções especiais, com menos instruções e menos desvios, o que explica claramente o ganho de velocidade
Efeito da busca quaternária
- Também foi comparada uma versão SIMD binary que mantém a otimização SIMD, mas troca a busca por interpolação quaternária por busca binária
- Na plataforma Apple, o efeito da abordagem quaternária foi pequeno
- Na plataforma Intel, a abordagem quaternária foi uma otimização relevante em arrays grandes com cache cold
- Nos servidores Intel, a busca quaternária aproveita melhor o paralelismo em nível de memória
Pontos centrais da implementação
- A função
simd_quadrecebe um arrayuint16_t, o número de elementoscardinalitye o valor procuradopos, retornando um booleano gapé fixado em 16, e secardinality < gapa busca é feita com um laço simples- O laço de busca por blocos, enquanto
n > 3, lê e compara os últimos valores dos blocos nas posições 1/4, 2/4 e 3/4, movendobasepela soma dos três resultados de comparação - O bloco selecionado compara 16 elementos em dois grupos, em paralelo usando
vceqq_u16no ARM NEON ou_mm_cmpeq_epi16no x64 SSE2 - Na faixa restante de elementos, o retorno verifica se
v >= pose então devolve sev == pos
Conclusão
- A busca binária tradicional dos livros é um algoritmo razoável, mas pode ser acelerada de forma significativa em termos práticos
- Muitos algoritmos padrão não foram projetados assumindo o alto grau de paralelismo dos computadores atuais
- SIMD Quad é uma abordagem que busca 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
- Faster intersections between sorted arrays with shotgun
1 comentários
Comentários do Hacker News
Independentemente das otimizações de hardware de baixo nível mencionadas por Daniel Lemire, a busca binária ou suas variações de implementação só são a melhor opção quando tudo o que se sabe é que os dados estão ordenados/são monótonos
Se houver informação prévia sobre a distribuição dos dados, dá para usá-la para criar algoritmos muito mais rápidos. Um exemplo é como uma pessoa, com um dicionário em papel, consegue ir para o conjunto de páginas mais ou menos certo mais rápido do que com uma busca binária pura
Matematicamente, buscar em uma lista ordenada se parece mais com encontrar a função inversa de uma função monótona por meio de um algoritmo de controle em malha fechada, e também seria possível criar uma função de custo para usar descida do gradiente ou variantes aceleradas. De forma mais geral, quase sempre é mais eficiente usar mais informação sobre o problema específico que você quer resolver do que pegar a solução de uma formulação abstrata demais, e isso pode gerar ganhos de desempenho escaláveis muito maiores do que melhorias por fator constante obtidas usando melhor o hardware
O número fixo de iterações é bom para o preditor de desvios, e o loop principal também foi otimizado de forma bem agressiva para o hardware-alvo, evitando multiplicações. As tentativas de deixá-lo mais esperto pioraram o loop e não trouxeram ganho. Também é difícil porque o formato do array de structs tem tamanho 12 e, em geral, N é pequeno
Não favoritei, então volto a procurar umas duas vezes por ano. Diz a lenda que ainda estou procurando
É por isso que árvores B são o padrão em bancos de dados. Os dados podem ser qualquer coisa, e se você importar um grande lote de novas linhas, as características podem mudar drasticamente a qualquer momento
Até dá para construir algoritmos que acelerem consultas com algo como descida do gradiente, mas árvores B já são muito rápidas e ainda têm várias vantagens, como desempenho de pior caso e exigências de I/O previsíveis, varredura por intervalos, travessia ordenada e suporte a condições por prefixo
Dá para criar algoritmos de consulta mais eficientes para distribuições específicas de dados, mas muitas vezes eles perdem propriedades importantes. Mesmo que outro algoritmo faça uma estimativa inicial mais próxima, ele pode ser mais lento para encontrar o item final, e mesmo que a média seja melhor, o pior caso pode ser tão ruim que o torne impraticável
Mesmo em um dicionário de papel, depois da primeira estimativa você quase sempre usava algo muito próximo de busca binária, e o número de etapas economizadas por essa estimativa inicial é pequeno. Depois de chegar ao conjunto de páginas mais ou menos certo, você também tende a folhear linearmente um pouco além do necessário; uma busca binária rígida talvez fosse mais rápida, mas isso precisa ser equilibrado com o tempo de virar páginas
Ed Kmett refinou a ideia na biblioteca discrimination[2] para Haskell, e a apresentação técnica relacionada[3] também é 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
“Busca quaternária” não seria, no fim das contas, só um loop de busca binária desenrolado em um nível? Para achar o intervalo onde o item está, o número de comparações parece parecido, só que processando 4 por vez em vez de 2. Parece algo que desenrolamento de loop também conseguiria
Na prática, do ponto de vista do processador, todos os loops já vêm meio desenrolados, e sobra só o pequeno overhead do próprio loop. Na busca binária, o custo principal é trazer dados da memória ou do cache, então a disputa real é conseguir pedir o quanto antes os dados que serão necessários depois, para esperar menos pela chegada deles
A diferença de algoritmos como a busca quaternária é que, em vez de fazer pré-busca profunda só de um lado de cada desvio, eles fazem prefetch superficial de todos os casos possíveis. Assim, o prefetch que de fato vai ser necessário acaba sendo emitido de qualquer maneira, e se usa um pouco menos de largura de banda com dados que não serão usados no caminho de execução real
Para prever o desempenho real de um algoritmo de busca, “número de comparações” é quase uma métrica inútil. O gargalo não está em quantas comparações você consegue fazer, mas em quão bem consegue aproveitar a largura de banda de memória e cache. Se considerar até os detalhes internos do comportamento de desvios dos processadores modernos, até dá para ver isso como uma forma de desenrolamento de loop
De qualquer forma, as duas buscas são O(log N), com constantes diferentes. Em aulas de algoritmos, as constantes não importam muito, mas no mundo real elas podem pesar bastante
Recentemente também escrevi um texto[1] sobre busca exponencial[2]. É um algoritmo útil quando os próprios elementos buscados já estão ordenados e você precisa fazer busca binária repetidamente em um array; na nossa carga de trabalho tivemos ganho de 8x
[1] https://lalitm.com/post/exponential-search/
[2] https://en.wikipedia.org/wiki/Exponential_search
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, basta fazer busca binária entre 2048 e 4096 para encontrar o usuário mais recente e, de quebra, o total de usuários. Informação útil de se saber ao pesquisar concorrentes SaaS
Como a CPU sempre acessa uma linha de cache inteira, normalmente 64 bytes, talvez seja melhor pesquisar a linha de cache inteira. Depois que os dados já estão dentro da CPU, o custo é quase de graça
Então eu gostaria de tentar uma busca “binária” que, no ponto médio, examine todos os valores da linha de cache central e, se não houver correspondência, siga para a esquerda ou direita. Pesquisar uma linha de cache pode ser feito com uma única instrução SIMD de 512 bits. Uma linha de cache de 64 bytes contém 32 inteiros de 16 bits, então isso talvez pudesse ser quase 32x mais rápido que uma busca binária simples, ou ao menos reduzir em 32x os acessos à memória, o que dominaria na maioria dos programas reais
Com chaves de 4 bytes e ponteiros de filho de 4 bytes, ou índices de array, um nó interno pode preencher exatamente uma linha de cache de 64 bytes com 7 chaves, 8 ponteiros de filho e 1 ponteiro seguinte. Em 1 milhão de itens, a profundidade da árvore cai de algo como 20 para algo como 7, e é provável que os primeiros níveis permaneçam no cache
Com algum cuidado, dá para acelerar a busca dentro de nós de árvore B com SIMD, mas há muita dependência de dados
Para arrays menores, busca linear com valor sentinela no fim já é difícil de superar. Só que essa afirmação é meio enganosa porque “menor” é uma condição vaga demais para dar uma noção intuitiva
No geral, gostei do texto. Ele explorou perfeitamente algo que eu sempre tive curiosidade, inclusive com experimentos de eliminação úteis
Fiz alguns experimentos de busca em arrays pequenos, de 16 a 32 itens, e a busca binária foi uma das piores abordagens por causa dos desvios. Para arrays pequenos, o método mais rápido foi a busca linear sem desvios
Ela não interrompe o loop no meio e percorre todos os elementos. Por exemplo, se você quer saber se um número está no array, faz o OR lógico dos resultados do teste de todos os itens. Eu não usei SIMD, mas em arrays pequenos os desvios são tão caros que sai mais rápido simplesmente testar tudo sem desvios
A explicação do algoritmo me deixou um pouco confuso
A parte de SIMD só é usada na etapa final, isto é, ao pesquisar os últimos 16 elementos
A parte de busca quaternária verifica 3 pontos para criar 4 caminhos, mas ela está procurando o bloco correto, não simplesmente a chave correta
Os detalhes são interessantes: o autor usa o último elemento de cada bloco na busca quaternária. Fico curioso sobre como o algoritmo mudaria se usasse o primeiro elemento ou um elemento arbitrário
A intuição central aqui, de múltiplas comparações SIMD, parece escalável para algo maior do que só a etapa final
A ideia geral seria: a) usar gather para trazer vários elementos em 16 posições igualmente espaçadas b) comparar em paralelo com instruções SIMD c) focar no bloco correto d) trocar para busca linear quando o bloco ficar pequeno, ou então repetir o ciclo de gather/comparação
Instruções gather leem memória não contígua, então numa busca binária acabam lendo mais do que o necessário. Ainda assim, se permitirem comparação em várias direções e comprimirem 4 etapas de busca binária em uma só, talvez consigam vencer em tabelas grandes
Nem todo tipo de dado permite comparação completa em 16 direções. Busca em float64, mesmo com AVX-512, fica limitada a comparação em 8 direções, mas int32 e float32 permitem comparação em 16 direções
Acho bem provável que a busca binária acabe sendo mais rápida na prática do que uma abordagem baseada em gather
Os algoritmos clássicos de ciência da computação foram, na prática, “projetados” para CPUs sem paralelismo: sem múltiplos núcleos, sem Hyper-threading, sem instruções SIMD, com todos os acessos à memória custando o mesmo e sem noções como latência de cache L1/L2/L3, além da suposição de dados gerais/aleatórios
Quando você foge de qualquer uma dessas premissas, surgem muitos ajustes possíveis para melhorar o desempenho
Os algoritmos clássicos são um excelente ponto de partida para depois desenvolver soluções mais otimizadas quando você passa a conhecer melhor a forma específica dos dados ou as características/recursos da CPU
Quando se vai até a ponta mais extrema da otimização, normalmente se acaba olhando para como os dados ficam armazenados e são acessados na memória, e se uma mudança que melhora isso não prejudica etapas posteriores. Em um emprego antigo, alguém passou tempo demais otimizando uma parte específica do código, mas essa otimização expulsou do cache muitas informações necessárias depois, e o aplicativo inteiro acabou ficando mais lento
Isso provavelmente se aproxima da 5ª regra de programação de Rob Pike, que por sua vez é quase uma reformulação de algo dito por Fred Brooks 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: se a busca binária é boa porque reduz o espaço de busca pela metade a cada etapa, então busca ternária não seria melhor por reduzir para um terço de cada vez?
Em vez de comparar só um valor do meio, a ideia era comparar o valor em 1/3 e, se fosse baixo demais, comparar o valor em 2/3
Mas concluí que, embora cada etapa reduzisse o problema para 1/3 em vez de 1/2 como na busca binária, ela exigia em média 3/2 vezes mais comparações, então no fim dava na mesma
Correção: vendo a resposta de zamadatix, na verdade são 2 comparações em 2/3 dos casos, então a média real é 5/3
Primeiro terço: 1 comparação
Segundo terço: 2 comparações
Terceiro terço: 2 comparações
(1+2+2)/3 = média de 5/3 comparações. É fácil se enganar com a sensação de “faz 1 ou 2 comparações”, como se fosse 50%, mas na realidade a chance de resolver na primeira comparação é 1/3, e a de precisar de 2 comparações é 2/3
Assim, dá para mostrar que a busca ternária é 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 etapas diminui, mas para chegar até o fim você acaba fazendo mais comparações em média. Isso tende a valer para buscas desse tipo em geral, sempre que o fator de divisão é maior que 2. Claro, isso assume que o valor buscado tem distribuição uniforme e que o custo das operações é idealizado, e é justamente aí que entra a discussão do texto principal
Não como uma versão ternária do algoritmo de busca binária, porque isso não é busca ternária de verdade, e sim algo mais próximo de uma busca binária enviesada. Como comparações são essencialmente binárias, algoritmos de busca baseados em comparação são todos, em certo sentido, variantes de busca binária, e escolher algo que não seja o elemento central é menos eficiente em termos de complexidade algorítmica. Ainda assim, em hardware real isso pode ser melhor sob certas condições. Para fazer uma busca ternária de verdade, a operação básica precisaria ser uma comparação de 3 vias
A coisa fica interessante quando se considera a “eficiência de radix”[1]. A melhor escolha é 3, o número natural mais próximo de e. Isso também se relaciona com busca em árvores, e é possível que árvores ternárias sejam melhores que árvores binárias
[1] https://en.wikipedia.org/wiki/Optimal_radix_choice
Então aquela ideia, que talvez não fosse prática nas CPUs da época, pode hoje ter mais chances de funcionar