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.
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 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 ++?
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:
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.)
Podemos tirar -Osa foto. Os seguintes tempos são obtidos através da compilação com
-S -O2movendo manualmente a montagem add()após work()0,37s
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:
Para fno-align-*:
Para -fno-omit-frame-pointer:
Parece 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.
Palpite cego: isso pode ser um erro de cache?
@ H2CO3 Esse foi o meu primeiro pensamento também, mas não foi incentivado o suficiente para postar o comentário sem ler e entender a pergunta do OP em profundidade.
@ g-makulik É por isso que eu avisei que é um "palpite cego" ;-) "TL; DR" é reservado para perguntas ruins. : P
Apenas um ponto de dados interessante: acho que -O3 ou -Ofast é cerca de 1,5x mais rápido que -Os quando compilo com clang no OS X. (não tentei reproduzir com o gcc.)
É o mesmo código. Dê uma olhada no endereço de .L3, destinos de ramificação desalinhados são caros.
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.3e 4.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):
— Marat Dukhan
Apenas para esclarecer: você realmente mediu o desempenho do código do OP em 12 plataformas diferentes? (+1 para o mero pensamento de que você faria isso)
@anatolyg Sim, eu fiz! (e vai acrescentar mais alguns em breve)
De fato. Outro +1 por não apenas teorizar sobre diferentes CPUs, mas realmente provar isso. Não é algo que você vê em todas as respostas sobre velocidade. Esses testes são executados com o mesmo sistema operacional? (Como pode ser possível este skews o resultado ...)
@ Ali No AMD-FX 6300 -O2 -fno-align-functions -fno-align-loopsdiminui o tempo para 0.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.
@Ongware Não vejo como o sistema operacional influenciaria significativamente os resultados; o loop nunca faz chamadas do sistema.
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).
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.
Como posso garantir que esses alinhamentos acidentais de sorte / azar não interfiram quando faço micro-otimizações (não relacionadas ao alinhamento de pilhas) em códigos-fonte C ou C ++?
Simplesmente dizendo ao gcc para fazer o alinhamento correto:
O código será mais lento se:
um XXlimite de bytes corta add()no meio ( XXdependendo da máquina).
se a chamada para add()precisar pular um XXlimite 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 e add()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 nem add()é 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 para add()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 passar g++ -O2 -falign-functions=32 -falign-loops=32ou qualquer múltiplo de 16, o código também não é sensível a isso.
Percebi pela primeira vez em 2009 que o gcc (pelo menos nos meus projetos e nas minhas máquinas) tem a tendência de gerar código visivelmente mais rápido se eu otimizar o tamanho (-Os) em vez da velocidade (-O2 ou -O3) e fiquei pensando desde porque.
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 ?
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).
Uau ... Isso definitivamente vai além do que eu costumo fazer para contornar anomalias de benchmarking.
— Mysticial 24/10/2013
@ Ali acho que faz sentido, pois como o compilador pode incorporar algo que não vê? Provavelmente é por isso que usamos a 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.
Eu acho que foi o Communications of the ACM que publicou um artigo há alguns anos sobre a execução de aplicativos razoavelmente grandes (perl, Spice etc.) enquanto deslocava toda a imagem binária em um byte por vez, usando ambientes Linux de tamanho diferente. Lembro-me de uma variação típica de 15% ou mais. Seu resumo foi que muitos resultados de benchmark são inúteis porque essa variável externa de alinhamento não é levada em consideração.
up'd particularmente para -flto. é bastante revolucionário se você nunca usou antes, falando da experiência :)
Este é um vídeo fantástico que fala sobre como o alinhamento pode afetar o desempenho e como criar um perfil para ele: youtube.com/watch?time_continue=1&v=r-TLSBdHe1A
— Zhro 05/10/19
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.
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.
Eu acho que você pode obter o mesmo resultado do que você fez:
Peguei a montagem para -O2 e mesclei todas as suas diferenças na montagem para -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 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.
Se eu acho corretamente, esses são os preenchimentos para o alinhamento da 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 impedir são para alinhamento de código.
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.
É 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).
O engraçado é: -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.
Quanto você deseja apostar que os parâmetros align = estejam relacionados ao tamanho das linhas de cache?
— 27413 Joshua
Eu realmente não me importo mais: não está visível na minha máquina. E, passando as -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 adde workno 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.
Obrigado. Eu brinquei com ele: só ganho velocidade trocando add()e work()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ções perfe não notei nada que pudesse explicar esse comportamento estranho. O único resultado consistente é que, no caso lento, perfregistra 100,0 in add()e um grande valor na linha logo após a chamada add()no loop. Parece que estamos parando por algum motivo no add()caso lento, mas não nas corridas rápidas.
Estou pensando em instalar o VTune da Intel em uma das minhas máquinas e fazer um perfil. perfsuporta apenas um número limitado de coisas, talvez o material da Intel seja um pouco mais útil em seu próprio processador.