tutorial - use assembly in c++




Por que o GCC gera código de 15-20% mais rápido se eu otimizar o tamanho em vez da velocidade? (4)

Estou adicionando este post-accept para destacar que os efeitos do alinhamento no desempenho geral dos programas - incluindo os grandes - foram estudados. Por exemplo, este artigo (e acredito que uma versão disso também apareceu no CACM) mostra como a ordem dos links e as alterações de tamanho do ambiente OS foram suficientes para alterar significativamente o desempenho. Eles atribuem isso ao alinhamento de "loops quentes".

Este artigo, intitulado "Produzir dados errados sem fazer nada obviamente errado!" diz que o viés experimental inadvertido devido a diferenças quase incontroláveis ​​em ambientes de execução de programas provavelmente torna muitos resultados de benchmark sem sentido.

Eu acho que você está encontrando um ângulo diferente na mesma observação.

Para o código crítico de desempenho, esse é um argumento muito bom para sistemas que avaliam o ambiente na instalação ou no tempo de execução e escolhem o melhor local entre versões otimizadas diferentes de rotinas de chaves.

Eu notei em 2009 que o GCC (pelo menos em meus projetos e em minhas máquinas) tem a tendência de gerar código notavelmente mais rápido se eu otimizar o tamanho ( -Os ) em vez da velocidade ( -O2 ou -O3 ), e eu tenho sido imaginando desde o porquê.

Eu consegui criar um código (bastante bobo) que mostra esse comportamento surpreendente e é suficientemente pequeno para ser postado aqui.

const int LOOP_BOUND = 200000000;

__attribute__((noinline))
static int add(const int& x, const int& y) {
    return x + y;
}

__attribute__((noinline))
static int work(int xval, int yval) {
    int sum(0);
    for (int i=0; i<LOOP_BOUND; ++i) {
        int x(xval+sum);
        int y(yval+sum);
        int z = add(x, y);
        sum += z;
    }
    return sum;
}

int main(int , char* argv[]) {
    int result = work(*argv[1], *argv[2]);
    return result;
}

Se eu compilar com -Os , são necessários 0,38 s para executar este programa e 0,44 s se forem compilados com -O2 ou -O3 . Esses tempos são obtidos consistentemente e praticamente sem ruído (gcc 4.7.2, x86_64 GNU / Linux, Intel Core i5-3320M).

(Atualização: eu mudei todo o código de assembly para o GitHub : eles fizeram o post inchado e, aparentemente, adicionaram muito pouco valor às perguntas, pois os fno-align-* têm o mesmo efeito.)

Aqui está o assembly gerado com -Os e -O2 .

Infelizmente, meu entendimento de assembly é muito limitado, então não tenho idéia se o que fiz em seguida foi correto: peguei o assembly para -O2 e -O2 todas as suas diferenças no assembly para -Os exceto as linhas .p2align , resultado here . Este código ainda é executado em 0.38s e a única diferença é o material .p2align .

Se eu acho que corretamente, esses são preenchimentos para alinhamento de pilha. De acordo com porque o GCC pad funciona com NOPs? isso é feito na esperança de que o código seja executado mais rapidamente, mas aparentemente essa otimização saiu pela culatra no meu caso.

É o preenchimento que é o culpado neste caso? Porquê e como?

O ruído que isso faz praticamente impossibilita as micro-otimizações de temporização.

Como posso ter certeza de que tais alinhamentos de sorte / azar acidental não estão interferindo quando eu faço micro-otimizações (não relacionadas ao alinhamento de pilha) no código-fonte C ou C ++?

ATUALIZAR:

Seguindo a resposta de Pascal Cuoq, mexi um pouco com os alinhamentos. Passando -O2 -fno-align-functions -fno-align-loops para gcc, todos os .p2align do assembly e o executável gerado é executado em 0.38s. De acordo com a documentação do gcc :

-Os ativa todas as otimizações -O2 [mas] -Os desativa os seguintes sinalizadores de otimização:

  -falign-functions  -falign-jumps  -falign-loops <br/>
  -falign-labels  -freorder-blocks  -freorder-blocks-and-partition <br/>
  -fprefetch-loop-arrays <br/>

Então, praticamente parece um problema de (des) alinhamento.

Eu ainda sou cético sobre -march=native como sugerido na resposta de Marat Dukhan . Não estou convencido de que isso não esteja apenas interferindo nesse problema de (des) alinhamento; Não tem absolutamente nenhum efeito na minha máquina. (No entanto, eu votei sua resposta.)

ATUALIZAÇÃO 2:

Nós podemos tirar -Os fora da imagem. Os seguintes horários são obtidos pela compilação com

  • -O2 -fno-omit-frame-pointer 0.37s

  • -O2 -fno-align-functions -fno-align-loops 0,37s

  • -S -O2 então movendo manualmente a montagem de add() depois do work() 0.37s

  • -O2 0,44s

Parece-me que a distância de add() do site de chamadas é muito importante. Eu tentei o perf , mas a saída do perf report e do perf report faz muito pouco sentido para mim. No entanto, só consegui obter um resultado consistente:

-O2 :

 602,312,864 stalled-cycles-frontend   #    0.00% frontend cycles idle
       3,318 cache-misses
 0.432703993 seconds time elapsed
 [...]
 81.23%  a.out  a.out              [.] work(int, int)
 18.50%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦       return x + y;
100.00 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   }
       ¦   ? retq
[...]
       ¦            int z = add(x, y);
  1.93 ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 79.79 ¦      add    %eax,%ebx

Para fno-align-* :

 604,072,552 stalled-cycles-frontend   #    0.00% frontend cycles idle
       9,508 cache-misses
 0.375681928 seconds time elapsed
 [...]
 82.58%  a.out  a.out              [.] work(int, int)
 16.83%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦       return x + y;
 51.59 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   }
[...]
       ¦    __attribute__((noinline))
       ¦    static int work(int xval, int yval) {
       ¦        int sum(0);
       ¦        for (int i=0; i<LOOP_BOUND; ++i) {
       ¦            int x(xval+sum);
  8.20 ¦      lea    0x0(%r13,%rbx,1),%edi
       ¦            int y(yval+sum);
       ¦            int z = add(x, y);
 35.34 ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 39.48 ¦      add    %eax,%ebx
       ¦    }

Para -fno-omit-frame-pointer :

 404,625,639 stalled-cycles-frontend   #    0.00% frontend cycles idle
      10,514 cache-misses
 0.375445137 seconds time elapsed
 [...]
 75.35%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]                                                                                     ¦
 24.46%  a.out  a.out              [.] work(int, int)
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
 18.67 ¦     push   %rbp
       ¦       return x + y;
 18.49 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   const int LOOP_BOUND = 200000000;
       ¦
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦     mov    %rsp,%rbp
       ¦       return x + y;
       ¦   }
 12.71 ¦     pop    %rbp
       ¦   ? retq
 [...]
       ¦            int z = add(x, y);
       ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 29.83 ¦      add    %eax,%ebx

Parece que estamos atrasando a chamada para add() no caso lento.

Eu examinei tudo que o perf -e pode cuspir na minha máquina; não apenas as estatísticas que são dadas acima.

Para o mesmo executável, o stalled-cycles-frontend mostra uma correlação linear com o tempo de execução; Não notei mais nada que se correlacionasse tão claramente. (Comparando stalled-cycles-frontend para diferentes executáveis ​​não faz sentido para mim.)

Eu incluí as falhas de cache, uma vez que surgiu como o primeiro comentário. Eu examinei todas as falhas de cache que podem ser medidas na minha máquina por perf , não apenas as que foram dadas acima. As falhas de cache são muito muito barulhentas e mostram pouca ou nenhuma correlação com os tempos de execução.


Eu acho que você pode obter o mesmo resultado que você fez:

Eu peguei a montagem de -O2 e mesclei todas as suas diferenças na montagem de -Os, exceto as linhas .p2align:

… Usando -O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1 . Eu tenho compilado tudo com essas opções, que foram mais rápidas que o simples -O2 toda vez que me preocupei em medir, por 15 anos.

Além disso, para um contexto completamente diferente (incluindo um compilador diferente), notei que a situação é semelhante : a opção que supostamente “otimiza o tamanho do código em vez da velocidade” otimiza o tamanho e a velocidade do código.

Se eu acho que corretamente, esses são preenchimentos para alinhamento de pilha.

Não, isso não tem nada a ver com a pilha, os NOPs gerados por padrão e as opções -falign - * = 1 prevent são para alinhamento de código.

De acordo com porque o GCC pad funciona com NOPs? isso é feito na esperança de que o código funcione mais rápido, mas aparentemente essa otimização saiu pela culatra no meu caso.

É o preenchimento que é o culpado neste caso? Porquê e como?

É muito provável que o preenchimento seja o culpado. O motivo pelo qual padding é necessário e é útil em alguns casos é que o código é tipicamente buscado em linhas de 16 bytes (veja os recursos de otimização da Agner Fog para os detalhes, que variam de acordo com o modelo do processador). Alinhar uma função, um loop ou um rótulo em um limite de 16 bytes significa que as chances são estatisticamente maiores de que serão necessárias menos linhas para conter a função ou o loop. Obviamente, ele sai pela culatra porque esses NOPs reduzem a densidade do código e, portanto, a eficiência do cache. No caso de loops e label, os NOPs podem até precisar ser executados uma vez (quando a execução chega ao loop / label normalmente, ao contrário de um jump).


Não sou de modo algum um especialista nessa área, mas parece que me lembro de que os processadores modernos são bastante sensíveis quando se trata de predizer ramificações . Os algoritmos usados ​​para prever as ramificações são (ou pelo menos estavam de volta nos dias em que escrevi o código assembler) com base em várias propriedades do código, incluindo a distância de um alvo e na direção.

O cenário que me vem à mente são pequenos loops. Quando o ramo estava indo para trás e a distância não estava muito longe, a predição de ramificação estava otimizando para este caso, já que todos os pequenos loops são feitos dessa maneira. As mesmas regras podem entrar em work quando você troca o local de add e work no código gerado ou quando a posição de ambos muda ligeiramente.

Dito isso, não tenho ideia de como verificar isso e só queria que você soubesse que isso pode ser algo que você quer investigar.


Por padrão, os compiladores otimizam o processador "médio". Como processadores diferentes favorecem sequências de instrução diferentes, as otimizações de compilador ativadas por -O2 podem beneficiar o processador médio, mas diminuir o desempenho em seu processador específico (e o mesmo se aplica a -Os ). Se você tentar o mesmo exemplo em processadores diferentes, verá que em alguns deles se beneficia de -O2 enquanto outros são mais favoráveis ​​às otimizações -Os .

Aqui estão os resultados para o time ./test 0 0 em vários processadores (tempo de usuário relatado):

Processor (System-on-Chip)             Compiler   Time (-O2)  Time (-Os)  Fastest
AMD Opteron 8350                       gcc-4.8.1    0.704s      0.896s      -O2
AMD FX-6300                            gcc-4.8.1    0.392s      0.340s      -Os
AMD E2-1800                            gcc-4.7.2    0.740s      0.832s      -O2
Intel Xeon E5405                       gcc-4.8.1    0.603s      0.804s      -O2
Intel Xeon E5-2603                     gcc-4.4.7    1.121s      1.122s       -
Intel Core i3-3217U                    gcc-4.6.4    0.709s      0.709s       -
Intel Core i3-3217U                    gcc-4.7.3    0.708s      0.822s      -O2
Intel Core i3-3217U                    gcc-4.8.1    0.708s      0.944s      -O2
Intel Core i7-4770K                    gcc-4.8.1    0.296s      0.288s      -Os
Intel Atom 330                         gcc-4.8.1    2.003s      2.007s      -O2
ARM 1176JZF-S (Broadcom BCM2835)       gcc-4.6.3    3.470s      3.480s      -O2
ARM Cortex-A8 (TI OMAP DM3730)         gcc-4.6.3    2.727s      2.727s       -
ARM Cortex-A9 (TI OMAP 4460)           gcc-4.6.3    1.648s      1.648s       -
ARM Cortex-A9 (Samsung Exynos 4412)    gcc-4.6.3    1.250s      1.250s       -
ARM Cortex-A15 (Samsung Exynos 5250)   gcc-4.7.2    0.700s      0.700s       -
Qualcomm Snapdragon APQ8060A           gcc-4.8       1.53s       1.52s      -Os

Em alguns casos, você pode aliviar o efeito de otimizações desvantajosas pedindo ao gcc para otimizar seu processador em particular (usando as opções -mtune=native ou -march=native ):

Processor            Compiler   Time (-O2 -mtune=native) Time (-Os -mtune=native)
AMD FX-6300          gcc-4.8.1         0.340s                   0.340s
AMD E2-1800          gcc-4.7.2         0.740s                   0.832s
Intel Xeon E5405     gcc-4.8.1         0.603s                   0.803s
Intel Core i7-4770K  gcc-4.8.1         0.296s                   0.288s

Atualização: no Core i3 baseado em Ivy Bridge, três versões do gcc ( 4.6.4 , 4.7.3 e 4.8.1 ) produzem binários com desempenho significativamente diferente, mas o código de montagem tem apenas variações sutis. Até agora, não tenho explicação para esse fato.

Montagem do gcc-4.6.4 -Os (executa em 0.709 segundos):

00000000004004d2 <_ZL3addRKiS0_.isra.0>:
  4004d2:       8d 04 37                lea    eax,[rdi+rsi*1]
  4004d5:       c3                      ret

00000000004004d6 <_ZL4workii>:
  4004d6:       41 55                   push   r13
  4004d8:       41 89 fd                mov    r13d,edi
  4004db:       41 54                   push   r12
  4004dd:       41 89 f4                mov    r12d,esi
  4004e0:       55                      push   rbp
  4004e1:       bd 00 c2 eb 0b          mov    ebp,0xbebc200
  4004e6:       53                      push   rbx
  4004e7:       31 db                   xor    ebx,ebx
  4004e9:       41 8d 34 1c             lea    esi,[r12+rbx*1]
  4004ed:       41 8d 7c 1d 00          lea    edi,[r13+rbx*1+0x0]
  4004f2:       e8 db ff ff ff          call   4004d2 <_ZL3addRKiS0_.isra.0>
  4004f7:       01 c3                   add    ebx,eax
  4004f9:       ff cd                   dec    ebp
  4004fb:       75 ec                   jne    4004e9 <_ZL4workii+0x13>
  4004fd:       89 d8                   mov    eax,ebx
  4004ff:       5b                      pop    rbx
  400500:       5d                      pop    rbp
  400501:       41 5c                   pop    r12
  400503:       41 5d                   pop    r13
  400505:       c3                      ret

Montagem do gcc-4.7.3 -Os (executa em 0.822 seg):

00000000004004fa <_ZL3addRKiS0_.isra.0>:
  4004fa:       8d 04 37                lea    eax,[rdi+rsi*1]
  4004fd:       c3                      ret

00000000004004fe <_ZL4workii>:
  4004fe:       41 55                   push   r13
  400500:       41 89 f5                mov    r13d,esi
  400503:       41 54                   push   r12
  400505:       41 89 fc                mov    r12d,edi
  400508:       55                      push   rbp
  400509:       bd 00 c2 eb 0b          mov    ebp,0xbebc200
  40050e:       53                      push   rbx
  40050f:       31 db                   xor    ebx,ebx
  400511:       41 8d 74 1d 00          lea    esi,[r13+rbx*1+0x0]
  400516:       41 8d 3c 1c             lea    edi,[r12+rbx*1]
  40051a:       e8 db ff ff ff          call   4004fa <_ZL3addRKiS0_.isra.0>
  40051f:       01 c3                   add    ebx,eax
  400521:       ff cd                   dec    ebp
  400523:       75 ec                   jne    400511 <_ZL4workii+0x13>
  400525:       89 d8                   mov    eax,ebx
  400527:       5b                      pop    rbx
  400528:       5d                      pop    rbp
  400529:       41 5c                   pop    r12
  40052b:       41 5d                   pop    r13
  40052d:       c3                      ret

Montagem do gcc-4.8.1 -Os (executado em 0.994 segundos):

00000000004004fd <_ZL3addRKiS0_.isra.0>:
  4004fd:       8d 04 37                lea    eax,[rdi+rsi*1]
  400500:       c3                      ret

0000000000400501 <_ZL4workii>:
  400501:       41 55                   push   r13
  400503:       41 89 f5                mov    r13d,esi
  400506:       41 54                   push   r12
  400508:       41 89 fc                mov    r12d,edi
  40050b:       55                      push   rbp
  40050c:       bd 00 c2 eb 0b          mov    ebp,0xbebc200
  400511:       53                      push   rbx
  400512:       31 db                   xor    ebx,ebx
  400514:       41 8d 74 1d 00          lea    esi,[r13+rbx*1+0x0]
  400519:       41 8d 3c 1c             lea    edi,[r12+rbx*1]
  40051d:       e8 db ff ff ff          call   4004fd <_ZL3addRKiS0_.isra.0>
  400522:       01 c3                   add    ebx,eax
  400524:       ff cd                   dec    ebp
  400526:       75 ec                   jne    400514 <_ZL4workii+0x13>
  400528:       89 d8                   mov    eax,ebx
  40052a:       5b                      pop    rbx
  40052b:       5d                      pop    rbp
  40052c:       41 5c                   pop    r12
  40052e:       41 5d                   pop    r13
  400530:       c3                      ret




assembly