{n} vezes mais rápido que C

 (owen.cafe)
1 pontos por GN⁺ 2023-07-07 | 1 comentários | Compartilhar no WhatsApp
  • Mesmo em um loop pequeno em C, a saída do compilador nem sempre é a melhor possível; ao ajustar manualmente o assembly x86_64, a versão sem desvios condicionais ficou 6,73 vezes mais rápida que a saída do clang
  • A função alvo trata 's' como +1, 'p' como -1 e '\0' como término ao percorrer uma string, mas a saída do clang 16 divide esse fluxo em 3 desvios condicionais
  • Após trocar a ordem dos desvios, reorganizar os blocos básicos e substituir saltos por aritmética, o tempo de execução caiu de 3,23 s para 2,87 s, igualando a velocidade do GCC 12 nessa etapa
  • A versão mais rápida usa cmove para escolher entre 0, 1 e -1 como valor a somar para cada caractere e então sempre executa add, registrando 0,48 s e vazão de 1,94 GiB/s
  • O benchmark foi feito em um AMD Ryzen 5 5625U com Linux 6.1.33, processando 1 milhão de caracteres aleatórios 'p'/'s' 1000 vezes e usando o melhor resultado entre várias execuções

Função testada e saída do compilador

  • A função alvo incrementa um ponteiro de string caractere por caractere e atualiza o inteiro res conforme o caractere
    • 's': res += 1
    • 'p': res -= 1
    • '\0': retorna res
    • qualquer outro caractere: sem mudança
  • Como a função é pequena, a expectativa inicial era que gcc ou clang conseguiriam otimizá-la muito bem, talvez até de forma ótima
  • O assembly inicial gerado pelo clang divide os quatro casos em três desvios condicionais (je, je, jne)
    • começa com res = 0
    • lê um caractere e primeiro verifica se é '\0'
    • depois compara com 'p' e 's'
  • Resultado inicial do clang
    • Tempo de execução: 3,23 s
    • Vazão: 295,26 MiB/s
  • O GCC gerou um pouco mais de código, mas foi levemente mais rápido

Verificar os caracteres comuns antes da condição rara de término

  • O loop só termina ao encontrar o caractere nulo '\0', e nesse contexto ele pode aparecer no máximo uma vez
  • A saída do clang verifica '\0' primeiro, fazendo com que cada caractere 'p' e 's' passe antes pela condição de término
  • A primeira mudança manual foi inverter a ordem das comparações para verificar 'p' e 's' primeiro
  • Resultado
    • Tempo de execução: 3,10 s
    • Ganho de velocidade: 1,04x
    • Vazão: 307,64 MiB/s

Reorganização de blocos básicos e redução de saltos

  • Como os dois casos comuns, 'p' e 's', ambos saltam de volta para o início do loop, dá para reduzir desvios posicionando um dos blocos acima do loop
  • Colocando o bloco de 's' logo antes do loop, a execução cai de volta no loop após tratar 's', sem salto extra
  • Em troca, no início da função é preciso um salto único para pular o bloco de 's' e entrar no loop
    • o salto no início da função acontece só uma vez
    • como 's' pode aparecer muitas vezes, isso foi tratado como um trade-off aceitável
  • Resultado
    • Tempo de execução: 2,98 s
    • Ganho total de velocidade: 1,08x
    • Vazão: 320,02 MiB/s

Eliminar um salto incondicional com aritmética

  • Para remover o jmp incondicional que volta ao loop no bloco p:, foi usada aritmética
  • Como uma redução de 1 pode ser obtida com sub eax, 2 seguido de inc eax, isso permite que, após tratar 'p', o fluxo caia no bloco de 's'
  • Com isso, mais uma instrução de desvio foi eliminada
  • Resultado
    • Tempo de execução: 2,87 s
    • Ganho total de velocidade: 1,12x
    • Vazão: 332,29 MiB/s
  • Nesse ponto, o desempenho ficou igual ao do código gerado pelo GCC 12
    • o código do GCC 12 também roda em 2,87 s
    • a versão escrita manualmente tem 13 instruções
    • a saída do GCC tem 19 instruções
    • o código do GCC aparentemente desenrola o loop e reutiliza parcialmente os blocos de case

Substituir desvios condicionais por cmove

  • Se os desvios condicionais são o gargalo, é possível eliminá-los sem depender do preditor de desvios
  • A versão mais rápida usa cmove, ou seja, movimentação condicional se igual
  • A regra de funcionamento é simples
    • o valor padrão é 0
    • se o caractere atual é 's', usa 1
    • se o caractere atual é 'p', usa -1
    • em cada iteração, o valor escolhido é sempre somado a res
  • Essa abordagem remove muitas setas do grafo de fluxo de controle
  • Resultado
    • Tempo de execução: 0,48 s
    • Ganho total de velocidade: 6,73x
    • Vazão: 1,94 GiB/s
  • Nesse loop compacto em C com assembly escrito à mão, foi possível obter um ganho de mais de 6x com uma otimização que o compilador não automatizou

Tentativa de economizar registradores e outros experimentos que falharam

  • Também foi testada uma versão com sete do x86_64, que define condicionalmente um registrador de 1 byte como 0 ou 1
  • Essa versão elimina o uso de r8d, mas foi mais lenta que a versão baseada apenas em cmov
  • Resultado
    • Tempo de execução: 0,51 s
    • Ganho total de velocidade: 6,33x
    • Vazão: 1,83 GiB/s
  • Usar menos registradores ou operações de 8 bits no lugar de operações de 32 bits não trouxe mais velocidade
  • Outras tentativas também pioraram o desempenho
    • desenrolar o loop da melhor versão: ficou mais lento
    • alinhar o início do loop a um limite de 16 bytes: ficou mais lento
    • no GNU assembler, colocar .align <bytes> antes de um rótulo pode inserir nop

Ambiente de benchmark e código

  • A lista de códigos está no GitHub
  • Ambiente de benchmark
    • OS: Linux 6.1.33
    • CPU: AMD Ryzen 5 5625U with Radeon Graphics
    • família de CPU 25, 6 núcleos, 2 threads por núcleo, 1 soquete
    • clang: 16.0.1
    • gcc: 12.2.0
  • A versão em C foi compilada com -march=native para permitir a geração de código ajustado à CPU específica
  • O benchmark usa uma lista de 1 milhão de caracteres aleatórios 'p' e 's'
    • cada versão da função processa essa lista 1000 vezes
    • cada versão é executada várias vezes e o melhor resultado é escolhido
  • O texto continua em um artigo seguinte, part two

Leituras relacionadas

1 comentários

 
GN⁺ 2023-07-07
Comentários do Hacker News

  • A conclusão correta parece ser menos assembly escrito à mão é 6 vezes mais rápido que C e mais saltos podem ser muito mais lentos que aritmética condicional
    Mesmo em C, se você não usar switch e tratar com um ou dois if, dá para obter facilmente o mesmo efeito. Ao mudar a função em C para algo como incrementar se for s, decrementar se for p e encerrar se for \0, ficou 5,5 vezes mais rápida, caindo de 3,58 segundos para 0,65 segundo no exemplo de execução

    • Boa. Na parte 2, reescreveram o C e obtiveram melhoria de 12 vezes: https://owen.cafe/posts/the-same-speed-as-c/
      Como outros disseram, também dá para vetorizar o algoritmo depois de ajustar a entrada. Encarei isso como um exercício educacional e sinceramente espero que ninguém desça para assembly sem um motivo realmente forte
    • Dizer que saltos são mais lentos que aritmética condicional está correto quando os saltos são imprevisíveis. Quando os saltos são previsíveis, eles são mais rápidos
      O Linus já escreveu longamente no passado que cmov não é útil em desvios previsíveis: https://yarchive.net/comp/linux/cmov.html
    • Fiquei curioso sobre qual versão do GCC foi usada. No Ubuntu e no Windows o desempenho foi o mesmo, e no gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 tanto lone quanto ltwo ficaram em cerca de 3,58 segundos
    • Fico pensando se trocar switch por vários if é sempre mais rápido. Também queria saber a partir de quantos casos o switch passa a ser melhor e, se isso for consistente, parece algo que deveria entrar em otimização de compilador
    • Parece que o compilador deveria ser capaz de fazer esse tipo de transformação

  • Acho que o código original não foi escrito de forma muito amigável ao compilador. Se escrever como result += *s == 's'; result -= *s == 'p';, o compilador gera o código sem desvios com sete/cmov apropriado, e a velocidade fica quase igual à do assembly otimizado do texto
    Ainda assim, ele não faz unrolling do loop nem vetorização. Se você passar também o tamanho da string e iterar sabendo o size, o compilador conhece o tamanho do loop, faz unrolling e, se possível, usa instruções AVX-512. Em entradas grandes fica muito mais rápido, mas estou com preguiça de benchmarkar isso manualmente. Se você é um programador C que não acompanha o comprimento das strings, faça como quiser, mas na minha opinião realmente não deveria: https://godbolt.org/z/rde51zMd8

    • A versão amigável ao compilador está na parte 2: https://owen.cafe/posts/the-same-speed-as-c/
      Essa versão alcança 3,88GiB/s. De propósito não fui até a vetorização; queria manter o escopo do problema pequeno e mostrar as dicas e truques de assembly do texto. Ainda dá para escrever depois um artigo sobre fazer padding na string de entrada e vetorizar o algoritmo
    • Está faltando uma linha importante no código: /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */
    • Parece que em Nim isso também dispara se você fizer algo assim: ativar {.overflowChecks:off.} e percorrer input, incrementando quando 's' == c e decrementando quando 'p' == c
      No Apple M1 houve cerca de 5 vezes de ganho de desempenho, e com a checagem de overflow ligada ficou só em algo como 2 vezes sobre a versão C básica. É sempre bom conhecer padrões que induzem otimizações SIMD
    • “Realmente não deveria” quer dizer que não se deve deixar de acompanhar o comprimento da string?

  • Falando como alguém mais próximo de especialista em otimização, eu resolveria esse problema de forma totalmente diferente. No meu computador, a versão C inicial fazia 389MB/s, e se o assembly do texto entregar a mesma melhoria de 6,2 vezes, isso dá algo em torno de 2,4GB/s
    Em buffers longos, esta versão em C++ passa de 24GB/s no meu computador: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
    Sem assembly, usando intrinsics de AVX2, ela fica 61 vezes mais rápida que a versão original

    • Interessante. Em vez de manter contadores em registradores ymm, parece que dá para vetorizar o prólogo usando movemask e popcnt
      Ainda não testei o código, então precisaria de benchmark, mas parece possível seguir por esse caminho criando máscaras para s, p e \0, e usando tzcnt e bzhi para contar os bits até o fim da string
    • Fiquei curioso se isso também dá para fazer com std::experimental::simd: https://en.cppreference.com/w/cpp/experimental/simd
    • Seria bom reescrever isso de uma forma compatível com o repositório do @414owen
    • Queria saber de bons materiais para aprender e praticar AVX

  • Este código parece combinar muito bem com SIMD. Se der para mudar o protótipo para receber um comprimento explícito, fica fácil ler e processar 16 bytes por vez
    Dá para somar e subtrair diretamente os resultados das comparações, e provavelmente já vale a pena só chamar strlen() no começo da função para obter um comprimento explícito

  • Fiz rapidamente uma implementação vetorizada em RISC-V. Ela usa rvv para ler a string, encontrar a posição do \0 e então contar com vcpop quantos s e p existem
    Num Mangopi MQ Pro (C906, rv64gc + rvv 0.7.1, comprimento de vetor de 128 bits), o switch ficou em 0,19 Bytes/Cycle, a implementação em C com tabela ficou em 0,17 Bytes/Cycle, e rvv ficou em 1,57 Bytes/Cycle, caindo para 1,35 depois de cerca de 30KiB. Se alinhar o ponteiro à página e fizer vl não ultrapassar o tamanho da página, dá para chegar a 2/1,7 Bytes/Cycle

    • Para ficar totalmente correto, o load deveria ser um fault-only-first load. O rvv tem esse recurso; caso contrário, pode falhar quando o byte nulo estiver logo antes do fim da memória alocada

  • Isso parece ser uma característica específica da arquitetura x86. Como o custo de não fazer desvio é muito baixo, o desvio acaba parecendo relativamente caro: https://wordsandbuttons.online/challenge_your_performance_in...
    Mas em outros processadores isso pode não ser verdade: https://wordsandbuttons.online/using_logical_operators_for_l...
    A pergunta maior é por que o C é necessário em geral. Se a ideia é ajustar tudo manualmente para rodar da melhor forma em um hardware específico, então C é a ferramenta errada, e o que você precisa é assembly e um bom sistema de macros. O objetivo original de C era facilitar a portabilidade de código de nível de sistema de uma plataforma para outra, e a perda de eficiência nesse processo era esperada. É parecido com escrever um poema em esperanto e depois traduzi-lo automaticamente para o idioma desejado, em vez de traduzir poesia em hindi para urdu. Você não vai conseguir dois grandes poemas, mas consegue rapidamente duas traduções ruins, e esse é o papel do C

  • Se você compilar com FDO/PGO, então reordenação de desvios e de blocos certamente pode acontecer. Sem FDO, o compilador não tem como saber com que frequência cada desvio será escolhido. Em alguns casos, FDO também pode ativar cmov
    Mas se cmov é mais eficaz do que um test/jump comum depende muito de quão previsível é o desvio; em geral, cmov funciona melhor quando o desvio é muito imprevisível. Se cmov ficou 6 vezes mais rápido, então imagino que a entrada de teste seja uma string aleatória composta quase toda de s e p. Não está errado, mas o texto parece um pouco enganoso porque explora no benchmark uma propriedade não mencionada dos dados

    • O código de teste está aqui: https://github.com/414owen/blog-code/blob/master/02-the-same...
      Escolhe aleatoriamente 's' ou 'p', e nenhum caractere além de 's', 'p' e o nulo terminador pode aparecer. Sabendo dessa característica da entrada, dá até para fazer uma otimização esperta demais como result += (1 | *s++) - 'r';. É um código inteligente até demais, mas ilustra perfeitamente o ponto de explorar propriedades dos dados
    • Dentro da string, '\0' só pode aparecer no máximo uma vez, porque a função retorna ao encontrá-lo, enquanto os outros caracteres podem aparecer várias vezes. Isso parece ser informação à qual o compilador poderia ter acesso mesmo sem PGO
      Claro que PGO ajuda, e no meu computador deu 2,80 s, melhor que o código no fim da seção Rearranging blocks. A entrada está descrita em Benchmarking setup e também está no repositório: https://github.com/414owen/blog-code/blob/master/01-six-time...
      Na parte 2, linkada no fim do texto, eles deixam o código C o mais rápido possível e vencem todo o assembly deste artigo. Nunca disse que usar assembly é necessariamente uma boa ideia; só acho que otimização e interpretação da saída do compilador são um desafio interessante e uma boa oportunidade de aprendizado

  • Acho que fiz uma versão mais rápida do que a do artigo e a do texto seguinte. Mas isso tem o custo de ser especializada para o caso em que a string é composta apenas de 's' e 'p'
    Como o benchmark também testa apenas strings formadas por 's' e 'p', acho justo. O ponto central é que queremos aumentar res em 1 quando o próximo caractere for s, mas res += c - 'r' falha porque vale 1 para s, mas -2 para p. Só que, se você tratar 'p' - 'r' como inteiro sem sinal, acontece underflow e a carry flag é ativada, e o adc no x64 soma dois registradores junto com a carry flag. Assim, dá para trocar dois cmp, cmov por um único sub, adc. Esta versão foi 1,08 vez mais rápida que a versão em C do texto seguinte e 1,66 vez mais rápida que a x64-7 original. Claro, ainda daria para melhorar mais com SWAR/SIMD

    • É uma abordagem interessante. Acho que eu deveria ter deixado explícito que o assembly um tanto simplista em 02-the-same-speed-as-c/loop-5.x64.s era apenas a versão mais rápida que eu tinha
      No meu computador, loop-5.x64.s faz 0,244 s, e a implementação acima faz 0,422 s. Não sei exatamente por que essa diferença aparece; olhando, a implementação acima parece mais rápida. Por isso é importante sempre medir no hardware real em que o código vai rodar
    • Uma abordagem ainda mais simples seria somar todos os elementos do array e, no fim, subtrair 'p' * len, depois dividir por ('s' - 'p') para obter a contagem de s. A contagem de p seria len - s_count
      A soma inicial também é facilmente vetorizável. Se eu não estiver cometendo nenhum erro, isso deve funcionar; o único problema seria a possibilidade de overflow no acumulador. Não estou com vontade de fazer benchmark disso. Edit: deixei passar a parte em que ao ver s o valor diminui, então o resultado final é p_count - s_count

  • strlen() provavelmente já é implementado de forma bem rápida e, se o tamanho do buffer for conhecido, o compilador pode vetorizar automaticamente o loop interno
    De fato, o código len = strlen(buf) seguido de um loop for somando (buf[i] == 's') - (buf[i] == 'p') é autovetorizado: https://gcc.godbolt.org/z/qYfadPYoq

  • No passado, escrevi um decodificador UTF-8 em Common Lisp para SBCL. Já existia um decodificador embutido, então era só por prática
    Tirando as otimizações óbvias e fáceis, quase todo o ganho de desempenho veio de estruturar o código de forma que o compilador gerasse instruções cmov* em vez de desvios

    • Fiquei curioso para ver um exemplo de como você mudou o código. E também queria saber se você ficou desassemblando a função repetidamente para conferir se estava usando as instruções certas, ou se confirmou a melhora real com benchmarks
    • Se o desvio for previsto corretamente, ele provavelmente será mais rápido do que uma movimentação condicional, porque o desvio não aumenta o comprimento do caminho crítico
      Decodificadores UTF-8 normalmente rodam bastante em entradas compostas inteiramente por ASCII. Fiquei curioso sobre que tipo de entrada foi usada no benchmark