Algoritmo de busca de substring adequado para SIMD (2018)

• APIs como strstr e std::string::find partem do pressuposto de uma busca pontual de substring, mas em CPUs modernas o custo de comparar strings curtas e vetores é baixo, então uma abordagem SIMD pode ser vantajosa
• A ideia central é substituir a condição de hash fraco de Karp-Rabin por um predicado vetorial e fazer a comparação exata da substring apenas nas posições candidatas
• O algoritmo SIMD genérico reduz candidatos comparando em paralelo o primeiro e o último caractere da needle, e valida com memcmp apenas as posições com possibilidade de correspondência
• As abordagens com SSE4.1 MPSADBW e SSE4.2 PCMPESTRM também são comparadas, mas os resultados mostram que o SIMD genérico é mais consistentemente rápido, e PCMPESTRM tende a ser ainda mais lento que MPSADBW
• O SIMD genérico foi mais rápido que strstr em C em todas as plataformas, mas pode ler além da string de entrada, então não é seguro, e a comparação também não é totalmente equivalente porque recebe o comprimento antecipadamente

---

Hipóteses de custo que mudaram na busca de strings

• APIs como strstr em C, std::string::find em C++ e pos, index de strings em Python foram pensadas para uma busca única de substring dentro de uma string dada
• Os algoritmos tradicionais se dividem em duas grandes categorias
  • métodos baseados em autômatos finitos determinísticos, como Knuth-Morris-Pratt e Boyer-Moore
  • métodos baseados em comparação simples, como Karp-Rabin
• Os algoritmos padrão assumem que comparar 1 par de caracteres, consultar tabelas auxiliares e fazer desvios condicionais é barato, enquanto comparar duas substrings é caro
• Em CPUs desktop modernas, essa hipótese pode não se sustentar
  • em CPUs de 64 bits, não há diferença de custo entre comparar 1, 2, 4 ou 8 bytes
  • com suporte a instruções SIMD, comparações vetoriais de 16, 32 ou 64 bytes podem ser tão baratas quanto comparar um único byte
  • consultas a tabelas têm custo de acesso à memória comparável a uma ida e volta no cache L1, e leituras por caractere têm custo semelhante
  • desvios mal previstos podem impor uma penalidade de cerca de 10~20 ciclos
  • uma cadeia curta de dependências entre leitura de caractere, comparação e desvio condicional dificulta o aproveitamento da execução out-of-order da CPU

Abordagem: usar predicados vetoriais no lugar de hash fraco

• Karp-Rabin só faz a comparação exata quando o hash fraco da substring procurada bate com o hash do trecho atual da string
• A abordagem SIMD substitui essa condição de hash por um predicado vetorial
  • o predicado é calculado em paralelo
  • a comparação exata da substring só é feita nas posições onde o vetor de predicados é verdadeiro
• A especialização por comprimento também é usada para melhorar o desempenho
  • uma implementação genérica chama uma função como memcmp para comparar substrings
  • quando o comprimento da substring de busca é conhecido, essa chamada pode ser substituída por algumas instruções de CPU, às vezes até por uma única instrução, ajustada àquele comprimento específico
  • isso reduz tanto o custo da chamada de função quanto o custo interno de memcmp

Algoritmo 1: SIMD genérico

• O algoritmo SIMD genérico se aplica a vários conjuntos de instruções SIMD e também à abordagem SWAR
• O predicado básico verifica se o primeiro caractere e o último caractere da needle coincidem ao mesmo tempo
  • o primeiro caractere é preenchido no registrador F
  • o último caractere é preenchido no registrador L
  • em cada iteração, o chunk A é lido no offset atual i da haystack, e o chunk B em i + k - 1
  • calcula-se F == A e B == L, depois os dois resultados são combinados para formar uma máscara de posições candidatas
  • a comparação exata da substring só é feita onde a máscara é verdadeira
• No exemplo de busca de "cat" em "a_cat_tries", apenas a posição de índice 2 tem correspondência simultânea do primeiro c e do último t, então a comparação exata é executada só uma vez
• Escolher sempre o primeiro e o último caractere nem sempre é ideal
  • se a string de entrada for quase toda 'A' e a needle for "AjohndoeA", muitos candidatos podem surgir
  • a implementação pode escolher, em vez do último caractere, o caractere mais distante que seja diferente do primeiro
  • se todos os caracteres da needle forem iguais, pode-se usar um procedimento especial para padrões como "AAAAA"

Diferenças entre implementações

• As implementações em SSE e AVX2 têm estrutura quase idêntica e usam o número mínimo de instruções
  • como já se sabe que o primeiro e o último caractere coincidem, memcmp não precisa compará-los de novo
• A abordagem SWAR explora o fato de que, se o resultado do XOR é 0, os bytes são iguais
  • em vez de fazer AND dos resultados parciais como em SSE/AVX2, usa OR
  • encontrar as posições de byte zero exige mais trabalho
  • na implementação em C++ para vetores de 64 bits, calcula-se a máscara exata de bytes
• O AVX512F não tem operações por byte e seu menor elemento vetorial é uma palavra de 32 bits, então exige a técnica SWAR
  • dois XORs e um OR são calculados com instruções AVX512F
  • procuram-se os elementos que contêm bytes zero dentro de cada elemento de 32 bits
  • para cada elemento de 32 bits correspondente, verificam-se 4 substrings candidatas
• A implementação ARM Neon de 32 bits usa registradores SIMD de 128 bits
  • o gargalo é a longa ida e volta entre a unidade Neon e a CPU
  • os resultados das comparações são gravados na memória como palavras de 64 bits para processamento
  • desenrolar 2 loops internos dá um ganho de cerca de 1,2x
• A implementação AArch64 é quase igual ao procedimento ARM Neon, mas ler diretamente as lanes dos registradores SIMD é rápido

Algoritmo 2: SSE4.1 MPSADBW

• Em SSE4.1 e AVX2, MPSADBW calcula a distância Manhattan entre um subvator de 4 bytes de um registrador e 8 subvectores contíguos de 4 bytes de outro registrador
• Quando dois subvectores são iguais, a distância L1 é 0, então isso pode ser usado para encontrar posições candidatas
  • nessa abordagem, o predicado é a igualdade dos 4 primeiros caracteres
• Comparar os 4 primeiros caracteres parece mais forte que comparar o primeiro e o último, mas ainda não evita complexidade quadrática no pior caso
  • se a haystack for cheia de "a" e a needle for "aaaabcde", o predicado será verdadeiro para todos os caracteres da entrada
• A abordagem com MPSADBW tem algumas limitações
  • em princípio, ela não se ajusta bem a substrings com menos de 4 caracteres
  • é possível tratar comprimento 3, mas com código adicional
  • MPSADBW em SSE processa apenas 8 bytes por vez
  • MPSADBW em AVX2 opera por lanes de 128 bits, não no vetor completo de 256 bits, então exige código extra de carregamento
  • a latência da instrução é alta, cerca de 5~7 ciclos dependendo da CPU, mas o throughput é de 1~2 ciclos, então o desenrolamento do loop pode esconder a latência
• O AVX512F não tem MPSADBW, mas como elementos de 32 bits são suportados nativamente, dá para imitar o predicado de igualdade do prefixo de 4 bytes
  • em cada iteração, são criados 4 vetores AVX512 com os possíveis prefixos de 4 bytes
  • montar cada vetor exige 2 shifts e 1 OR
  • o loop de comparação fica mais complexo, e são necessários 4 bytes além do fim do vetor para preencher o último elemento

Algoritmo 3: SSE4.2 PCMPESTRM

• O SSE4.2 introduziu o conjunto de instruções STNI, pensado como bloco de construção para operações com strings
• A Intel praticamente abandonou o STNI em processadores posteriores, não introduziu uma versão AVX2, e essas instruções são muito lentas
  • uma latência de 11 ciclos é considerada difícil de aceitar
• As instruções PCMPxSTRx têm quatro variantes, conforme a forma de determinar o comprimento da string e a forma de armazenar o resultado
  • o comprimento pode ser dado explicitamente, ou a primeira ocorrência de byte 0 pode ser tratada como fim da string, como em strings C tradicionais
  • o resultado pode ser armazenado como máscara de bits/bytes ou como o número do primeiro/último bit ativo da máscara
• Aqui é usado o modo de comparação range ordered
  • apesar do nome, quando a substring ou o registrador termina, ele encontra o prefixo correspondente
  • no exemplo de busca de "ABCD" em "ABCD_ABC_ABCD_AB", o sufixo "AB" também pode ser tratado como correspondência
  • por isso, a única suposição segura é a de igualdade do primeiro caractere, e o restante precisa ser verificado com memcmp

Ambiente de medição de desempenho

• O desempenho de várias implementações SIMD foi medido, incluindo especialização em tempo de execução para substrings curtas
• strstr em C foi incluído como referência, mas nas tabelas x64 std::string::find foi omitido por causa de um bug de desempenho na GNU libc
• Cada programa de teste foi executado três vezes
• Ambiente de teste x64
  • Westmere i5 M540, GCC 6.2.0
  • Bulldozer FX-8150, GCC 4.8.4
  • Haswell i7 4470, GCC 5.4.1
  • Skylake i7 6700, GCC 5.4.1
  • Knights Landing 7210, GCC 5.3.0
• Ambiente de teste ARM
  • ARMv7 Raspberry Pi 3, código de 32 bits, GCC 4.9.2
  • ARMv8 ARM Cortex A57 / AMD Opteron A1100, código de 64 bits, Clang 3.8.0

Resultados em x64

• A implementação SIMD genérica mostrou o maior ganho de velocidade em relação a strstr no x64
  • no Westmere, SSE2 generic levou 0.74589 s, enquanto strstr levou 0.82246 s
  • no Haswell, AVX2 generic levou 0.38653 s, enquanto strstr levou 0.52786 s
  • no Skylake, AVX2 generic levou 0.36309 s, enquanto strstr levou 0.66148 s
  • no KNL, AVX512F generic levou 1.14057 s, enquanto strstr levou 4.94606 s
• O ganho máximo foi de 1,10x no Westmere, 1,37x no Haswell, 1,82x no Skylake e 4,33x no KNL
• O desempenho de strstr no Bulldozer, com 9.37792 s, foi tão ruim que não serve bem como referência
• A abordagem com MPSADBW teve desempenho fraco no geral, exceto no Skylake, e foi particularmente ruim no KNL
• A abordagem com PCMPESTRM foi ainda mais lenta que MPSADBW

Resultados em ARM

• No ARMv7, std::strstr levou 7.30405 s e std::string::find levou 4.17131 s
• No ARMv7, o ARM Neon 32-bit generic levou 1.29861 s, até 3,1x mais rápido que std::string::find
• No ARMv8, std::strstr levou 3.37546 s e std::string::find levou 1.81368 s
• No ARMv8, o AArch64 64-bit generic levou 0.27897 s, até 6,5x mais rápido que std::string::find
• No ARMv8, o SWAR 64-bit generic levou 0.46269 s, com desempenho próximo ao procedimento SIMD de 32 bits

Conclusão e limitações

• O algoritmo SIMD genérico foi mais rápido que strstr em C em todas as plataformas
• Na implementação, é melhor escolher a versão SIMD mais alta disponível para a CPU específica
• MPSADBW teve desempenho fraco, com exceção do Skylake, e foi muito ruim no Knights Landing
• PCMPESTRM teve desempenho inferior ao de MPSADBW
• O desempenho do ARM Neon foi bom, incluindo a implementação SWAR
  • a versão SWAR foi 1,7x mais rápida que string::find
  • a versão SIMD foi 3,1x mais rápida que string::find
• A comparação com strstr pode não ser totalmente justa
  • strstr processa strings cujo comprimento é desconhecido
  • estas implementações recebem o comprimento como argumento e tiram proveito disso
• A implementação não é segura
  • ela pode ler dados além da string de entrada
  • se a string estiver logo antes de uma região de memória não mapeada, pode ocorrer violação de acesso
  • o AddressSanitizer também pode relatar o problema
  • seria possível torná-la segura, mas esse não era o objetivo
• Todas as implementações e programas de teste estão no GitHub