Função tolower() implementada com AVX-512

• Um experimento que processa, com AVX-512-BW, 64 bytes por vez a tarefa de copiar uma string e converter letras ASCII maiúsculas em minúsculas, extraindo desempenho SIMD mesmo em strings pequenas
• O ponto central da implementação é comparar se cada byte está entre 'A' e 'Z' e então usar uma operação com máscara que soma 'a' - 'A' apenas nessas posições
• Strings curtas e a cauda restante de strings longas são tratadas com load/store mascarados, reduzindo o custo de lidar com pequenos fragmentos que códigos SIMD costumam enfrentar
• Em medições de uma cópia de cerca de 1 MiB em chunks de 1 byte a 1 KiB, com Clang 16, Debian 11 e AMD Ryzen 9 7950X, tolower64 ficou consistentemente entre os mais rápidos dos comparados
• No Zen 4, o AVX-512-BW se mostrou bem adequado a processamento de strings, mas ARM SVE e RISC-V Vector extension não foram verificados diretamente em detalhes

---

Criando um tolower() de 64 bytes com AVX-512-BW

• O objetivo é implementar em SIMD um kernel tolower() que copia uma string enquanto converte caracteres ASCII maiúsculos em minúsculos
• AVX-512-BW é uma extensão que oferece operações em unidades de byte e word, disponível em processadores AMD Zen recentes
  • O AVX-512 é dividido em várias extensões, o que torna o suporte complexo
  • O suporte no lado da Intel é avaliado como especialmente irregular
• O ARM SVE também oferece load/store mascarados em nível de byte, adequados para processamento de strings
  • Está disponível em núcleos big-ARM Neoverse recentes, como no Amazon Graviton
  • Não está disponível no Apple Silicon
• A RISC-V Vector extension segue um estilo semelhante ao ARM SVE e está disponível em vários computadores pequenos de placa única

Como o tolower64() funciona

• tolower64() é um kernel baseado em AVX-512 que processa 64 bytes por vez
• Primeiro, registradores vetoriais são preenchidos com valores de referência contendo 64 bytes
  • 'A'
  • 'Z'
  • 'a' - 'A'
• O vetor de caracteres de entrada c é comparado com 'A' e 'Z', criando duas máscaras de 64 bits
  • posições em que c >= 'A'
  • posições em que c <= 'Z'
• As duas máscaras são combinadas com _kand_mask64() para criar a máscara is_upper, que marca apenas as posições com letras maiúsculas
• Por fim, aplica-se _mm512_mask_add_epi8()
  • bytes em que is_upper é false mantêm o valor original de c
  • bytes em que is_upper é true passam a ser c + ('a' - 'A')

Tratamento de strings longas e curtas

• A maior parte das strings longas é tratada com load/store vetoriais não alinhados comuns
  • _mm512_loadu_epi8()
  • tolower64()
  • _mm512_storeu_epi8()
• Para strings curtas e o último fragmento restante de strings longas, são usados load/store não alinhados mascarados
• A máscara é criada com apenas os len bits menos significativos ativados
  • uint64_t len_bits = (~0ULL) >> (64 - len)
  • ela é colocada em um registrador de máscara SIMD com _cvtu64_mask64(len_bits)
• _mm512_maskz_loadu_epi8() preenche com 0 o registrador de destino nas posições em que a máscara está desativada
• _mm512_mask_storeu_epi8() armazena apenas as posições em que a máscara está ativada
• Essa abordagem é o ponto central para processar rapidamente pequenos fragmentos de strings

Condições do benchmark e itens comparados

• O benchmark foi executado com Clang 16, Debian 11 e AMD Ryzen 9 7950X
• O alvo medido foi uma cópia de cerca de 1 MiB, variando o tamanho dos chunks de 1 byte a 1 KiB
• Para refletir diferenças de alinhamento entre as strings de origem e destino, alguns bytes foram colocados entre cada string, e esses bytes não foram incluídos no volume medido de 1 MiB
• Como o cache L2 do Ryzen 9 7950X é de 1 MiB por núcleo, esperava-se que cada execução de teste avançasse até o cache L3
• Cada função foi compilada separadamente para evitar interferência de inlining e movimentação de código
  • Em código real, é mais provável incentivar o inlining do que impedi-lo

Resultado: desempenho suave do tolower64

• O tolower64, em rosa, fica de modo geral consistentemente próximo do grupo mais rápido entre as funções testadas
  • Há uma pequena queda quando o tamanho chega a 65 bytes e passa para o segundo vetor
  • Ele sobe rapidamente e não apresenta vales profundos de desempenho, mostrando que load/store mascarados são eficazes para lidar com pequenos fragmentos de strings
• O copybytes64, em verde, é uma versão de memcpy que usa AVX-512 de maneira semelhante
  • Não é muito mais rápido que tolower64
  • Como o Clang moderno reconhece o significado dessa função e a reescreve completamente, ela foi compilada com Clang 11
• O copybytes1, em laranja, é uma versão byte a byte de memcpy
  • Compilada com Clang 11
  • Mostra que as heurísticas de autovetorização do Clang 11 são relativamente ruins para fragmentos de strings menores que 256 bytes
• O tolower, em vermelho, é a linha de base que chama o tolower() padrão de <ctype.h>, e é muito lenta
• O tolower1, em roxo, é um tolower() byte a byte compilado com Clang 16
  • A autovetorização do Clang 16 ficou muito melhor que a do Clang 11
  • É mais lento que a versão escrita à mão e gera um código muito mais complexo
  • O tratamento de pequenos fragmentos de strings não é tão bom quanto o do tolower64, fazendo o gráfico de desempenho oscilar de forma pontiaguda
• O tolower8, em marrom, é o tolower() SWAR do artigo anterior
  • O Clang tenta autovetorizá-lo, mas a função é complexa e o resultado não é bom
  • Embora tenha sido compilado com Clang 16, aparece o abismo de desempenho em 256 bytes no estilo do Clang 11
• O memcpy, em azul, chama o memcpy da glibc
  • É rápido no início, mas há uma faixa em que cai para cerca de metade da velocidade do copybytes64
  • A causa não foi identificada

Conclusão e código

• AVX-512-BW é muito adequado para lidar com strings, especialmente strings curtas
• No Zen 4, ele é muito rápido, e as funções intrínsecas também são relativamente fáceis de usar
• A característica mais marcante é o desempenho suave
  • Quase não aparecem os vales de desempenho que a autovetorização sofre ao alternar para código escalar em pequenos fragmentos de strings
• Não foi possível investigar em detalhe ARM SVE e RISC-V Vector extension por falta de acesso conveniente a equipamentos com suporte a essas duas extensões
• O código pode ser visto no repositório git do site

[GN⁺]

Opiniões no Hacker News

• O truque do “unsafe read beyond of death” é considerado comportamento indefinido nos modelos de memória do Rust e do LLVM, mesmo que seja permitido pelo hardware
  Como em outros comportamentos indefinidos, o compilador pode assumir durante a otimização que “isso não acontece”, o que pode gerar resultados inesperados; para contornar, é preciso usar assembly inline
  https://github.com/ogxd/gxhash/issues/82

  • Seria bom haver uma opção que não fosse assembly para esses casos
    Um tipo de load como “valores além da região alocada são lidos como elementos não especificados, e só é comportamento indefinido quando o hardware não gostar” não parece difícil de suportar, e bastaria que internamente fosse um alias dessa chamada em assembly
    Indo além, seria bom se houvesse pelo menos uns 64 bytes de endereço sem fault garantidos depois de toda alocação, seja malloc, pilha, constantes etc., mas isso exigiria cooperação de vários componentes e seria bem mais complexo
    Em um alocador customizado isso é trivial, mas nesse caso fica difícil usar código SIMD em dados fora do heap customizado, e você acaba preso a uma chance minúscula de segfault
    Sanitizers e Valgrind continuariam úteis, porque valores fora dos limites poderiam ser rastreados como valores indefinidos e gerar erro quando realmente usados
  • Mesmo no nível de hardware, fico em dúvida se isso é realmente verdade
    Tenho curiosidade sobre o que acontece ao ler uma página não mapeada ou memória protegida, e, como não vi o código, não sei se as garantias de alinhamento evitam isso
  • A explicação de que “se é comportamento indefinido, o compilador pode assumir que isso não acontece” está errada
    Comportamento indefinido é um termo técnico do padrão C, então a própria generalização é estranha; o ANSI C não permite explicitamente essa suposição, e o ISO C, embora seja mais aberto, também não justifica especificamente essa suposição
    Vejo explicações do tipo “UB = pode assumir que não pode acontecer” como uma espécie de alarmismo bastante desonesto

• Vendo o código limpo e performático do texto, fico curioso sobre como a implementação de AVX512 da AMD vai competir com o AVX10 planejado pela Intel
  O ponto central do AVX10 parece estar em resolver a situação dos P-cores/E-cores da Intel, enquanto a AMD parece ter escolhido uma abordagem melhor, mantendo a API fluida enquanto usa, conforme o caso, a implementação de largura total do Zen 5 ou o processamento em duas passagens de 256 bits no Zen 4 e no Zen 5 mobile
  Os grandes ganhos de desempenho do texto também vieram todos de núcleos Zen 4, e o AVX512 tem muitas vantagens; por isso é frustrante que a Intel o tenha restringido demais como segmentação de mercado, praticamente impedindo sua adoção em código cliente de uso geral

  • Se a Intel realmente colocar AVX10/256 em todas as CPUs que lançar daqui para a frente, ela acabará vencendo pela disponibilidade
    O mercado tem rejeitado repetidamente bifurcar caminhos de código por CPU, e, na prática, as implementações SIMD importantes miram o menor denominador comum
    AVX10.1/256 e AVX512VL têm um subconjunto em comum; então, depois de tempo suficiente, quando a maioria das CPUs der suporte a ele, as pessoas passarão a mirar essa parte
    A AMD continuará obtendo vitórias fáceis em alguns apps de benchmark atualizados para dar suporte a AVX512, mas, se a Intel mantiver o plano do AVX10, é provável que a AMD também acabe usando amplamente pipelines SIMD de duas passagens para dar suporte eficiente a AVX10/256, preservando a compatibilidade com AVX512
    A Intel tomou muitas decisões ruins na última década, mas fragmentar o mercado pelo conjunto de instruções foi uma das piores. Foi como matar por conta própria o impulso e o interesse pelas inovações recentes; recursos como operações com máscara são muito mais importantes que a largura em si, então espero que coloquem AVX10/256 em toda a linha
  • A implementação de AVX512 do Zen 4 não é double-pumped, e jornalistas de tecnologia deveriam parar de chamá-la assim
    Esse termo tem um significado específico, que não corresponde ao funcionamento real
    O Zen 4 apenas decodifica operações sobre registradores ZMM em várias micro-operações e as agenda em unidades de 256 bits livres, enquanto shuffles de largura total de 512 bits recebem tratamento especial em hardware dedicado para evitar emulação cara
    Por isso, mesmo tendo 4 unidades SIMD de 256 bits, o Zen 4 se comporta como um núcleo 2×512 bits poderoso; essa implementação de forma alguma é barata e possivelmente é a melhor forma já vista até agora em hardware de consumo
  • Não entendo por que a Intel não resolve esse problema colocando AVX512 de duas passagens nos E-cores. Ou então poderia fazer CPUs só com P-cores para desktop, como deveria ser desde o início
    Já houve anos para corrigir isso, e é irritante que, mesmo com a AMD dando suporte, a adoção não aconteça por causa da participação de mercado; infelizmente, o AVX10 parece que vai permitir à Intel segurar o mundo por mais tempo
    No desktop, eu gostaria de ver núcleos melhores, mais núcleos e um conjunto de instruções bem padronizado que abra recursos úteis como SIMD largo, float16 e gather/scatter; a AMD está fazendo isso razoavelmente bem
    Já a Intel coloca núcleos fracos ao lado de núcleos bons, limita os núcleos bons para acomodar os fracos, lança CPUs com a mesma contagem de núcleos por várias gerações, faz parecer que há muitos núcleos usando núcleos fracos, cria tantas variantes de instruções que fica difícil surgir um conjunto comum útil, e ainda abandona o suporte a instruções que ela mesma parecia ter prometido
    Minha preferência por fabricantes de desktop foi Intel nos anos 90, AMD no início dos anos 2000, Intel no fim dos anos 2000 e nos anos 2010, e agora AMD de novo. Fico curioso para saber o que a Intel fará para recuperar uma base que não seja atrapalhar a concorrente, e a competição precisa continuar para que um lado não fique acomodado demais

• Material interessante para ver por diversão: http://www.unicode.org/Public/3.1-Update1/CaseFolding-4.txt

  • Também existe isso: se converter o ß do alemão para maiúsculas, o comprimento da string muda
    Por exemplo, "straße".upper() vira 'STRASSE'
    Além disso, se você não especificar a localidade, ao fazer a conversão ida e volta para maiúsculas/minúsculas do i sem ponto das línguas turcomanas, 'ı'.upper().lower() vira 'i', quebrando o resultado
  • Felizmente, este código veio de um trabalho com DNS, então é somente ASCII e não precisa lidar com essa complexidade
    Existem vários protocolos ASCII case-insensitive, e eles aparecem com frequência nos hot paths de muitos servidores
  • Strings usadas internamente como IDs e texto digitado por pessoas são coisas diferentes
    Para as primeiras, em geral basta usar ASCII puro em uma codificação de 8 bits, mas para o segundo a coisa fica complexa
    Um endereço DNS é um exemplo simples: tecnicamente ele pode conter quase qualquer Unicode, mas para a resolução DNS de fato ele é convertido para um subconjunto ASCII muito restrito, e esse processo de resolução não diferencia maiúsculas de minúsculas
    Claro, também existem linguagens de programação que dão suporte a todos os sistemas de escrita do Unicode e ainda têm identificadores case-insensitive. Se você está lidando com isso, meus pêsames
  • Em relação ao exemplo em que o alemão maße vira MASSE, o alemão também tem o Eszett maiúsculo, ẞ
    Ele ainda não é amplamente distribuído e há poucas fontes que o suportam, mas, em teoria, agora existe

• Acho que a explicação de “adição de máscara” no texto talvez esteja errada
  Não seria o caso de somar quando is_upper é false e copiar sem alteração quando é true?

  • Ah, percebi tarde demais que o nome da variável to_upper está invertido e deveria se chamar to_lower
    Obrigado por apontar a parte confusa; corrigi o texto e o código
  • Essa operação é tolower
    O A maiúsculo é 0x40 e a minúscula é 0x60, então a adição de 0x20 deve acontecer quando is_upper é true

• Essas otimizações SWAR muitas vezes só são úteis quando a string está alinhada a um endereço de 8 bytes
  Ao aplicar um algoritmo SWAR a uma string desalinhada, é comum ele ficar mais lento que o algoritmo original
  Se você dividir em três etapas — processar o início até um endereço alinhado, processar o corpo alinhado e processar a cauda com menos de 8 bytes — acaba gerando mais instruções
  Há um caso parecido com a alegação incorreta de que utf8.IsValid é mais rápido em Go, além de benchmarks, aqui: https://github.com/sugawarayuuta/charcoal/pull/1

  • As operações SIMD com máscara do AVX-512 e do ARM SVE surgiram para resolver esse problema
    As operações de memória são sempre alinhadas e do tamanho completo do vetor, mas é possível aplicar máscara apenas aos elementos válidos
    Mesmo que uma operação de memória vetorial mascarada esteja desalinhada e atravesse uma página não mapeada ou protegida, se a respectiva lane estiver desativada pela máscara, não ocorre fault
    Para operações como strlen(), em que o comprimento não é conhecido de antemão, também há uma instrução especial de load que reduz o comprimento do vetor imediatamente antes do primeiro elemento que causaria fault

• Adição com máscara parece elegante. Seria ótimo se os intrinsics do .NET permitissem manipular diretamente os registradores de máscara do AVX512, mas por enquanto é preciso depender de “idiomas reconhecidos”
  Analisando o loop central gerado pelo GCC com uiCA(CQA/MAQAO) no Ice Lake, dá cerca de 32 B/ciclo; convertido para 3 GHz, isso fica quase 96 GiB/s, assumindo que não haja gargalo de memória. Claro que, nesse tipo de algoritmo, o acesso à memória é sempre o gargalo
  Ainda assim, não parece chegar muito perto do uso ideal, e com Clang o resultado chega a 42,67 B/ciclo graças a um unroll melhor resolvido e uma seleção de instruções superior. Acho difícil até o cache L2 sustentar esse throughput, mas é interessante que a conversão de maiúsculas/minúsculas de strings de tamanho médio termine mais ou menos no tempo de a luz da tela atingir a córnea
  Alguns meses atrás implementei algo parecido em C# para conversão de maiúsculas/minúsculas ASCII dentro de UTF-8: https://github.com/U8String/U8String/blob/main/Sources/U8Str...
  Como strings curtas dominam a maioria das bases de código, a conversão com unroll para tamanhos abaixo do comprimento vetorizado é importante, e o switch é compilado como jump table com fall-through sem branches
  Por enquanto uso só até 256 bits, porque em casos como Zen 3 ou 4, que têm apenas unidades SIMD 256×4, isso já satura. Há uma comparação lado a lado com uma versão em C aqui: https://godbolt.org/z/eTGYhTPan
  Em AVX512, parece possível fazer a conversão com 3 instruções usando vpternlogd; quando eu tinha hardware AVX512 disponível, o .NET otimizava assim com largura de 256 bits + AVX512VL, mas agora, estranhamente, não consigo reproduzir com largura de 512 bits
  Também dá para ver uma tentativa fracassada de SWAR no dispatch do switch; fico curioso sobre a licença do texto. Se passar na suíte de testes, eu gostaria de usar

  • Clang e GCC têm formas diferentes de tratar intrinsics, e em especial, nas instruções AVX-512, o Clang tem mais chances que o GCC de se desviar do opcode e do algoritmo especificados no guia da Intel
    Considerando a arquitetura dos dois compiladores, dá para entender, mas às vezes o resultado é uma melhoria e às vezes é um prejuízo
    Alguns anos atrás trabalhei em um projeto altamente vetorizado que precisava compilar com ambos, e acabamos mantendo no repositório assembly inline para alvos específicos e arquivos .S, junto com uma versão de referência em C
    O Makefile ficou uma bagunça e tivemos de colocar até benchmarks na suíte de testes, o que gerou um grande peso de manutenção; por isso cheguei à conclusão de que é preciso muito cuidado ao usar intrinsics como um recurso de baixo nível melhor que a autovetorização
    Ex.: em https://godbolt.org/z/T4Pjhrz5d, a saída do GCC era a esperada, mas a do Clang foi surpreendente e, na prática, mais lenta. Em loop, pelo uiCA, são 7 ciclos contra 4 ciclos do GCC, e isso também apareceu em benchmarks de um app real em que essa função era executada bilhões de vezes em um algoritmo de força bruta
    Lembro também de ter visto, ao olhar a base de código do LLVM, um problema em que o Clang 16 talvez nem emitisse algumas instruções AVX-512 com máscara por causa de uma refatoração interna
  • A análise é muito útil
    A intenção não era buscar o desempenho máximo possível; no começo eu só queria ver se funcionava, e foi um bônus a primeira tentativa ter saído bem razoável
    Meu interesse principal são strings menores que o registrador vetorial e eliminar os vales no gráfico de throughput
    Seguindo o link do código no fim do post do blog há informações de licença; fora a parte MPL-2.0 escrita originalmente para o BIND, é 0BSD ou MIT-0
  • Só olhando para um grande bloco de assembly é difícil perceber, mas o Clang reescreve (x >= 'a' && x <= 'z') na forma (x - 'a') < ..., reduzindo uma instrução
    Por causa de uma codificação de opcode esquisita, às vezes isso também reduz até um load de registrador

• Não sei o que é swar

  • É a sigla de “SIMD Within A Register”
    Normalmente se refere a uma técnica em que vários itens são empacotados em um único registrador e usados, na prática, como SIMD, mesmo sem instruções SIMD explícitas
    Por exemplo, se você colocar números de 31 e 32 bits em um registrador de 64 bits e deixar 1 bit para carry, dá para fazer duas somas com uma única soma de 64 bits
    Em jogos, valores RGB(A) têm sido empacotados em inteiros de 32 bits para usar truques assim em gráficos, e o ScummVM também tem código que interpola 2 pixels RGB de 16 bits dentro de um valor de 32 bits, totalizando 6 componentes: https://github.com/scummvm/scummvm/blob/master/graphics/scal...
  • Significa SIMD dentro de um registrador

• Depois que Unicode apareceu, os conceitos de maiúsculas e minúsculas viraram um pântano
  Para fazer direito, é preciso muitos dados
  Se você está fazendo uma tarefa cujo sucesso depende de um tolower ASCII terminar a tempo, talvez seja melhor virar o jogo de algum jeito e mudar as premissas

• Antigamente, coloquei uma borda preta em volta de imagens para evitar completamente o problema de leituras SIMD além do buffer
  Funcionou muito bem e, em termos de velocidade, conseguiu superar algumas implementações do OpenCV, mas nem sempre dá para controlar totalmente a entrada desse jeito

• Fico curioso se tentaram fazer assim. O resultado da autovetorização parece bem limpo
  https://godbolt.org/z/1c5joKK5n

  • Isso é basicamente igual a tolower1. Veja os bullets abaixo do gráfico