Aumentando em 4 vezes o desempenho do código com um if inútil

 (purplesyringa.moe)
1 pontos por GN⁺ 3 시간 전 | 1 comentários | Compartilhar no WhatsApp
  • Ao adicionar uma única condicional ao loop que percorre o caminho ótimo de codificação de um compressor específico de domínio, o tempo de execução de um benchmark sintético caiu de 320 µs para 80 µs
  • Como, a cada iteração, o endereço de memória depende do j da iteração imediatamente anterior, até uma única instrução mov fica presa à latência de acesso à memória, sem conseguir aproveitar o paralelismo em nível de instrução
  • Ao refletir na predição de desvio a característica de que next_j[i][j] é, na maioria das vezes, igual ao j existente, a CPU consegue contornar a dependência entre iterações e executar especulativamente várias iterações
  • Usa-se um cast para volatile para impedir que o compilador remova o if semanticamente desnecessário. No LLVM, [[unlikely]] ou __builtin_expect(..., 0) também funcionam, mas volatile gera código melhor e também é suportado pelo GCC
  • Em um experimento realista, obteve-se uma melhora de desempenho de cerca de 2 vezes, possivelmente devido à geração de código não ideal do LLVM; se for difícil prever j, pshufb, com latência de 1 ciclo, pode ser usado como alternativa

Percorrendo o caminho ótimo do compressor

  • É preciso dividir a string de entrada em vários chunks e escolher a menor codificação para cada chunk
    • Como cada codificação comprime bem caracteres diferentes, é difícil decidir diretamente os limites dos chunks
    • O algoritmo do artigo anterior transforma esse problema em uma busca pelo caminho mais curto em uma grade
  • Cada célula registra a próxima célula ótima para onde seguir
    • Seguindo as referências da primeira célula até a última, obtém-se a sequência ótima de codificações
  • O primeiro loop, que preenche next_j, já foi otimizado com SIMD
    • O gargalo real é o loop simples de percurso do caminho, como abaixo
uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}
  • A operação central, excluindo a escrita, j = next_j[i][j], é compilada para uma única instrução mov

Dependências que deixam até uma única instrução lenta

  • CPUs modernas usam paralelismo em nível de instrução para executar simultaneamente várias instruções e trabalhos de iterações diferentes
    • É por isso que, em loops comuns, o custo de verificar i < n_symbols e de fazer i++ não bloqueia os outros trabalhos
  • Porém, instruções dependentes entre si não podem ser executadas ao mesmo tempo
    • Para calcular o endereço de memória next_j[i][j] da iteração atual, é necessário o j obtido na iteração imediatamente anterior
    • A próxima iteração não pode começar até que o resultado da anterior esteja disponível; assim, mesmo que os dados estejam no cache, ela sofre o impacto da latência de acesso à memória

Usando predição de desvio como especulação de valor

  • Como se espera que este compressor não tenha muitos chunks, next_j[i][j] será igual ao j existente na maioria dos casos
  • Não é possível instruir diretamente a CPU a prever o endereço supondo que j será mantido, mas é possível obter o mesmo efeito usando predição de desvio
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}
  • Se a CPU prever que o corpo do if não será executado, ela considerará que não há dependência entre iterações para atualizar j e executará especulativamente várias iterações
  • Se a condição for realmente verdadeira, ocorre a recuperação de uma falha de predição de desvio
    • As escritas feitas com a especulação errada são descartadas
    • A execução é reiniciada usando o j correto
  • Enquanto j quase não muda, o gargalo do loop passa de latência para throughput

Impedindo o compilador de remover o if

  • Do ponto de vista do compilador, o código com a condicional adicionada tem a mesma semântica do código original
    • Se j estivesse na memória, seria possível evitar uma escrita desnecessária ou uma escrita em memória somente leitura, mas aqui ele é um valor em registrador
    • Otimizações como eliminação de subexpressão comum (CSE) podem remover a condição e o acesso duplicado
  • Hints comuns de compilador são usadas para eliminar desvios, mas aqui é o contrário: é preciso manter código com desvio em vez de código sem desvio
  • Aplica-se um cast para volatile no lado da atribuição para fazer os acessos à memória da verificação da condição e da atribuição parecerem independentes
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}
  • Em uma verificação adicional em 13 de julho, como no método encontrado por ibookstein, também é possível obter o mesmo efeito no LLVM usando [[unlikely]] ou __builtin_expect(..., 0)
  • A abordagem com volatile gera código melhor e também funciona no GCC

Mudanças de desempenho observadas no benchmark

  • No benchmark sintético, o tempo de execução do loop caiu de 320 µs para 80 µs, ficando 4 vezes mais rápido
    • A diferença em uma única execução é pequena, mas, como o loop é executado várias vezes durante a compressão, ela se acumula no custo total
  • Em um experimento mais realista, foi registrada uma melhora de desempenho de cerca de 2 vezes
    • Possivelmente houve influência de o LLVM ter gerado código não ideal, mas ainda assim era um nível que valia a pena aplicar

Uma alternativa: representação baseada em bitmask

  • Neste algoritmo, next_j[i][j] pode ter apenas um de dois valores
    • Na maioria das vezes, é o j atual
    • O restante é um valor independente de j e dependente apenas de i
  • É possível substituir next_j[i], um array de 8 elementos, por um par de valor alternativo e bitmask
    • Nessa representação, o if é semanticamente necessário, então não é preciso usar o contorno com volatile
    • Porém, no x86, operações que testam um bit em uma posição variável podem ser mais lentas que uma comparação, então o desempenho geral pode acabar ficando menor

Quando não é possível prever j

  • O artigo sobre acelerar a travessia de listas ligadas com especulação de valor também trata de uma forma de melhorar o desempenho usando o mesmo método
  • Se for difícil prever j, pode-se usar pshufb, uma operação de índice vetorial
    • A latência de pshufb é de 1 ciclo, então é difícil reduzir mais sem execução especulativa
    • Com operações vetoriais, é possível calcular em paralelo os caminhos para cada j inicial possível
    • Também é possível dividir o trabalho entre várias threads e mesclar os resultados

Leituras relacionadas

1 comentários

 
GN⁺ 3 시간 전
Opiniões no Lobste.rs

  • Parece que adicionar o atributo [[unlikely]] do C++20 a uma instrução if já basta para impedir que o clang elimine esse código: https://clang.godbolt.org/z/r4xYWfPfe
    Não consegui verificar em outros compiladores

    • Revendo, no LLVM isso realmente funcionou, e acho que no começo eu tinha testado por engano com GCC, onde não fazia efeito
      Mas o [[unlikely]] move o código para fora do caminho rápido, então o LLVM gera um código um tanto ineficiente, assim 
              cmp     r8b, dl  
        jne     not_equal  
continue:  
        ...  
not_equal:  
        mov     ecx, edx  
        jmp     continue
      O formato abaixo parece mais razoável 
              cmp     r8b, dl  
        je      skip  
        mov     ecx, edx  
skip:  
        ...
      Além disso, ele também adiciona uma instrução ao loop quente ao otimizar para não ler o valor várias vezes da memória. Por isso, a técnica com volatile ainda continua útil, mas é bom saber que o código original também pode continuar funcionando

  • Essa técnica é chamada em outros lugares de value speculation: https://mazzo.li/posts/value-speculation.html

    • Depois de reinventar esse método, a primeira coisa que pensei foi que ele também poderia ser aplicado a uma lista ligada armazenada em arena, e o texto linkado trata exatamente disso, então adicionei o link ao meu post

  • Daqui a 2 ou 3 anos, os desenvolvedores provavelmente vão ficar cada vez mais indiferentes à saída de LLMs, então fico me perguntando se ainda vão se interessar por esse tipo de post de blog

    • Mesmo hoje, são pouquíssimas as pessoas que ligam para isso; no conjunto da programação, é um conhecimento de nicho
      Ainda assim, para quem se interessa, continua sendo algo muito útil e um ótimo texto
    • Godbolt é muito popular. Quando criticam o hábito de não ler código, desenvolvedores deslumbrados com LLMs às vezes respondem “você olha até assembly?” como se fosse uma grande réplica, mas eu realmente verifico o assembly e vou continuar fazendo isso
      Um desenvolvedor que acha que detalhes não importam dificilmente se tornará um bom desenvolvedor. Assim como um grande engenheiro civil se preocupa até com parafusos e porcas de um projeto grande, um grande desenvolvedor também precisa ir a fundo nos pequenos detalhes. O todo é feito de detalhes, então, se você se importa com o que produz, não tem como evitar isso
    • Não acho que seja algo fundamentalmente diferente de agora. Já hoje a maioria não se interessa pela saída do compilador de código escrito por humanos
      Pode até haver menos gente olhando a saída do compilador de código escrito por IA, mas a estrutura básica não deve mudar
    • O que muda se parece menos com a existência ou não de interesse e mais com uma reorganização das prioridades de otimização
      Dez anos atrás, se um script Bash estivesse um pouco lento, você não começaria pensando em paralelismo no nível de instrução ou previsão de desvios da CPU. Pode haver um trecho crítico de desempenho escrito em uma linguagem compilável e otimizável; dentro dele, um caminho quente que vale inspecionar em detalhe; e, dentro dele, um ou dois loops quentes em que vale a pena verificar vetorização ou diferenças de comportamento em CPUs modernas
      Mesmo usando LLM, os pontos mais quentes em termos de desempenho ainda podem valer uma revisão manual excepcional. Você pode aceitar conscientemente a baixa qualidade do resultado, ou usar LLM para fazer 70% e corrigir os 30% restantes à mão — talvez isso melhore para 85:15 — mas este texto continua tratando de uma área de detalhes de nível top 1%
    • Como não escrevo C++, nesse sentido isso já não é um alvo direto do meu interesse hoje, mas mesmo assim achei a leitura interessante e daqui a 2 ou 3 anos esse tipo de conteúdo provavelmente ainda vai continuar sendo divertido