A função `tolower()` usando AVX-512

• Há alguns anos, escrevi sobre como acelerar tolower() usando truques de SWAR. Alguns dias atrás, fiquei interessado em um texto de Olivier Giniaux sobre uma otimização para processar strings pequenas com instruções SIMD. Esse método é usado em uma função de hash rápida escrita em Rust.

• Instruções SIMD facilitam o processamento de strings curtas, mas sempre me incomodou a dificuldade de transferir dados entre a memória e os registradores vetoriais. O texto de Olivier apresentou uma maneira interessante de resolver esse problema.

Sinais de esperança

• Alguns conjuntos de instruções SIMD oferecem funções úteis de carregamento e armazenamento com máscara para processamento de strings. Elas operam em nível de byte.

  • ARM SVE: disponível em grandes núcleos ARM Neoverse recentes, como os do Amazon Graviton. Porém, não está disponível no Apple Silicon.
  • AVX-512-BW: disponível em processadores AMD Zen recentes. AVX-512 é um conjunto de extensões complexo, e no caso da Intel o suporte é bastante aleatório.

• Como eu tinha uma máquina com AMD Zen 4, decidi experimentar AVX-512-BW.

tolower64()

• Usei o guia de intrinsics da Intel para escrever uma função básica tolower() capaz de processar 64 bytes de uma vez.
  • Pesquisei mm512*epi8 usando * como curinga para encontrar funções AVX-512 que operam em bytes.
  • Preenchi alguns registradores com 64 bytes úteis.
  • Configurei os valores necessários para converter letras maiúsculas em minúsculas.
  • Comparei os caracteres de entrada com A e Z para verificar se eram maiúsculos.
  • Usei uma máscara para converter em minúsculas quando o caractere era maiúsculo.

Carregamento e armazenamento em massa

• Era preciso encapsular o kernel tolower64() em uma função mais conveniente. Por exemplo, uma função que copia a string enquanto a converte para minúsculas.
  • Para strings longas, usei instruções de carregamento e armazenamento vetorial desalinhado.

Carregamento e armazenamento com máscara

• Para strings pequenas e para o final de strings longas, usei carregamento e armazenamento desalinhados com máscara.
  • A máscara tem os primeiros len bits ativados.
  • O carregamento e o armazenamento são semelhantes às versões de largura total com uma máscara adicional.

Benchmark

• Foi feito benchmark do desempenho de várias funções semelhantes.

  • Compilado com Clang 16 e executado em um AMD Ryzen 9 7950X.
  • Cada função foi compilada separadamente para evitar interferência de inline e movimentação de código.

• Resultados:

  • tolower64 foi a função mais rápida entre todas as testadas.
  • copybytes64 usa AVX-512 de forma parecida com tolower64, mas não é muito mais rápida.
  • copybytes1 faz memcpy byte a byte e mostra que a vetorização automática do Clang 11 é relativamente ruim.
  • A tolower() padrão foi a mais lenta.
  • tolower1 é uma tolower() byte a byte compilada com Clang 16; a vetorização automática melhorou, mas ainda é lenta.
  • tolower8 é a tolower() com SWAR apresentada em um post anterior do blog; o Clang tenta vetorização automática, mas o resultado não é bom.
  • memcpy é rápida no início, mas cai para metade da velocidade de copybytes64.

Conclusão

• AVX-512-BW é muito útil, especialmente ao processar strings curtas.

• No Zen 4, é muito rápido, e as funções intrínsecas são fáceis de usar.

• O desempenho do AVX-512-BW é muito estável.

• Não pude investigar em detalhe por não ter uma máquina com suporte a ARM SVE, mas fiquei curioso sobre o quão bem o SVE funciona com strings curtas.

• Espero que essas extensões de conjunto de instruções sejam adotadas de forma mais ampla. Elas podem melhorar bastante o desempenho no processamento de strings.

• O código deste post do blog pode ser visto no meu site.

Resumo do GN⁺

• Este texto explica como processar strings curtas com eficiência usando instruções SIMD.
• Mostra que os conjuntos de instruções AVX-512-BW e ARM SVE são úteis para processamento de strings.
• Nos benchmarks, o AVX-512-BW mostrou desempenho excelente, especialmente em strings curtas.
• O texto deve ser útil para desenvolvedores interessados em otimização de desempenho.

[GN⁺]

Comentários do Hacker News

• No modelo de memória do Rust e do LLVM, o truque de "unsafe read beyond of death" é considerado comportamento indefinido

  • O compilador pode assumir que esse comportamento não ocorre para fins de otimização
  • Para evitar isso, é preciso usar assembly inline

• Surgiu curiosidade sobre a implementação de AVX512 da AMD e a disputa com o AVX10 da Intel

  • O AVX10 existe para resolver o problema de núcleos P vs E da Intel
  • A AMD usa a largura total do Zen5 ou o double pump de 256 bits do Zen4 e do Zen5 mobile, conforme o caso
  • O grande ganho de desempenho acontece nos núcleos Zen4

• A otimização SWAR só é útil para strings alinhadas em endereços de 8 bytes

  • Aplicá-la a strings desalinhadas a torna mais lenta que o algoritmo original
  • Dividir o algoritmo em três partes exige mais instruções

• A adição de máscaras parece elegante

  • Seria bom se os recursos embutidos do .NET tivessem uma forma de manipular diretamente os registradores de máscara do AVX512

• Usando Clang, é possível obter resultados melhores

  • Ele oferece uma seleção de instruções melhor e um resultado final bem refinado

• O loop principal para strings curtas tem uma instrução a menos

  • É importante processar strings curtas rapidamente

• Alguém escreveu em C# uma implementação semelhante para converter ASCII em maiúsculas/minúsculas em UTF-8

  • Como strings curtas dominam a maioria dos codebases, é importante tratá-las rapidamente

• Há um exemplo de uso de SIMD com AVX512 para converter texto em uwu

• Seria ainda mais impressionante se considerasse conversão de caracteres Unicode

  • A maioria dos programadores só se preocupa com ASCII, mas existe um mundo muito maior além do conjunto de caracteres padrão

• No passado, houve a experiência de adicionar bordas pretas ao redor de imagens para evitar problemas de SIMD com buffers

  • Nem sempre é possível ter controle total sobre a entrada