Algoritmo de busca de substring adequado para SIMD (2018)

• Trata-se de um tema sobre um algoritmo de busca de substring compatível com SIMD
• Apresenta uma abordagem técnica para busca rápida de strings
• Mostra um caminho para melhorar a eficiência em relação aos métodos existentes por meio de processamento paralelo
• Chama atenção como uma dica de desempenho útil para desenvolvedores e profissionais de TI
• O algoritmo tem relação com a otimização para hardware moderno

---

Visão geral

• Este documento apresenta um algoritmo de busca de substring otimizado para o conjunto de instruções SIMD (Single Instruction, Multiple Data)
• No ambiente atual de TI, em que a velocidade de processamento de strings se tornou importante, ele aborda uma forma de processamento paralelo para complementar as limitações dos métodos tradicionais de busca sequencial
• Com SIMD, é possível comparar vários dados ao mesmo tempo em uma única operação, o que pode trazer ganhos importantes de desempenho em buscas de strings em grande volume

Principais pontos

• O algoritmo SIMD divide a string de entrada em várias partes e compara vários bytes de uma vez com a mesma instrução
• Com essa abordagem, é possível fazer uma busca mais rápida e eficiente do que com a comparação tradicional baseada em laços de repetição
• Ele é particularmente útil em áreas que exigem processamento rápido de grandes volumes de dados, como busca em texto, análise de logs e sequenciamento de DNA

Benefícios para desenvolvedores e engenheiros

• Ao aplicar um algoritmo compatível com SIMD, é possível maximizar o potencial das CPUs modernas com mudanças mínimas no código
• Oferece vantagens em velocidade e eficiência em relação à lógica de busca tradicional
• Também apresenta excelente escalabilidade de desempenho em ambientes multicore

Conclusão

• Em áreas como serviços de TI, análise de dados e mecanismos de busca em tempo real, onde o desempenho da busca de substring é importante, a adoção de um algoritmo baseado em SIMD pode levar a melhorias reais de desempenho
• Trata-se de uma estratégia essencial de otimização para aproveitar ambientes de hardware modernos

[GN⁺]

Comentários no Hacker News

• Explicação de que a forma de aceleração do ripgrep é uma abordagem AVX2 (genérica) usando a crate regex do Rust. Enfatiza que até uma expressão regular como \w+\s+Sherlock\s+\w+ pode ser pesquisada rapidamente extraindo apenas Sherlock. A implementação real pode ser vista aqui. Menciona que a principal diferença em relação ao algoritmo deste texto é o uso de uma heurística que otimiza a busca com 2 bytes menos frequentes com base na distribuição de fundo, em vez do primeiro/último byte da needle. Os resultados de benchmark mostram desempenho muito superior ao simples Two-Way ou ao memmem da GNU libc. Também destaca uma limitação de API no benchmark prebuilt: rotinas do tipo memmem perdem eficiência porque precisam reconstruir repetidamente o estado sempre que a needle fixa muda

  • Questionamento sobre como se conhece a distribuição de fundo dos bytes, e observação de que escanear essa distribuição no haystack poderia, ao contrário, prejudicar o desempenho

• Compartilhamento de experiência implementando esse tipo de algoritmo de busca de strings ao tentar otimizações SIMD para a libc de Wasm/WASI. Opinião de que, quando o comprimento do haystack é conhecido e a needle é grande o suficiente, combiná-lo com Quick Search é útil, junto com código relacionado e um link com a explicação do algoritmo

• Compartilhamento de que o C# também aplica SIMD em IndexOf, com mais detalhes aqui

• Apresentação da experiência de também ter implementado pessoalmente vários algoritmos usando SIMD para busca de strings e split. Divulgação do fonte conversion.cxx do tamgu. Afirma que usou um algoritmo diferente do mencionado no texto principal

  • Pedido para resumir brevemente o próprio algoritmo. Como exemplo, acrescenta a explicação de que o algoritmo 1 do texto original usa o primeiro/último caractere, enquanto o algoritmo 2 compara simultaneamente os 4 primeiros caracteres e verifica várias posições candidatas

  • Compartilhamento de que, alguns anos atrás, tentou implementar uma versão modificada usando SIMD genérico do Zig para busca de janela do LZ77. Mais detalhes aqui

• Comentário de que isso faz lembrar o projeto hparse, que usa algoritmos SIMD para parsing rápido de HTTP

• Menção de que o algoritmo SWAR gera UB (comportamento indefinido) ao fazer cast de dados alinhados em 1 byte para unidades de 8 bytes. Também aponta que cargas desalinhadas podem causar problemas de desempenho

  • Opinião de que esse tipo de código costuma ser entendido como algoritmo idealizado ou pseudocódigo voltado à legibilidade. Aponta que não usa memcpy e que a verificação de limites é imprecisa. Há três UBs: assumir que o comprimento do haystack é múltiplo de 8, causar out-of-bounds por overflow de inteiro sem sinal quando a needle está vazia etc. Compartilha a experiência de que, em muitos códigos de demonstração com SIMD, costuma-se mostrar apenas o uso interessante de vetores e omitir as condições de contorno

• Reforço de que já é sabido que o strstr da libc é lento, mas que o musl é rápido e usa um algoritmo moderno. Agora só falta dar um nome para incluí-lo no smart shootout. Curiosidade sobre como ele se compararia aos melhores algoritmos SIMD

  • Apresentação, como benchmark de referência, de resultados comparando o Two-Way do musl com o algoritmo de libc otimizado com SIMD que a pessoa compartilhou. O método de benchmark foi baseado neste código. As melhorias com uso de SIMD podem ser vistas nesta tabela. Avalia honestamente que não é algo extraordinário, mas uma melhoria bem razoável. Menciona que o musl é especializado em strings de comprimento fixo (memmem), enquanto no ambiente Wasm foi possível tentar livremente várias otimizações para strings de comprimento desconhecido (strstr). Strings terminadas em NUL acabam dificultando vários bons algoritmos

  • Comentário de que seria bom se o smart incluísse mais algoritmos SIMD, e expressão de vontade pessoal de experimentar isso quando houver tempo

• Pergunta se a versão de 2018 não ficou de fora na comparação de SIMD para busca de strings

• Pergunta sobre qual é, na prática, o limiar em que abordagens SIMD passam a ser eficientes dependendo do tamanho da string. Enfatiza que, em strings pequenas, o overhead de configuração do SIMD (alinhamento, cálculo de comprimento etc.) pode acabar sendo pior do que uma busca simples baseada em bytes. Observa que isso pode variar bastante conforme a arquitetura de hardware

  • Comentário de que, pela própria experiência, acontece mais o contrário. Esses algoritmos são quase brute force e praticamente não exigem configuração extra, então a complexidade de tempo piora com needles longas e repetitivas. Já algoritmos avançados de busca de strings, que evitam problemas quadráticos ou executam de forma sublinear, exigem uma configuração cara para analisar com mais profundidade a estrutura da needle

• Desejo de que fosse possível usar SIMD diretamente em Python, sem chamar outra linguagem

  • Menção ao blog do Austin e a uma coletânea dele (story on vowels detection link), perguntando mais concretamente o que significa “usar SIMD diretamente sem chamar outra linguagem”. Brinca que Assembly, no fim das contas, também é “outra linguagem”... Explica que o ecossistema relacionado a Python e SIMD é bastante amplo, incluindo PeachPy (escrever assembly x86 em Python), Mojo (uma nova linguagem no estilo Python) e bibliotecas SIMD com bindings finos para CPython. Pergunta que abordagem a pessoa quer especificamente e, se o alvo for ASCII, também recomenda a função find_first_of do StringZilla (código)

  • Questionamento sobre por que insistir em fazer isso diretamente em Python. Se a preocupação for com limites de desempenho, aconselha que apenas mudar de linguagem já pode trazer ganhos de 20 a 50 vezes ou mais