A busca binária branchless mais rápida

• Este artigo discute uma implementação genérica de busca binária em C++ que é duas vezes mais rápida e mais curta que a função padrão std::lower_bound.
• A nova implementação é "sem desvios" porque é compilada usando instruções de movimento condicional em vez de desvios/saltos condicionais.
• A busca binária funciona dividindo uma lista ordenada em duas partes no item do meio e comparando o valor central com um valor fornecido. Dependendo do resultado da comparação, decide-se em qual das duas sublistas continuar procurando.
• O artigo também discute o conceito de predição de desvios, uma técnica em que o processador executa instruções em paralelo para acelerar a execução. No entanto, como a busca binária é imprevisível, a predição de desvios não é ideal.
• O autor apresenta sb_lower_bound, uma nova implementação de busca binária mais rápida que a implementação padrão e que a versão branchless_lower_bound. Ela é mais rápida porque há muito menos instruções dentro do loop.
• O autor também apresenta bb_lower_bound, uma versão ainda mais rápida que usa outro método para particionar a lista de busca.
• O artigo termina com a sugestão de que, se a parte mais lenta do seu programa envolve buscas e/ou comparações que o processador não consegue prever, vale tentar usar o clang com -mllvm -x86-cmov-converter=false. Se você precisar de uma busca binária mais rápida, experimente sb_lower_bound.
• O autor também fornece o código das novas implementações de busca binária e discute detalhadamente o desempenho de cada uma.
• O artigo foi atualizado com uma versão refatorada de sb_lower_bound, reduzindo o número de instruções de assembly no loop crítico de 9 para 8, o que trouxe uma pequena melhora de velocidade.
• O autor também discute o conceito de prefetching, que consiste em trazer partes específicas da memória para o cache para que, quando os dados pré-buscados forem realmente necessários, haja apenas a latência do cache L1/L2. Também é fornecida uma versão de sb_lower_bound com prefetching adicionado para 256 KB+.
• O artigo foi escrito por Mihail Dumitrescu e publicado em 24 de junho de 2023.

[GN⁺]

Opiniões no Hacker News

• O artigo discute o conceito e os potenciais benefícios da busca binária sem ramificações.
• Um comentário questiona a necessidade de eliminar ramificações, sugerindo que a paralisação do pipeline causada por falhas na previsão de ramificações não é uma parte intrínseca da arquitetura.
• O comentário explica ainda que toda operação é essencialmente uma ramificação, e que o motivo de essas ramificações não prejudicarem o desempenho é que não são ramificações no pipeline principal.
• Outro comentário sugere o uso da linguagem Nim, compilada para uma linguagem "bare-metal", para implementar lowerBound.
• Há uma discussão sobre se o código retorna a primeira correspondência ou apenas alguma correspondência, destacando a importância de entender a funcionalidade do código.
• Um comentário elogia a introdução intuitiva da postagem do blog, que rapidamente apresenta a implementação em C++ mais rápida de busca binária genérica.
• Um comentário aponta que a stdlib do Zig não chama C++ para busca binária e fornece um link para a busca binária na stdlib do Zig.
• Há uma discussão sobre busca binária e o problema das ramificações, sugerindo que o problema não são as ramificações em si, mas a dependência de dados gerada por não se saber qual será a próxima posição de memória a ser buscada até que a comparação seja concluída.
• Um comentário compartilha resultados de desempenho de busca binária em processadores Cascade Lake, sugerindo que o clang é pior que o gcc para otimizar esse código específico.
• Um comentário questiona o destino do link "BUT RUST", dizendo que ele parece estar desatualizado.
• Um comentário observa que os resultados não se mantêm com funções de comparação mais complexas, sugerindo que o melhor desempenho pode ser alcançado usando sb_lower_bound para tipos primitivos e std::lower_bound nos demais casos.
• Por fim, um comentário menciona que a propriedade de imprevisibilidade agora afeta o passe de conversão para cmov e fornece um link para mais informações.