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

222

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?
tempestade tangente
fonte
7
Existem todos os tipos de instruções "inúteis" que podem realmente servir para quebrar cadeias de dependência, marcar registros físicos como aposentados etc. A exploração dessas operações requer algum conhecimento da microarquitetura . Sua pergunta deve fornecer uma curta sequência de instruções como um exemplo mínimo, em vez de direcionar as pessoas ao github.
Brett Hale
1
@BrettHale bom ponto, obrigado. Eu adicionei um trecho de código com alguns comentários. Copiar o valor de um registro para ram marcaria o registro como aposentado, mesmo que o valor nele seja usado posteriormente?
27513
9
Você pode colocar o desvio padrão nessas médias? Não há nenhuma indicação real neste post de que haja uma diferença real.
starwed
2
Você pode tentar cronometrar as instruções usando a instrução rdtscp e verificar os ciclos do relógio para ambas as versões?
Jakobbotsch
2
Também pode ser devido ao alinhamento da memória? Eu não fiz a matemática me (preguiçoso: P), mas acrescentando algumas instruções manequim pode causar o seu código não ser memória alinhado ...
Lorenzo DEMATTÊ

Respostas:

144

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 .

Raymond Hettinger
fonte
2
Hmm. Isso parece promissor. As únicas ramificações condicionais nessa implementação sha256 são as verificações para o final dos loops FOR. Na época, eu tinha marcado essa revisão como uma singularidade no git e continuei otimizando. Um dos meus próximos passos foi reescrever o loop pascal FOR na montagem, quando essas instruções extras não tiveram mais um efeito positivo. Talvez o código gerado pelo pascal livre fosse mais difícil de prever pelo processador do que o contador simples com o qual eu o substitui.
tangentstorm
1
@ tangentstorm Isso soa como um bom resumo. A tabela de previsão de ramificação não é muito grande; portanto, uma entrada da tabela pode se referir a mais de uma ramificação. Isso pode tornar inúteis algumas previsões. O problema é facilmente resolvido se uma das ramificações conflitantes for movida para outra parte da tabela. Quase qualquer pequena mudança pode fazer isso acontecer :-)
Raymond Hettinger
1
Penso que esta é a explicação mais razoável do comportamento específico que observei, por isso vou marcar isso como resposta. Obrigado. :)
tangentstorm
3
Há um absolutamente excelente discussão sobre um problema semelhante dos contribuintes para Bochs correu para, você pode querer adicionar esta a sua resposta: emulators.com/docs/nx25_nostradamus.htm
Leander
3
O alinhamento do Insn é muito mais importante do que apenas as metas de ramificação. Os gargalos de decodificação são um grande problema para o Core2 e o Nehalem: geralmente é difícil manter as unidades de execução ocupadas. A introdução de Sandybridge do cache uop aumentou bastante o rendimento do front-end. O alinhamento de destinos de ramificação é feito devido a esse problema, mas afeta todo o código.
27568 Peter Panes
80

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).

Jonas Maebe
fonte
1
Interessante. Mas o processador (ou FPC) é inteligente o suficiente para ver que gravar em RAM é um NOP nesse caso?
tangentstorm
8
Assembler não é otimizado.
Marco van de Voort 27/07/2013
5
Os compiladores poderiam explorá-lo fazendo otimizações incrivelmente caras, como criar e criar perfis repetidamente e depois variar a saída do compilador com um algoritmo genético ou de recozimento simulado. Eu li sobre alguns trabalhos nessa área. Mas estamos falando de um mínimo de 5 a 10 minutos de 100% da CPU para compilar, e as otimizações resultantes provavelmente seriam o modelo do núcleo da CPU e até a revisão do núcleo ou do microcódigo.
AdamIerymenko
Eu não chamaria isso de NOP aleatório, eles explicam por que os NOPs podem ter um efeito positivo no desempenho (tl; dr: stackoverflow.com/a/5901856/357198 ) e a inserção aleatória do NOP resultou na degradação do desempenho. O interessante do artigo é que a remoção do NOP 'estratégico' pelo GCC não teve efeito no desempenho geral!
PuercoPop
15

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.

cowarldlydragon
fonte
6
Sua resposta é meio confusa. Em muitos lugares, parece que você está adivinhando, embora a maioria do que você diz esteja correta.
alcuadrado 27/07
2
Talvez eu deva esclarecer. O que acham confusa é a falta de certeza
alcuadrado
3
adivinhar que faz sentido e com boa argumentação é completamente válido.
Jturolla
7
Ninguém pode realmente saber com certeza por que o OP está observando esse comportamento estranho, a menos que um engenheiro da Intel tenha acesso a equipamentos de diagnóstico especiais. Então, tudo o que os outros podem fazer é adivinhar. Isso não é culpa de @ cowarldlydragon.
Alex D
2
Downvote; nada do que você diz explica o comportamento que o OP está vendo. Sua resposta é inútil.
fuz
0

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.

Maxim Masiutin
fonte
Tudo isso é verdade, mas não tem nada a ver com o código apresentado na pergunta.
Cody Gray
@CodyGray - obrigado pelo seu feedback. Editei a resposta e adicionei um capítulo sobre o caso - que mover para a memória cercado por operações de registro prepara o cache e é gratuito, pois a unidade de armazenamento está ociosa de qualquer maneira. Portanto, a operação subsequente da loja será mais rápida.
Maxim Masiutin