Não zombe do feliz e divertido preditor de desvios (2023)

Não zombe do feliz preditor de desvios

• Tenho escrito bastante assembly AArch64 recentemente
• Uma ideia "inteligente" para remover um salto no loop acabou piorando o desempenho
• Explico esse erro para que outras pessoas não cometam o mesmo engano

Exemplo de código

float run(const float* data, size_t n) {
  float g = 0.0;
  while (n) {
    n--;
    const float f = *data++;
    foo(f, &g);
  }
  return g;
}

static void foo(float f, float* g) {
  // g를 수정하는 작업
}

Traduzido para assembly AArch64

// x0: const float* data
// x1: size_t n
// s0: float de retorno
stp  x29, x30, [sp, #-16]!
mov s0, #0.0
loop:
  cmp x1, #0
  b.eq exit
  sub x1, x1, #1
  ldr s1, [x0], #4
  bl foo
  b loop
foo:
  // s1에서 읽고 s0에 누적
  // ...
  ret
exit:
  ldp  x29, x30, [sp], #16
  ret

Tentativa de otimização

• Tentativa de melhorar o desempenho reduzindo a instrução bl
• Mas o desempenho acabou piorando

Comparação de desempenho

• Código original: 969 ns
• Código otimizado: 3.85 µs

Análise da causa

• O preditor de desvios fica confuso porque os pares bl e ret não correspondem
• Segundo a documentação da ARM, a instrução ret ajuda a prever retornos de função

Como resolver

• Usar br x30 em vez de ret
• Desempenho recuperado: 913 ns

Otimização adicional

• Fazer inline de foo para melhorar o desempenho
• Usar unrolling de loop e instruções SIMD

Desempenho final

• SIMD + unrolling manual de loop: 94 ns

Conclusão

• Não confunda o preditor de desvios
• O código SIMD é mais rápido, mas como a soma de ponto flutuante não segue a propriedade associativa, o resultado pode ser diferente

Opinião do GN⁺

• Este texto mostra bem a importância da otimização em assembly AArch64
• Entender como o preditor de desvios funciona é essencial para otimizar desempenho
• A otimização com instruções SIMD é muito eficaz, mas é preciso considerar questões de precisão
• Usar uma linguagem de alto nível como Rust pode facilitar ganhos de desempenho via otimizações do compilador
• Um projeto com funcionalidade semelhante é o guia de otimização em assembly de Agner Fog

[GN⁺]

Opiniões no Hacker News

• Resumiu o artigo junto com amigos da época do Apple II

  • Um código otimizado leva 94 nanossegundos para somar 1024 números de ponto flutuante de 32 bits
  • Um 6502 de 1 MHz passaria 94 nanossegundos tentando buscar da memória o primeiro byte da primeira instrução
  • Esse código só apresenta desempenho otimizado quando executa no cache. DRAM é lenta

• Raymond Chen abordou o mesmo tema há quase 20 anos

  • Depois de verificar o fim do loop, ele segue para a função foo sem desvio
  • Isso viola heurísticas básicas de predição
  • Já faz décadas que preditores de desvio mantêm uma pilha sombra de endereços de retorno

• Em código SIMD, a soma de ponto flutuante pode ser feita em outra ordem porque a adição de ponto flutuante não segue a propriedade associativa

  • Isso pode ser o motivo de o compilador não gerar instruções SIMD
  • Somas de ponto flutuante têm inerentemente uma margem de erro, e qualquer resposta dentro dessa faixa é válida
  • Se houver entradas especiais de ponto flutuante, a linguagem precisa fornecer meios para codificar isso explicitamente

• Desde o Rust 1.78, o compilador usa unrolling de loop mais agressivo e um pouco de SIMD

  • O unrolling de loop começou no Rust 1.59
  • No código do Github, estava sendo usada a versão Rust 1.67.0-nightly

• Houve confusão sobre como x0 é incrementado em assembly ARM/ARM64

  • A instrução ldr s1, [x0], #4 faz o carregamento enquanto incrementa x0 em 4
  • No x86_64 não existe uma única instrução que faça carregamento e incremento ao mesmo tempo

• Surpreendeu que não tenham tentado um método menos complexo para otimizar o código assembly

  • Dá para reescrever o código assembly para precisar de apenas um desvio no fim do loop
  • É possível fazer inline de foo e omitir a instrução RET

• Houve quem desejasse que o autor não ficasse mudando de unidade o tempo todo