Por que a introdução de instruções MOV inúteis aceleraria um loop apertado na montagem x86_64?

Fundo:

Ao otimizar algum código Pascal com linguagem assembly incorporada, notei uma MOVinstrução desnecessária e a removi.

Para minha surpresa, remover as instruções desnecessárias fez com que meu programa desacelerasse .

Descobri que adicionar MOVinstruções arbitrárias e inúteis aumentava ainda mais o desempenho .

O efeito é irregular e as alterações são baseadas na ordem de execução: as mesmas instruções indesejadas transpostas para cima ou para baixo por uma única linha produzem uma desaceleração .

Entendo que a CPU faz todos os tipos de otimizações e racionalizações, mas isso parece mais magia negra.

Os dados:

Uma versão do meu código compila condicionalmente três operações indesejadas no meio de um loop que executa 2**20==1048576vezes. (O programa circundante apenas calcula os hashes SHA-256 ).

Os resultados na minha máquina bastante antiga (CPU Intel (R) Core (TM) 2) 6400 a 2,13 GHz):

avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without:        1836.44 ms

Os programas foram executados 25 vezes em um loop, com a ordem de execução mudando aleatoriamente a cada vez.

Excerto:

{$asmmode intel}
procedure example_junkop_in_sha256;
  var s1, t2 : uint32;
  begin
    // Here are parts of the SHA-256 algorithm, in Pascal:
    // s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
    // s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
    // Here is how I translated them (side by side to show symmetry):
  asm
    MOV r8d, a                 ; MOV r9d, e
    ROR r8d, 2                 ; ROR r9d, 6
    MOV r10d, r8d              ; MOV r11d, r9d
    ROR r8d, 11    {13 total}  ; ROR r9d, 5     {11 total}
    XOR r10d, r8d              ; XOR r11d, r9d
    ROR r8d, 9     {22 total}  ; ROR r9d, 14    {25 total}
    XOR r10d, r8d              ; XOR r11d, r9d

    // Here is the extraneous operation that I removed, causing a speedup
    // s1 is the uint32 variable declared at the start of the Pascal code.
    //
    // I had cleaned up the code, so I no longer needed this variable, and 
    // could just leave the value sitting in the r11d register until I needed
    // it again later.
    //
    // Since copying to RAM seemed like a waste, I removed the instruction, 
    // only to discover that the code ran slower without it.
    {$IFDEF JUNKOPS}
    MOV s1,  r11d
    {$ENDIF}

    // The next part of the code just moves on to another part of SHA-256,
    // maj { r12d } := (a and b) xor (a and c) xor (b and c)
    mov r8d,  a
    mov r9d,  b
    mov r13d, r9d // Set aside a copy of b
    and r9d,  r8d

    mov r12d, c
    and r8d, r12d  { a and c }
    xor r9d, r8d

    and r12d, r13d { c and b }
    xor r12d, r9d

    // Copying the calculated value to the same s1 variable is another speedup.
    // As far as I can tell, it doesn't actually matter what register is copied,
    // but moving this line up or down makes a huge difference.
    {$IFDEF JUNKOPS}
    MOV s1,  r9d // after mov r12d, c
    {$ENDIF}

    // And here is where the two calculated values above are actually used:
    // T2 {r12d} := S0 {r10d} + Maj {r12d};
    ADD r12d, r10d
    MOV T2, r12d

  end
end;

Tente você mesmo:

O código está online no GitHub, se você quiser experimentá-lo.

Minhas perguntas:

• Por que copiar inutilmente o conteúdo de um registro para a RAM aumentaria o desempenho?
• Por que a mesma instrução inútil forneceria uma aceleração em algumas linhas e uma desaceleração em outras?
• Esse comportamento é algo que poderia ser explorado previsivelmente por um compilador?

A causa mais provável da melhoria da velocidade é que:

• inserir um MOV muda as instruções subseqüentes para diferentes endereços de memória
• uma dessas instruções movidas era um ramo condicional importante
• que a ramificação estava sendo prevista incorretamente devido ao alias na tabela de previsão da ramificação
• mover a ramificação eliminou o alias e permitiu que a ramificação fosse prevista corretamente

Seu Core2 não mantém um registro de histórico separado para cada salto condicional. Em vez disso, mantém um histórico compartilhado de todos os saltos condicionais. Uma desvantagem da previsão global de ramificação é que o histórico é diluído por informações irrelevantes se os diferentes saltos condicionais não forem correlacionados.

Este pequeno tutorial de previsão de ramificação mostra como os buffers de previsão de ramificação funcionam. O buffer do cache é indexado pela parte inferior do endereço da instrução de ramificação. Isso funciona bem, a menos que dois ramos não correlacionados importantes compartilhem os mesmos bits inferiores. Nesse caso, você acaba com o alias, o que causa muitas ramificações imprevisíveis (que paralisam o pipeline de instruções e tornam o programa mais lento).

Se você quiser entender como as previsões incorretas de ramificações afetam o desempenho, consulte esta excelente resposta: https://stackoverflow.com/a/11227902/1001643

Os compiladores normalmente não têm informações suficientes para saber quais ramificações terão o alias e se esses alias serão significativos. No entanto, essas informações podem ser determinadas em tempo de execução com ferramentas como Cachegrind e VTune .

Você pode ler http://research.google.com/pubs/pub37077.html

TL; DR: a inserção aleatória de instruções nop em programas pode aumentar facilmente o desempenho em 5% ou mais, e não, os compiladores não podem explorar isso facilmente. Geralmente, é uma combinação do preditor de ramificação e do comportamento do cache, mas também pode ser, por exemplo, uma paralisação da estação de reserva (mesmo que não haja cadeias de dependência quebradas ou que haja excesso de assinaturas óbvias de recursos).

Acredito nas CPUs modernas que as instruções de montagem, embora sejam a última camada visível para um programador por fornecer instruções de execução a uma CPU, na verdade são várias camadas da execução real pela CPU.

As CPUs modernas são híbridas RISC / CISC que convertem instruções CISC x86 em instruções internas com comportamento mais RISC. Além disso, existem analisadores de execução fora de ordem, preditores de ramificação, a "fusão de micro-operações" da Intel que tenta agrupar instruções em lotes maiores de trabalho simultâneo (como o titânio do VLIW / Itanium ). Existem até limites de cache que podem tornar o código mais rápido para quem sabe porque é maior (talvez o controlador de cache o encaixe de maneira mais inteligente ou o mantenha por mais tempo).

O CISC sempre teve uma camada de conversão de assembly para microcódigo, mas o ponto é que, com as CPUs modernas, as coisas são muito mais complicadas. Com todo o espaço extra dos transistores nas modernas fábricas de semicondutores, as CPUs provavelmente podem aplicar várias abordagens de otimização em paralelo e, em seguida, selecionar aquela no final que forneça a melhor aceleração. As instruções extras podem influenciar a CPU a usar um caminho de otimização melhor que outros.

O efeito das instruções extras provavelmente depende do modelo / geração / fabricante da CPU e provavelmente não é previsível. A otimização da linguagem assembly dessa maneira exigiria execução em várias gerações da arquitetura da CPU, talvez usando caminhos de execução específicos da CPU, e seria desejável apenas para seções de código realmente importantes, embora, se você estiver fazendo montagem, provavelmente já saiba disso.

Preparando o cache

As operações de movimentação para a memória podem preparar o cache e agilizar as operações de movimentação subsequentes. Uma CPU geralmente possui duas unidades de carga e uma unidade de armazenamento. Uma unidade de carregamento pode ler da memória em um registro (uma leitura por ciclo), uma unidade de armazenamento armazena do registro na memória. Existem também outras unidades que fazem operações entre registradores. Todas as unidades funcionam em paralelo. Portanto, em cada ciclo, podemos realizar várias operações ao mesmo tempo, mas não mais que duas cargas, uma loja e várias operações de registro. Geralmente, são 4 operações simples com registros simples, até 3 operações simples com registros XMM / YMM e 1-2 operações complexas com qualquer tipo de registro. Seu código possui muitas operações com registradores; portanto, uma operação de armazenamento de memória fictícia é gratuita (já que existem mais de quatro operações de registro), mas prepara o cache de memória para a operação de armazenamento subsequente. Para descobrir como as lojas de memória funcionam, consulte oManual de referência da otimização de arquiteturas Intel 64 e IA-32 .

Quebrando as dependências falsas

Embora isso não se refira exatamente ao seu caso, mas às vezes usando operações mov de 32 bits no processador de 64 bits (como no seu caso) são usadas para limpar os bits mais altos (32-63) e interromper as cadeias de dependência.

É sabido que em x86-64, o uso de operandos de 32 bits limpa os bits mais altos do registro de 64 bits. Por favor, leia a seção relevante - 3.4.1.1 - do Manual do desenvolvedor de software das arquiteturas Intel® 64 e IA-32, Volume 1 :

Operandos de 32 bits geram um resultado de 32 bits, estendido de zero a um resultado de 64 bits no registro de uso geral de destino

Portanto, as instruções mov, que podem parecer inúteis à primeira vista, limpam os bits mais altos dos registros apropriados. O que isso nos dá? Ele quebra as cadeias de dependência e permite que as instruções sejam executadas em paralelo, em ordem aleatória, pelo algoritmo Out-of-Order implementado internamente pelas CPUs desde o Pentium Pro em 1995.

Uma citação do Manual de referência da otimização de arquiteturas Intel® 64 e IA-32 , Seção 3.5.1.8:

As seqüências de código que modificam o registro parcial podem sofrer algum atraso em sua cadeia de dependência, mas podem ser evitadas usando os idiomas de quebra de dependência. Nos processadores baseados na microarquitetura Intel Core, várias instruções podem ajudar a limpar a dependência da execução quando o software as usa para limpar o conteúdo do registro para zero. Quebre as dependências de partes dos registros entre instruções, operando em registros de 32 bits em vez de registros parciais. Para jogadas, isso pode ser realizado com jogadas de 32 bits ou usando o MOVZX.

Regra de codificação do conjunto / compilador 37. (impacto M, generalidade MH) : Quebre dependências de partes dos registros entre as instruções, operando em registros de 32 bits em vez de registros parciais. Para jogadas, isso pode ser realizado com jogadas de 32 bits ou usando o MOVZX.

O MOVZX e o MOV com operandos de 32 bits para x64 são equivalentes - todos eles quebram as cadeias de dependência.

É por isso que seu código é executado mais rapidamente. Se não houver dependências, a CPU pode renomear internamente os registradores, embora à primeira vista possa parecer que a segunda instrução modifique um registro usado pela primeira instrução e as duas não possam ser executadas em paralelo. Mas, devido ao registro de renomeação, eles podem.

A renomeação de registradores é uma técnica usada internamente por uma CPU que elimina as dependências de dados falsos decorrentes da reutilização de registradores por instruções sucessivas que não possuem nenhuma dependência real de dados entre eles.

Eu acho que agora você vê que é óbvio demais.