A busca binária branchless mais rápida

 (mhdm.dev)
1 pontos por GN⁺ 2023-08-13 | 1 comentários | Compartilhar no WhatsApp
  • sb_lower_bound mantém a mesma interface de std::lower_bound e mostrou ser até 2x mais rápida que a busca binária comum quando o ramo de comparação é compilado como movimentação condicional (cmov)
  • Como o resultado da comparação na busca binária não permite saber antecipadamente a posição procurada, há muitas falhas de predição de desvio; no x86, a opção clang -mllvm -x86-cmov-converter=false ajuda a reduzir isso
  • Esta implementação reduz length pela metade a cada loop e atualiza apenas first conforme o resultado da comparação, diminuindo o número de instruções, e sempre faz k+1 comparações no intervalo 2^k <= n < 2^(k+1)
  • No benchmark com clang -cmov, o tempo médio de execução foi de 61.30ns para std::lower_bound, 33.24ns para sb_lower_bound e 32.73ns para bb_lower_bound; a média geométrica também mostrou grande diferença, com 39.17ns, 19.81ns e 21.33ns, respectivamente
  • Em buscas com strings de 8 bytes, nas quais a função de comparação é lenta, std::lower_bound às vezes ficou ligeiramente à frente; em arrays grandes, uma variante com prefetching foi em média cerca de 2.3x mais rápida que std::lower_bound

Estrutura básica de sb_lower_bound

  • sb_lower_bound é uma função C++ com a mesma forma de std::lower_bound
    • As entradas são first, last, value, comp
    • O valor retornado é o iterador para a primeira posição em que a comparação falha; se todos os elementos satisfizerem a condição, retorna last
  • O loop principal reduz length pela metade e move first para frente apenas quando comp(first[length], value) é verdadeiro
  • Aqui, “branchless” não significa que o if desaparece, mas sim que esse if é compilado como uma instrução de movimentação condicional, como cmov, em vez de um salto condicional
  • No clang, usando a opção -mllvm -x86-cmov-converter=false, essa forma pode ser compilada como movimentação condicional

Onde std::lower_bound fica mais lento

  • A busca binária tradicional compara o elemento do meio com value e depois escolhe o intervalo da esquerda ou da direita
  • Quando a posição do alvo é desconhecida, if (comp(first[half], value)) tende a se tornar um desvio difícil de prever
  • A CPU executa antecipadamente as próximas instruções com predição de desvio, mas, se errar a previsão, precisa descartar o trabalho já feito
  • Com movimentação condicional, é possível escolher valores com base no resultado da comparação e reduzir saltos condicionais
  • clang -cmov conseguiu transformar parte dos if/else de std::lower_bound em movimentação condicional, deixando-o cerca de 25% mais rápido
  • O gcc não tem uma boa opção para forçar movimentação condicional no mesmo cenário, e sb_lower_bound também não gera hoje código branchless independentemente do nível de otimização

Busca “ótima” do ponto de vista do número de comparações

  • Aqui, “ótima” significa uma busca binária com o menor número de comparações possível
  • Em uma lista de tamanho n, os resultados possíveis de std::lower_bound são n+1: n posições de elementos mais a posição final
  • Se o tamanho da lista é 2^k - 1, então há 2^k resultados possíveis; como cada comparação fornece 1 bit de informação verdadeiro/falso, o número ótimo de comparações é k
  • No caso “bonito”, em que o comprimento é 2^k - 1, é possível fazer uma busca ótima com um loop muito curto
  • Se o comprimento não encaixa nesse formato, pode ocorrer acesso fora dos limites, como no caso de [0, 1, 2, 3, 4, 5] quando value é 4

Características de desempenho e limitações de sb_lower_bound

  • Ao dividir um intervalo de tamanho par, sb_lower_bound nem sempre pula elementos suficientes, mesmo quando o resultado da comparação é verdadeiro
  • No intervalo 2^k <= n < 2^(k+1), ele sempre faz k+1 comparações
  • No mesmo intervalo, std::lower_bound faz k ou k+1 comparações e, em média, cerca de log2(n+1) comparações
  • O número de comparações pode ser maior, mas a quantidade de instruções dentro do loop é bem menor, então o tempo total de execução acaba sendo mais rápido
  • Quando a função de comparação é muito lenta, a diferença entre k+1 e log2(n+1) comparações pode impactar o desempenho
  • Para forçar movimentação condicional no gcc, há a opção de usar cmov com assembly inline específico para x86, mas a abordagem simples aumenta o número de instruções e a alternativa exige assembly separado por tipo

A variante mais rápida bb_lower_bound

  • bb_lower_bound divide o intervalo de outra forma até que o comprimento vire 2^k - 1, e então faz a busca em um segundo loop mais rápido
  • length & (length + 1) é usado para verificar se o comprimento tem a forma 11..1, isto é, 2^k - 1
  • Em comprimentos irregulares, usa-se o valor MAGIC auto step = length / 8 * 6 + 1 para aproximar rapidamente o intervalo de uma faixa “bonita”
  • Em geral, step precisa ser pelo menos length / 2 para entrar com frequência no loop rápido, mas, se ficar próximo demais de length, perde-se a vantagem da busca binária
  • Por causa do break, bb_lower_bound passa a ter um formato com ramificação
  • Um método que usaria uma tabela pré-calculada com o step mais rápido para todos os comprimentos ainda não foi explorado

A implementação totalmente branchless não foi mais rápida

  • Em uma máquina de 64 bits, o loop de sb_lower_bound roda no máximo 64 vezes, então é possível criar uma versão “totalmente branchless” que elimina até a checagem de length usando switch e fall-through intencional
  • A ideia é saltar para a posição de código correspondente ao número de comparações necessário usando std::bit_width(length)
  • Na prática, o desempenho não foi melhor
  • CPUs x86 modernas lidam muito bem com desvios previsíveis, como a condição de loop, então não houve ganho em remover a checagem de length
  • Também se concluiu que o loop comum é melhor por evitar templates, macros e a necessidade de copiar e ajustar 64 casos

Resultados de benchmark

  • No tempo médio de execução (ns), os resultados com clang -cmov foram os seguintes
    • std::lower_: 61.30
    • branchless_lower_: 43.43
    • asm_lower_: 54.32
    • sb_lower_: 33.24
    • sbm_lower_: 35.54
    • bb_lower_: 32.73
  • A média geométrica do tempo de execução (ns) também foi a menor para sb_lower_
    • std::lower_: 39.17
    • branchless_lower_: 25.14
    • asm_lower_: 31.21
    • sb_lower_: 19.81
    • sbm_lower_: 20.91
    • bb_lower_: 21.33
  • sbm_lower_bound é uma variante que usa a forma if em vez de first += comp(first[length], value) * (length + rem) para induzir o gcc a gerar movimentação condicional
  • Essa otimização pode desaparecer em uma próxima versão do gcc, então requer comentários e cuidado
  • Os comandos de benchmark usaram g++-10, clang++-10, clang++-10 -mllvm -x86-cmov-converter=false e também -march=haswell
  • -march=native ou não especificar -march não afetou muito o ranking, e os testes foram executados em um Intel i7 Kaby Lake

Medição de falhas de predição de desvio

  • Uma execução comum com clang, medida com perf, registrou cerca de 6,94 bilhões de branches e cerca de 1,20 bilhão de branch-misses, com taxa de 17,34%
  • A execução com clang -cmov registrou cerca de 4,07 bilhões de branches e cerca de 35,95 milhões de branch-misses, reduzindo a taxa para 0,88%
  • -cmov eliminou cerca de 2,9 bilhões de desvios e cerca de 1,2 bilhão de falhas de desvio
  • Os desvios removidos eram daqueles que falhavam na predição com probabilidade de cerca de 41%
  • Isso fica próximo dos 50% esperados para um desvio totalmente imprevisível

Com função de comparação lenta, o resultado muda

  • Para observar um cenário com comparação mais lenta, foi testada a busca em strings de 8 bytes
  • No tempo médio de execução (ns), std::lower_bound foi ligeiramente mais rápido ou muito próximo de sb_lower_bound
    • gcc: std::lower_ 160.01, sb_lower_ 165.66
    • clang: std::lower_ 157.71, sb_lower_ 162.68, bb_lower_ 157.22
    • clang -cmov: std::lower_ 156.06, sb_lower_ 164.71, bb_lower_ 157.48
  • Nesse caso, std::lower_bound foi de forma consistente um pouco mais rápido que sb_lower_bound
  • Uma biblioteca pode buscar o melhor desempenho usando sb_lower_bound para tipos primitivos e std::lower_bound nos demais casos

Diferenças visíveis no assembly

  • O hot loop de std::lower_bound com clang -cmov inclui movimentações condicionais como cmova e cmovbe, mas usa várias instruções para atualizar comprimento e posição
  • O hot loop de sb_lower_bound calcula metade do comprimento, o resto e o ponteiro a mover, e então atualiza first com cmova
  • O assembly de branchless_lower_bound é muito curto e limpo, mas, nos testes de desempenho, sb_lower_bound entregou resultado melhor com menor overhead

Atualização: sb_lower_bound ficou ainda mais curto

  • Após um comentário do autor de orlp.net, sb_lower_bound pôde ser refatorado para reduzir as instruções do hot loop em assembly de 9 para 8
  • O ponto central é que length - half é igual a half + length % 2
  • A forma refatorada calcula half = length / 2, faz first += length - half quando a comparação é verdadeira, e então atualiza length = half
  • Com clang -cmov, o tempo médio de execução melhorou levemente, de cerca de 33ns para cerca de 32ns

Em arrays grandes, prefetching funciona bem

  • O prefetching, sugerido nos comentários, é uma técnica para trazer antecipadamente para o cache L1/L2 os dados que serão necessários, reduzindo a latência no acesso real
  • Exemplos de latência: L1 cerca de 4 ciclos, L2 cerca de 12 ciclos, L3 cerca de 40 ciclos e memória cerca de 200 ciclos
  • Tanto gcc quanto clang suportam __builtin_prefetch()
  • Fazer prefetch da posição length / 4 desperdiça 1 em cada 2 acessos; adicionar também length / 8 faz com que 5 em cada 6 sejam desperdiçados
  • O cálculo das posições de prefetch e a própria chamada também têm overhead, e esse custo importa em um hot loop encurtado
  • Várias estratégias de prefetch não ajudaram em arrays menores que 256KB
  • Acima de 256KB, a versão sbp_lower_bound com prefetch melhorou o tempo médio de cerca de 32ns para cerca de 26ns em testes de até aproximadamente 4 milhões de entradas, ou 16MB
  • Em testes depois ampliados até cerca de 128 milhões de entradas, ou 512MB, a versão com prefetch ficou cerca de 2.3x mais rápida que std::lower_bound pelo tempo médio
    • A comparação foi de cerca de 161ns para std::lower_bound contra cerca de 71ns para a versão com prefetch

Observações em conjuntos de dados grandes e alternativas

  • Em tamanhos muito grandes, o std::lower_bound branchless gerado por clang -cmov ficou mais lento que a versão com ramificações
  • CPUs modernas podem seguir desvios previstos enquanto fazem carregamentos de memória e execução especulativa, o que pode funcionar na prática como uma forma de prefetch
  • sbpm_lower_bound é uma versão que adiciona prefetch a sbm_lower_bound e usa multiplicação booleana para induzir o gcc a gerar código branchless
  • Há saltos no gráfico de desempenho entre 1 milhão e 10 milhões de elementos, sugerindo que ainda existe espaço para uma implementação teoricamente mais rápida
  • Porém, o código com prefetch vai ficando cada vez mais complexo e cheio de constantes mágicas, e a chance de isso virar contribuição para gcc/libstdc++ ou llvm/libc++ diminui conforme a complexidade cresce
  • Uma alternativa que quebra as restrições de std::lower_bound é a Eytzinger Binary Search, que reorganiza o array de entrada em forma de heap binário por medianas para melhorar a localidade de cache
  • No teste de árvore 16-ária com inteiros apresentado por Sergey Slotin na CppCon 2022, os resultados foram de 7x a 15x mais rápidos que std::lower_bound

Código e condições de uso

  • Se a busca ou a comparação for a parte mais lenta do programa e o processador tiver dificuldade para prever o resultado das comparações, vale tentar no x86 a opção clang -mllvm -x86-cmov-converter=false
  • Se precisar de uma busca binária mais rápida, você pode testar sb_lower_bound; no gcc, sbm_lower_bound também é uma opção
  • O código é distribuído sob licença MIT
  • O código e os benchmarks estão disponíveis em github.com/mh-dm/sb_lower_bound/

Leituras relacionadas

1 comentários

 
GN⁺ 2023-08-13
Opiniões no Hacker News

  • Sempre que vejo pessoas tentando eliminar desvios, fico me perguntando se elas sabem que a estrutura em que uma falha de previsão de desvio faz uma pipeline longa parar não é um elemento essencial da arquitetura de CPU
    A razão de a pipeline ser longa é que muita análise e transformação é feita logo antes da execução, mas, como não se trata de um algoritmo com grande dependência de estado, a maior parte disso poderia ser feita de antemão
    O CPU Transmeta Crusoe funcionava desse jeito, e dá para imaginar um mundo em que não fosse preciso se preocupar com desvios
    Olhando mais a fundo, toda operação é um desvio que olha para o estado dos bits e altera o resultado, mas esses desvios locais dentro da ALU não ficam na pipeline principal, então não prejudicam muito o desempenho

    • É você, Dave? :-) Houve um artigo, tempos atrás, comparando CISC superscalar e RISC uniscalar do ponto de vista de throughput por hora e instruções por ciclo
      Lembro também de ter dito ao srk, na época, que escolher entre IPC e throughput como métrica influencia o que se considera bom ou ruim
      O lado do IPC vê que, se você criar um IPC mais alto, o processo de fabricação aumentará o clock e todo mundo ganha; já o lado do throughput adota uma abordagem mais realista, vendo que a Lei de Moore morreu, que fazer o silício rodar mais rápido o derrete, e que quem vence é quem projeta a ISA de forma inteligente
      Nos últimos 20 anos, ambos os lados tiveram sucessos e frustrações, e é interessante que hoje o RISC-V esteja voltando a essas questões em arquitetura de CPU
      Também é um bom lugar para acompanhar como ideias superscalares modernas são adicionadas com base na flexibilidade do conjunto de instruções, e, no longo prazo, acho que esse lado vai vencer
    • Isso está completamente errado
      A tradução da Transmeta não eliminava o custo dos desvios
      Fiquei com a lembrança de Linus, que trabalhava na Transmeta, dizendo em uma thread da comp.arch algo como “o trabalho da CPU é produzir cache misses o mais rápido possível”
      Cache misses obrigatórios existem, e nenhum JIT consegue eliminá-los
      No mundo real, mesmo com caches enormes como os de hoje, também não dá para evitar misses de capacidade
      O Itanium também acreditava que poderia eliminar o custo dos desvios com análise estática; basta lembrar qual foi o resultado
      Eu gostaria que programadores lessem alguns livros de arquitetura de computadores antes de concluir com tanta confiança que conseguem facilmente criar algo melhor que processadores modernos
      Acho que estão subestimando a escala do esforço intelectual colocado nos processadores atuais em pelo menos 7 dígitos
    • Mesmo que não haja estado, há muita dependência de fatores desconhecidos em tempo de compilação
      Um deles são os dados de entrada que serão processados
      A busca binária é exatamente esse caso: o compilador não sabe em qual posição o resultado será encontrado
      Outro é a microarquitetura, especialmente a hierarquia de cache e a configuração das unidades de execução
      Se a ISA for trocada por uma com instruções semelhantes às micro-operações das CPUs atuais, será preciso recompilar para cada microarquitetura
      Ainda assim, isso é tecnicamente solucionável com um JIT no sistema operacional, como nas GPUs atuais, em que programas são distribuídos em formato de bytecode (DXBC, SPIR-V, NVPTX) e o driver de GPU em modo de usuário recompila para as instruções reais do hardware
      A variável maior é que outros threads da CPU executam código que não se pode conhecer
      Mesmo eliminando o hyper-threading para tornar os núcleos independentes, ainda restam recursos compartilhados por todo o chip, como cache L3, memória externa, largura de banda de I/O, energia e dissipação de calor
    • Acho que o ponto central está na definição de desvio
      Se você redefinir tudo como Branch™, então algumas Branch™, inclusive coisas que não são desvios de verdade, podem ser pré-computadas
      Mas a eliminação de desvios, no sentido comum, não trata dos casos em que o caminho de computação realmente se divide em código como if/else?
      Mesmo nesse mundo, otimizações úteis seriam possíveis, mas ficariam limitadas a Branch™ que tentam calcular simultaneamente os resultados de vários futuros
    • Também dá para reformular o motivo de pipelines serem longas dizendo que há muito trabalho independente que pode ser feito simultaneamente dentro do processador
      Sempre que existe uma operação que pode ser executada de forma independente, surge a possibilidade de executá-la ao mesmo tempo
      Não estou falando só de decodificar, buscar e executar
      Se há uma ALU e um shifter independentes, dá para fazer um shift enquanto se faz uma soma; se há um somador e um multiplicador dedicados, não há motivo para não tentar os dois ao mesmo tempo
      Isso logo leva à vontade de manter várias instruções em andamento ao mesmo tempo, o que significa que é preciso conseguir buscar e decodificar instruções mais rápido do que a velocidade de processamento
      Também leva naturalmente à situação de querer reordenar as coisas para que N instruções Add não impeçam a visualização de um Shift independente
      Você pode achar que a estrutura atual é mais complexa do que o necessário, e pode não estar errado
      Ainda assim, há uma engenharia enorme envolvida na criação da estrutura atual; então, se você acha que seria possível torná-la muito mais rápida de outro modo, vale a pena investigar a fundo quão correta é essa afirmação

  • Na parte em que diz “quem dera houvesse uma linguagem bare-metal limpa e rápida para escrever tudo isso...”, o autor incluiu notas de rodapé “BUT RUST..” e “BUT ZIG..”, mas fico curioso sobre como seria com Nim
    Parece haver uma implementação de lowerBound na biblioteca nativa: https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
    Estritamente falando, não é uma linguagem “bare-metal”, mas como compila para C ou C++, seria interessante ver para que código ela compila aqui
    E também fico curioso sobre qual é o problema com C

  • Não sei bem se isso ainda é lower_bound
    Talvez eu tenha lido o código errado, mas parece retornar qualquer item correspondente quando há duplicatas, não a primeira correspondência
    Se a função de comparação estiver procurando um prefixo específico de string para autocompletar, então mesmo em uma lista única vários itens podem corresponder, e nesse caso você quer o primeiro item da lista

    • A cada correspondência, ele reduz o comprimento restante pela metade e só sai do loop quando o comprimento é 0, então deveria retornar o primeiro item
    • Parece bom ter uma opção mais rápida para quando você não se importa exatamente com qual item correspondente será retornado
    • Para mim, ele retorna a primeira correspondência
      Fico curioso para saber por que você acha que não

  • Queria que todos os posts de blog começassem como este: “Vocês devem estar ocupados, então vou direto ao ponto. Aqui está a implementação de busca binária em C++ mais rápida, geral e simples”

  • A biblioteca padrão do Zig não chama C++ para fazer busca binária
    A busca binária atual está aqui: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

  • Não estou entendendo bem
    O problema de busca binária e ramificações não é a ramificação em si, mas o fato de que, até terminar a comparação, você não sabe qual posição de memória buscar em seguida no array
    Não importa se você usa uma ramificação ou alguma outra coisa; no fim, a questão é o que você quer que o processador faça
    Há uma dependência de dados
    Antes de ler o índice do meio, você não sabe se vai pesquisar a metade superior ou a inferior
    Você pode especular e emitir leituras para os dois lados, e isso resolve a dependência, mas aumenta o tráfego de memória
    O ponto central é saber se esse é o trade-off certo; simplesmente remover a ramificação não é a resposta

  • No meu processador Cascade Lake, -mllvm -x86-cmov-converter=false reduz o desempenho da busca binária para quase metade
    Os números são nanossegundos por bsearch em um array de 100 MB de uint32
    O clang 15.0.7 parece ser muito pior que o gcc 13.2.1 nesta otimização específica de código
    O assembly pode ser visto aqui: https://godbolt.org/z/cbx5Kdjs6
    O assembly do gcc parece bem mais limpo

    Benchmark gcc clang clang -cmov
    slow u32 23.4 46.7 45.8
    fast u32 18.1 19.8 31.4
    • Então é só ver https://mhdm.dev/posts/sb_lower_bound/#prefetching
      100 MB é grande o suficiente para a versão com ramificações sair um pouco favorecida, não por ser melhor, mas por causa das características da execução especulativa do x86

  • Alguém sabe para onde o link “BUT RUST” deveria apontar originalmente?
    Como ele não estava fixado em uma versão, parece que já quebrou, e talvez a intenção fosse apontar para o meio do comentário de documentação de starts_with

    • Olhando as capturas do archive.org de pouco antes [1] e logo depois [2] da publicação do artigo, parece que a intenção era apontar para esta linha de código, que agora virou a linha 2779 [3]
      let mid = left + size / 2;

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

  • A intenção era linkar para a implementação de busca binária do Rust
    Foi atualizado para https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#...

  • É interessante que, com uma função de comparação comp mais complexa, o resultado não se mantém
    O artigo considerou um cenário de busca binária um tanto realista em que a função de comparação é lenta, como ao comparar ID, telefone, conta ou palavra-chave, e por isso testou a busca em strings de 8 bytes
    Nesse caso, std::lower_bound é só um pouco, mas consistentemente, mais rápido que sb_lower_bound; para obter sempre o melhor desempenho, a biblioteca poderia usar sb_lower_bound quando lida diretamente com tipos primitivos e std::lower_bound nos demais casos
    Gostaria de ver a análise aqui

    • Acredito que isso aconteça graças à predição de desvios, que permite colocar várias comparações no pipeline ao mesmo tempo e desfazê-las quando o preditor erra
      Com dados e entradas realmente aleatórios, a predição erraria cerca de metade das vezes
      A abordagem com CMOV fica bloqueada depois da função de comparação por causa da dependência de dados
      Em média, a abordagem com desvio executa duas comparações por vez, enquanto a com CMOV executa uma; portanto, quando o tempo de comparação fica maior que a penalidade de uma falha de predição de desvio, é de se esperar que surja um ponto de inversão
    • Se esse for o caso, é bem provável que exista uma versão de busca binária muito melhor para tipos primitivos
      Algo que fiz de forma aproximada com SIMD algum tempo atrás é 3 vezes mais rápido que std::lower_bound até esbarrar na largura de banda de memória: https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
    • Não encontrei nenhuma garantia sobre o conjunto de dados de entrada ou o conteúdo das chaves de busca além de dizerem que são “imprevisíveis”
      Presumo que sejam puramente aleatórios, mas, se essas strings de 8 bytes não forem informação pura, um preditor de desvios moderno pode facilmente ter desempenho melhor que cmov

  • O atributo unpredictable agora parece afetar o passe de conversão para cmov
    Como é de 1º de junho, provavelmente deve entrar no clang 17/18: https://reviews.llvm.org/D118118