Percebi pela primeira vez em 2009 que o GCC (pelo menos em meus projetos e em minhas máquinas) tem a tendência de gerar código visivelmente mais rápido se otimizar para tamanho ( -Os) em vez de velocidade ( -O2ou -O3), e fico pensando desde então.
Eu consegui criar 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 for compilado com -O2ou -O3. Esses tempos são obtidos de forma consistente e praticamente sem ruído (gcc 4.7.2, x86_64 GNU / Linux, Intel Core i5-3320M).
(Atualização: Mudei todo o código do assembly para o GitHub : Eles deixaram o post inchado e aparentemente agregam muito pouco valor às perguntas, pois os fno-align-*sinalizadores têm o mesmo efeito.)
Aqui está a montagem gerada com -Ose -O2.
Infelizmente, meu entendimento de montagem é muito limitado, então não tenho idéia se o que fiz a seguir foi correto: peguei a montagem -O2e mesclei todas as suas diferenças na montagem, -Os exceto pelas .p2alignlinhas, resultado aqui . Esse código ainda é executado em 0,38s e a única diferença é o .p2align material.
Se eu acho corretamente, esses são os preenchimentos para o alinhamento da pilha. De acordo com Por que o GCC pad funciona com os 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 produzido praticamente impossibilita micro otimizações de temporização.
Como garantir que esses alinhamentos acidentais de sorte / azar não interfiram quando 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 nos alinhamentos. Ao passar -O2 -fno-align-functions -fno-align-loopspara o gcc, todos .p2alignsaem do assembly e o executável gerado é executado em 0,38s. De acordo com a documentação do gcc :
-Os habilita todas as otimizações de -O2 [mas] -Os desabilita os seguintes sinalizadores de otimização:
-falign-functions -falign-jumps -falign-loops -falign-labels -freorder-blocks -freorder-blocks-and-partition -fprefetch-loop-arrays
Portanto, parece um problema de (des) alinhamento.
Ainda estou cético -march=nativequanto ao sugerido na resposta de Marat Dukhan . Não estou convencido de que não esteja apenas interferindo nesse problema de (des) alinhamento; não tem absolutamente nenhum efeito na minha máquina. (No entanto, votei na resposta dele.)
ATUALIZAÇÃO 2:
Podemos tirar -Osa foto. Os seguintes tempos são obtidos através da compilação com
-O2 -fno-omit-frame-pointer0,37s-O2 -fno-align-functions -fno-align-loops0,37s-S -O2movendo manualmente a montagemadd()apóswork()0,37s-O20.44s
Parece-me que a distância do add()local da chamada é muito importante. Eu tentei perf, mas a saída perf state perf reportfaz 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,%ebxPara 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,%ebxParece que estamos paralisando a chamada add()no caso lento.
Examinei tudo o que perf -epode cuspir na minha máquina; não apenas as estatísticas fornecidas acima.
Para o mesmo executável, o stalled-cycles-frontendmostra correlação linear com o tempo de execução; Não notei mais nada que se correlacionasse tão claramente. (Comparar stalled-cycles-frontendpara diferentes executáveis não faz sentido para mim.)
Incluí as falhas de cache quando surgiram como o primeiro comentário. Examinei todas as falhas de cache que podem ser medidas na minha máquina perf, não apenas as fornecidas acima. As falhas de cache são muito barulhentas e mostram pouca ou nenhuma correlação com os tempos de execução.
Respostas:
Por padrão, os compiladores otimizam para o processador "médio". Como processadores diferentes favorecem sequências de instruções diferentes, as otimizações do compilador ativadas
-O2podem beneficiar o processador médio, mas diminuem o desempenho do seu processador específico (e o mesmo se aplica a-Os). Se você tentar o mesmo exemplo em diferentes processadores, descobrirá que alguns deles se beneficiam-O2enquanto outros são mais favoráveis às-Osotimizações.Aqui estão os resultados para
time ./test 0 0vários processadores (horário do usuário relatado):Em alguns casos, você pode aliviar o efeito de otimizações desvantajosas solicitando
gcca otimização para seu processador específico (usando as opções-mtune=nativeou-march=native):Atualização: no Core i3 do Ivy Bridge, três versões de
gcc(4.6.4,4.7.3e4.8.1) produzem binários com desempenho significativamente diferente, mas o código de montagem possui apenas variações sutis. Até agora, não tenho explicação para esse fato.Montagem de
gcc-4.6.4 -Os(executa em 0,709 segundos):Montagem de
gcc-4.7.3 -Os(executa em 0,822 segundos):Montagem de
gcc-4.8.1 -Os(executa em 0,994 s):fonte
-O2 -fno-align-functions -fno-align-loopsdiminui o tempo para0.340s, então isso pode ser explicado pelo alinhamento. No entanto, o alinhamento ideal depende do processador: alguns processadores preferem loops e funções alinhados.Meu colega me ajudou a encontrar uma resposta plausível para minha pergunta. Ele notou a importância do limite de 256 bytes. Ele não está registrado aqui e me incentivou a postar a resposta pessoalmente (e levar toda a fama).
Resposta curta:
Tudo se resume ao alinhamento. Os alinhamentos podem ter um impacto significativo no desempenho, é por isso que temos as
-falign-*bandeiras em primeiro lugar.Enviei um relatório de bug (falso?) Para os desenvolvedores do gcc . Acontece que o comportamento padrão é "alinhamos os loops a 8 bytes por padrão, mas tentamos alinhá-lo a 16 bytes se não precisarmos preencher mais de 10 bytes". Aparentemente, esse padrão não é a melhor escolha nesse caso específico e na minha máquina. O toque 3.4 (tronco) com
-O3faz o alinhamento apropriado e o código gerado não mostra esse comportamento estranho.Obviamente, se um alinhamento inadequado é feito, as coisas pioram. Um alinhamento desnecessário / incorreto apenas consome bytes sem motivo e potencialmente aumenta perdas de cache, etc.
Simplesmente dizendo ao gcc para fazer o alinhamento correto:
g++ -O2 -falign-functions=16 -falign-loops=16Resposta longa:
O código será mais lento se:
um
XXlimite de bytes cortaadd()no meio (XXdependendo da máquina).se a chamada para
add()precisar pular umXXlimite de bytes e o destino não estiver alinhado.se
add()não estiver alinhado.se o loop não estiver alinhado.
Os dois primeiros são visíveis nos códigos e resultados que Marat Dukhan gentilmente postou . Nesse caso,
gcc-4.8.1 -Os(executa em 0,994 segundos):um limite de 256 bytes corta
add()bem no meio eadd()nem o loop está alinhado. Surpresa, surpresa, este é o caso mais lento!No caso
gcc-4.7.3 -Os(executado em 0,822 segundos), o limite de 256 bytes corta apenas uma seção fria (mas nem o loop nemadd()é cortado):Nada está alinhado, e a chamada para
add()deve ultrapassar o limite de 256 bytes. Este código é o segundo mais lento.No caso
gcc-4.6.4 -Os(é executado em 0,709 segundos), embora nada esteja alinhado, a chamada paraadd()não precisa ultrapassar o limite de 256 bytes e o destino está exatamente a 32 bytes:Este é o mais rápido dos três. Por que o limite de 256 bytes é importante em sua máquina, deixarei a ele descobrir isso. Eu não tenho esse processador.
Agora, na minha máquina, não recebo esse efeito de limite de 256 bytes. Apenas a função e o alinhamento do loop entram em ação na minha máquina. Se eu passar
g++ -O2 -falign-functions=16 -falign-loops=16, tudo volta ao normal: sempre recebo o caso mais rápido e o tempo não é mais sensível à-fno-omit-frame-pointerbandeira. Posso passarg++ -O2 -falign-functions=32 -falign-loops=32ou qualquer múltiplo de 16, o código também não é sensível a isso.Uma explicação provável é que eu tinha pontos de acesso sensíveis ao alinhamento, exatamente como o deste exemplo. Ao mexer com as bandeiras (passando em
-Osvez de-O2), esses pontos de acesso foram alinhados de forma feliz por acidente e o código ficou mais rápido. Não tinha nada a ver com a otimização do tamanho: foram por mero acidente que os pontos de acesso se alinharam melhor. A partir de agora, verificarei os efeitos do alinhamento em meus projetos.Ah, e mais uma coisa. Como esses pontos de acesso podem surgir, como o mostrado no exemplo? Como pode
add()falhar o alinhamento de uma função tão minúscula como essa ?Considere isto:
e em um arquivo separado:
e compilado como:
g++ -O2 add.cpp main.cpp.O gcc não está alinhado
add()!Isso é tudo, é fácil criar, sem intenção, pontos de acesso como o do OP. Claro que é parcialmente minha culpa: o gcc é um excelente compilador. Se compilar o acima como:,
g++ -O2 -flto add.cpp main.cppisto é, se eu executar a otimização do tempo do link, o código será executado em 0,19s!(O inlining é artificialmente desativado no OP, portanto, o código no OP era 2x mais lento).
fonte
inlinedefinição de função + no cabeçalho. Não tenho certeza da maturidade do lto no gcc. Minha experiência com isso, pelo menos em mingw, é um sucesso ou um fracasso.-flto. é bastante revolucionário se você nunca usou antes, falando da experiência :)Estou adicionando esse pós-aceitação para ressaltar 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 as mudanças na ordem dos links e no tamanho do ambiente do SO foram suficientes para alterar significativamente o desempenho. Eles atribuem isso ao alinhamento de "hot loops".
Este artigo, intitulado "Produzindo dados errados sem fazer nada obviamente errado!" diz que viés experimental inadvertido devido a diferenças quase incontroláveis nos 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 código crítico de desempenho, esse é um argumento bastante bom para sistemas que avaliam o ambiente na instalação ou no tempo de execução e escolhem o melhor local entre as versões otimizadas de maneira diferente das principais rotinas.
fonte
Eu acho que você pode obter o mesmo resultado do que você fez:
... usando
-O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1. Eu tenho compilado tudo com essas opções, que eram mais rápidas do que simples-O2toda vez que eu me preocupava 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 deveria “otimizar o tamanho do código em vez da velocidade” otimiza o tamanho e a velocidade do código.
Não, isso não tem nada a ver com a pilha, os NOPs gerados por padrão e as opções -falign - * = 1 impedir são para alinhamento de código.
É muito provável que o preenchimento seja o culpado. O motivo pelo qual o preenchimento é necessário e útil em alguns casos é que o código geralmente é obtido em linhas de 16 bytes (consulte os recursos de otimização do Agner Fog para obter detalhes, que variam de acordo com o modelo do processador). Alinhar uma função, loop ou rótulo em um limite de 16 bytes significa que as chances são estatisticamente aumentadas de que serão necessárias menos linhas para conter a função ou 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 rótulo, os NOPs podem até precisar ser executados uma vez (quando a execução chega ao loop / rótulo normalmente, ao contrário de um salto).
fonte
-O2 -fno-omit-frame-pointeré tão bom quanto-Os. Por favor, verifique a pergunta atualizada.Se o seu programa estiver limitado pelo cache do CODE L1, a otimização do tamanho começará a ser paga de repente.
Quando verifiquei pela última vez, o compilador não é inteligente o suficiente para descobrir isso em todos os casos.
No seu caso, -O3 provavelmente gera código suficiente para duas linhas de cache, mas -Os se encaixa em uma linha de cache.
fonte
-falign-*=16bandeiras, tudo volta ao normal, tudo se comporta de maneira consistente. Para mim, esta questão está resolvida.Eu não sou especialista nesta área, mas me lembro que os processadores modernos são bastante sensíveis quando se trata de previsão de ramificação . Os algoritmos usados para prever as ramificações são (ou pelo menos estavam 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 a direção.
O cenário que vem à mente são pequenos loops. Quando o ramo estava recuando e a distância não estava muito longe, a previsão do ramo estava otimizando para este caso, pois todos os pequenos loops são feitos dessa maneira. As mesmas regras podem entrar em jogo quando você troca o local
addeworkno código gerado ou quando a posição de ambos muda ligeiramente.Dito isso, não tenho idéia de como verificar isso e só queria que você soubesse que isso pode ser algo que você deseja analisar.
fonte
add()ework()se-O2for aprovado. Em todos os outros casos, o código fica significativamente mais lento ao trocar. Durante o final de semana, também analisei as estatísticas de predição / predição incorreta de ramificaçõesperfe não notei nada que pudesse explicar esse comportamento estranho. O único resultado consistente é que, no caso lento,perfregistra 100,0 inadd()e um grande valor na linha logo após a chamadaadd()no loop. Parece que estamos parando por algum motivo noadd()caso lento, mas não nas corridas rápidas.perfsuporta apenas um número limitado de coisas, talvez o material da Intel seja um pouco mais útil em seu próprio processador.