Não zombe do preditor de desvios Happy Fun (2023)

 (mattkeeter.com)
1 pontos por GN⁺ 2024-07-05 | 1 comentários | Compartilhar no WhatsApp
  • Uma otimização que tentava reduzir em um desvio um loop em assembly AArch64 acabou ficando 4 vezes mais lenta; a causa foi confundir o preditor de desvios ao usar de forma assimétrica o par chamada-retorno bl/ret
  • O código original faz dois desvios por loop, bl foo e b loop, mas o código modificado tentou reduzir o número de desvios fazendo um único bl loop para fixar x30 e então permitindo que vários ret retornassem ao mesmo endereço
  • No M1 Max, ao somar um array de 1024 float, o código normal com bl/ret levou 969 ns, mas a estrutura com um único bl e vários ret ficou em 3,85 µs; ao trocar ret por br x30, o tempo voltou para 913 ns
  • Os contadores de desempenho do Instruments mostraram que, ao somar 1 bilhão de elementos, a estrutura assimétrica bl/ret teve cerca de 93% de falhas de predição em desvios de retorno, e FETCH_RESTART, MAP_DISPATCH_BUBBLE e MAP_REWIND também aumentaram muito
  • Implementações mais rápidas passam por inline de foo, Rust iter().sum(), SIMD NEON e desenrolamento manual de loop; a versão SIMD final caiu para 94 ns, mas, como a ordem das somas de ponto flutuante muda, o resultado pode ser diferente

O efeito contrário em um loop AArch64

  • A função de exemplo percorre um array de float, passa cada valor para foo, e foo atualiza o valor acumulado g
  • Uma conversão AArch64 simples tem o seguinte fluxo
    • Verifica no início do loop se n == 0
    • Lê o valor com ldr s1, [x0], #4
    • Chama a sub-rotina com bl foo
    • O ret de foo volta para a instrução seguinte ao bl
    • Volta para o início do loop com b loop
  • foo tem uma forma próxima de uma naked function, usando o mesmo stack frame e os mesmos registradores da função pai, lendo s1 e acumulando em s0

O papel de bl e ret

  • bl é a instrução branch and link: ela salta para o rótulo especificado e salva o endereço da próxima instrução no registrador de link lr ou x30
  • ret salta para o endereço armazenado no registrador de link
  • Na estrutura original, bl foo e ret formam um par correspondente, e ret sempre volta para a instrução logo após aquele bl

A otimização fracassada de “reduzir um desvio”

  • A estrutura modificada tenta reduzir um desvio dentro do loop sem alterar foo
    • No início da função, chama bl loop para colocar em x30 o endereço inicial de loop
    • Depois de verificar a condição de término do loop, cai diretamente no código de foo sem um desvio separado
    • O ret de foo volta para loop, que está em x30
  • Nessa estrutura, x30 não muda no corpo do loop, então os ret repetidos sempre retornam ao mesmo endereço
  • O foo simples é um código de uma linha que soma float, assim:
foo:
    fadd s0, s0, s1
    ret
  • Nesse caso, a função inteira calcula a soma do array de entrada de float

Resultados de benchmark e problema de predição de desvios

  • O benchmark de um array de 1024 elementos foi feito na CPU M1 Max com criterion
    • bl/ret normal: 969 ns
    • Um único bl, vários ret: 3,85 µs
  • O código que reduziu um desvio ficou cerca de 4 vezes mais lento que o código original com dois desvios
  • Cliff e Dan entenderam que o par bl/ret não correspondia, o que confundiu o preditor de desvios
  • Segundo a documentação da ARM, RET permite que o processador reconheça retornos de função e faça uma predição de desvios mais precisa
    • BR LR também pode fazer funcionalmente a mesma coisa
    • Mas RET é uma instrução separada que o processador consegue reconhecer como retorno de função
    • Quando a predição de desvio acerta, as instruções corretas entram no pipeline e é possível evitar o tempo de espera por instruções vindas da memória

Pilha de endereços de retorno e experimento com br x30

  • É provável que o preditor de desvios mantenha internamente uma pilha de endereços de retorno de funções
    • Ao executar bl, faz push do endereço de retorno na pilha
    • Ao ver ret, assume que ele voltará para o endereço de retorno do bl mais recente
    • A partir desse endereço, começa a busca antecipada e a execução especulativa, e depois faz pop da pilha
  • Esse método funciona bem quando bl/ret são pares correspondentes
  • Se vários ret usarem repetidamente o mesmo endereço, a predição pode falhar, causando buscas antecipadas inúteis, execução especulativa errada e paradas ou flushes no pipeline
  • Como Dan sugeriu, ao trocar ret por br x30, a perda de desempenho desapareceu
    • bl/ret normal: 969 ns
    • Um único bl, vários ret: 3,85 µs
    • Um único bl, vários br x30: 913 ns
  • A versão com br x30 executa apenas um desvio por loop, por isso é ligeiramente mais rápida que o código original

Contadores de desempenho do Instruments

  • Foram verificados com o Instruments os contadores de desempenho dos dois primeiros programas
  • A medição foi feita durante a soma de um array de 1 bilhão de elementos
  • No bl/ret assimétrico, houve cerca de 93% de falhas de predição em desvios de retorno
Contador bl/ret normal Um único bl, vários ret
BRANCH_RET_INDIR_MISPRED_NONSPECIFIC 92 928.644.975
FETCH_RESTART 61.121 987.765.276
MAP_DISPATCH_BUBBLE 1.155.632 7.350.085.139
MAP_REWIND 6.412.734 2.789.499.545
  • A Apple não documenta completamente esses contadores
  • Os outros contadores são presumidos como efeitos downstream de uma predição de desvios ruim
    • FETCH_RESTART: possivelmente uma busca antecipada incorreta
    • MAP_DISPATCH_BUBBLE: possivelmente relacionado a parada de pipeline
    • MAP_REWIND: possivelmente execução especulativa incorreta que precisa ser revertida

Como deixar mais rápido

  • O exemplo é código didático, e o motivo de foo ser uma sub-rotina também está mais ligado à estrutura explicativa do que a “código o mais rápido possível”
  • Se o conteúdo de foo é conhecido no momento da build e fica abaixo da distância máxima de salto, é possível remover completamente bl e ret e fazer inline
    • Fica cerca de 6% mais rápido, indo de 969 ns para 911 ns
  • Em Rust, simplesmente usar f.iter().sum() reduz para 833 ns
pub fn sum_slice(f: &[f32]) -> f32 {
    f.iter().sum()
}

SIMD e desenrolamento manual de loop

  • A implementação SIMD manual em AArch64 é composta por três loops
    • loop: soma valores individuais em s0 até que a quantidade restante de valores seja múltipla de 4
    • simd: soma 4 valores de uma vez no registrador vetorial v1 e repete até que a quantidade restante de valores seja múltipla de 8
    • simd2: desenrola simd em 2x, processando 8 valores por repetição e acumulando em v1 e v2
  • Ao final da função, acumula os valores de v1 e v2 em s0 e retorna
  • O type punning trata x0, que é float*, como se fosse double*, lendo 128 bits, ou seja, 4 float, em d3 e d4
    • mov v3.d[1], v4.d[0] move os 64 bits de d4 para os 64 bits superiores de v3
    • Em fadd v1.4s, v1.4s, v3.4s, o sufixo .4s faz o tratamento como quatro float
  • Essa implementação SIMD roda em 94 ns, cerca de 8,8 vezes mais rápida que a melhor versão anterior, em Rust, de 833 ns

Resumo geral de desempenho e ressalva

Implementação Tempo
bl/ret normal 969 ns
Um único bl, vários ret 3,85 µs
Um único bl, vários br x30 913 ns
Loop comum usando b 911 ns
Reescrita em Rust 833 ns
SIMD + desenrolamento manual de loop 94 ns
  • O código SIMD muda a ordem das somas de ponto flutuante
  • Como a soma de ponto flutuante não é associativa, a versão SIMD pode não produzir o mesmo resultado que o código linear
  • Esse também pode ser o motivo pelo qual o compilador não gerou instruções SIMD para a soma
  • Todo o código está disponível no GitHub
  • Em uma máquina ARM64, é possível reproduzir o benchmark executando cargo bench

Leituras relacionadas

1 comentários

 
GN⁺ 2024-07-05
Opiniões no Hacker News

  • O último código otimizado soma um array de 1024 números de ponto flutuante de 32 bits em 94 ns.
    Nesse intervalo de 94 ns, o velho amigo 6502 de 1 MHz provavelmente ainda estaria começando a pensar se sinalizaria ao chip de memória para buscar o primeiro byte da primeira instrução do programa.
    Só que esse código depende inteiramente da premissa de que roda dentro do cache. Caso contrário, até o poderoso M1 Max citado no artigo teria ficado parado esperando a primeira busca na memória. DRAM é lenta

    • Agora temos a sorte de o tamanho total do cache L1 ter ficado tão grande quanto toda a memória que o 6502 conseguia endereçar. Vivemos mesmo em tempos incríveis

  • Raymond Chen tratou do mesmo assunto quase 20 anos atrás: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...

    • Como alguém que tem a referência de instruções da arquitetura x86/64 da Intel em papel, os chamados grossos livros azuis, e que lê datasheets e documentação com cuidado, eu sempre fico cauteloso quando ouço “intuitivamente parece que seria X, mas acontece Y”.
      Tirando uma compreensão básica das propriedades semicondutoras do silício e de dopagem, quase nada aqui é intuitivo. Se você não viu o diagrama do die, o roteamento e os caminhos, há pouquíssimo motivo para esperar que A seja mais rápido que B, a menos que engenheiros e datasheets digam isso explicitamente. Acho que isso vale especialmente para ARM
    • O texto de Raymond Chen é excelente e dá um bom contexto para interpretar este artigo.
      O que este artigo acrescenta é uma correção simples: trocar ret por outra instrução br. Assim, o par volta a ficar “simétrico”, e é possível obter um código um pouco mais rápido sem quebrar o preditor de desvios
    • Raymond Chen é realmente um tesouro. Sou grato que a Microsoft lhe dê autonomia para continuar escrevendo no blog; aprendi muito ali
    • Em processadores x86 recentes, parece que isso já não é mais verdade: https://news.ycombinator.com/item?id=40767676

  • Claro que qualquer coisa é possível, e um loop comum para somar um array de fato instrui o computador a acumular os elementos um por um.
    Mas, por exemplo, é difícil dizer que criar quatro acumuladores em paralelo com SIMD e somá-los no fim seja mais errado do que somar os elementos um por um.
    A soma de ponto flutuante deve ser vista, basicamente, como tendo uma margem de erro, e qualquer resposta dentro dessa margem deveria ser válida. Se você souber algo especial sobre os pontos flutuantes de entrada, a linguagem deveria dar um meio de expressar explicitamente essa intenção. Como o loop mais básico é o padrão, acho que por padrão ele deveria oferecer o melhor desempenho

    • Mesmo para uma tarefa simples como somar uma lista de números, existe uma quantidade surpreendente de algoritmos de soma.
      A abordagem ingênua de somar um a um no loop é obvious, mas há métodos mais sofisticados que dão limites melhores para o erro acumulado total, e a soma de Kahan é um exemplo conhecido: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
      Se forem dados em streaming, talvez só dê para somar um por um, mas, se for possível usar N buffers de tamanho fixo, surgem questões como qual subconjunto transformar em soma parcial quando um novo número chega, como adicioná-lo ao acumulado e se essa escolha tem uma melhora de erro demonstrável
    • Quando há uma grande diferença de magnitude entre valores de ponto flutuante, isso vira um problema sério.
      Por exemplo, calcular [1e50, -1e50, 1e3, 1e3] como (((1e50 + -1e50) + 1e3) + 1e3) dá 2e3, mas calcular como ((1e50 + 1e3) + (-1e50 + 1e3)) dá 0.
      Algo parecido acontece ao somar muitos valores pequenos a um valor grande: (((1e3 + 1e3) + 1e3) ... + 1e50) e (((1e50 + 1e3) + 1e3) ... + 1e3) são bem diferentes
    • Há muitos “deveria”, mas na prática quase nunca é assim. A única informação fornecida pela expressão original é a ordem das operações aritméticas.
      Se os resultados aritméticos não forem estáveis entre builds, isso vira um pesadelo completo. Não deveria acontecer de recompilar e executar o software com a mesma entrada e obter um resultado diferente.
      Também já passei por um caso antigo específico da Intel: a FPU usava internamente registradores de 80 bits e a memória usava 64 bits, então, quando o momento de preencher/esvaziar registradores mudava, o momento de arredondamento também mudava e o resultado ficava diferente. Era possível definir uma flag global da FPU no início do programa para forçar arredondamento a cada operação
    • Ordenar valores de ponto flutuante reduz o erro. Por isso, acho que usar vários acumuladores pode reduzir a precisão. Dados ordenados também não são raros.
      Sempre há uma resposta correta, e acho que o compilador não deveria fazer, ao menos por padrão, uma alteração incorreta. Ainda assim, formas de o programador expressar melhor a intenção são sempre bem-vindas
    • Muito código depende de as operações de ponto flutuante serem determinísticas dentro de uma arquitetura de conjunto de instruções específica.
      Aplicar SIMD a loops de ponto flutuante poderia ter virado o padrão, mas quebraria muito código existente e faria a saída mudar com frequência de forma não determinística, então virou um recurso que o programador precisa escolher explicitamente.
      Além disso, muitos programadores podem não saber disso, então, se float Sum(float[] values) começar a retornar um valor diferente, talvez não tenham como saber que a causa é a vetorização. Por isso, por exemplo, a biblioteca padrão do .NET usa SIMD em integers.Sum(), mas não em floats.Sum()

  • Só de ler a linha “depois de verificar o fim do loop, cai direto para dentro da função foo sem um desvio”, pensei: “ah, então esse é o problema”
    Achei que seria uma discussão profunda sobre heurísticas chamativas de preditor de desvios, mas no fim era uma violação de uma heurística básica
    Não dá para achar que se pode obter um enorme ganho de velocidade usando instruções call/ret que não combinam. Preditores de desvio mantêm uma pilha-sombra de endereços de retorno há décadas

    • Entender bem como um preditor de desvios funciona é bom, mas muita gente não entende, e para essas pessoas isso pode ser uma informação nova e talvez útil. Este texto simplesmente não era para você, e tudo bem
    • Em sistemas que têm uma pilha-sombra de chamadas em nível de arquitetura como recurso de segurança, isso pode quebrar a execução do programa de forma mais fundamental, ou seja, causar um crash
    • Por um lado, o objetivo de projeto do RISC é aumentar o desempenho do código compilado, sacrificando a maioria dos outros fatores
      Portanto esse tipo de risco deve ser documentado, mas os projetistas devem poder presumir que quem escreve assembly diretamente leu a documentação
      Por outro lado, Sophie Wilson escreveu a implementação original do BBC BASIC para ARM, mas naquela época não havia preditor de desvios. Embora as regras sejam diferentes por ser 32 bits, fico curioso sobre como o AArch64 torna o código mais lento quando as premissas arquiteturais mudam
    • Ainda assim, é um texto útil, pois também mostrou como essas e outras otimizações foram de fato alcançadas

  • É uma referência ao clássico do SNL “Do not taunt happy fun ball”: https://www.youtube.com/watch?v=GmqeZl8OI2M

    • Se o happy fun preditor de desvios começar a soltar fumaça, você deve evacuar imediatamente
    • A frase “Happy Fun Ball foi enviado para nossos soldados na Arábia Saudita e também está sendo lançado de caças sobre o Iraque” dá uma sensação de “em que ano estamos, afinal!?”
    • Ainda é legal em 16 estados: https://www.youtube.com/watch?v=2AzAFqrxfeY

  • Não se deve deixar passar que o texto é de 2023. Hoje ele já está um pouco datado, e desde o Rust 1.78 o compilador usa desenrolamento de loop mais agressivo e um pouco de SIMD: https://godbolt.org/z/zhbobW7rr
    O texto original dizia “olhando o assembly, ele está desenrolando o loop” e linkava https://godbolt.org/z/Kv77abW6c, mas estava usando o “Rust Nightly”, que muda continuamente. Hoje há mais desenrolamento de loop
    O desenrolamento de loop começou no Rust 1.59: https://godbolt.org/z/5PTnWrWf7
    Pelo código no GitHub, ele estava usando Rust 1.67.0-nightly, versão de 2022-11-27

    • Atualizei o link para selecionar explicitamente o Rust 1.67
    • O Rust 1.67.0 que o texto original parece ter visto produz este resultado: https://godbolt.org/z/4Y61d9seh
      Rodei eu mesmo o benchmark no mesmo hardware com o desenrolamento de loop agressivo do Rust 1.81 nightly mais recente, mas não houve diferença; a velocidade foi a mesma de 1,5 ano atrás

  • É um texto de 2023. Discussão da época: https://news.ycombinator.com/item?id=34520498

    • Para detalhar, é a discussão de janeiro de 2023 de “Do not taunt happy fun branch predictor”, com 171 comentários: https://news.ycombinator.com/item?id=34520498
      Repostar cerca de um ano depois não tem problema, e o link para a thread antiga é para leitores que quiserem saber mais

  • Como não sou muito familiarizado com assembly ARM/ARM64, fiquei confuso sobre como x0 é incrementado
    const float f = *data++; vira ldr s1, [x0], #4, e essa instrução parece ler o valor e, ao mesmo tempo, incrementar x0 em 4
    Parece que também dá para usar valores negativos, então deve ser possível percorrer no sentido inverso. Bem legal. No x86_64, acho que não há uma instrução única que leia e incremente ao mesmo tempo

    • lods e stos fazem, respectivamente, leitura/escrita e incremento sobre rsi ou rdi. Também há movs, que copia entre dois endereços de memória enquanto incrementa
      Normalmente é usado junto com rep, que repete rcx vezes. Por exemplo, um memset de 10 bytes pode ser feito como mov rcx, 10, mov rdi, dest, mov rax, 0, rep stosb
      Usando os sufixos w, d, q, avança-se respectivamente 2, 4 e 8 bytes

  • O texto foi bom, mas achei ruim ele ficar alternando entre unidades de µs e ns, dificultando passar os olhos pela tabela e comparar

    • Também foi um pouco desconcertante a troca de C para Rust no meio do texto

  • É surpreendente que não tenham tentado primeiro uma abordagem menos esperta antes de otimizar o código
    Reescrevendo o assembly, só seria necessário um desvio no fim do loop e, para X1, também daria para tratar com uma única operação de ALU, em vez de fazer separadamente a subtração para comparação e o decremento
    Indo mais além, daria simplesmente para inlinear foo e também omitir a instrução RET, sem o truque de BL/RET incompatíveis. Não fiz benchmark direto, então não sei o quanto isso realmente ficaria mais rápido

    • Há um erro de digitação. A linha que diz cbnz deveria ser cbz. CBZ desvia para o rótulo se o registrador for 0, e CBNZ desvia se não for 0