Porque é que a otimização vinculador tão pobre?

Question

Recentemente, um colega de trabalho apontou para mim que compilar tudo em um único arquivo criado código muito mais eficiente do que a compilação de arquivos de objetos separados - mesmo com a otimização de tempo de ligação ligado . Além disso, o tempo total de compilação para o projeto desceu significativamente. Dado que uma das principais razões para a utilização de C ++ é a eficiência do código, este foi surpreendente para mim.

Claramente, quando o archiver / vinculador torna uma biblioteca de arquivos de objetos, ou links-los em um executável, mesmo otimizações simples são penalizados. No exemplo abaixo, inline trivial custa 1,8% em desempenho quando feito pelo ligador em vez do compilador. Parece como a tecnologia compilador deve ser suficiente avançada para lidar com situações bastante comuns como este, mas isso não está acontecendo.

Aqui está um exemplo simples usando o Visual Studio 2008:

#include <cstdlib>
#include <iostream>
#include <boost/timer.hpp>

using namespace std;

int foo(int x);
int foo2(int x) { return x++; }

int main(int argc, char** argv)
{
  boost::timer t;

  t.restart();
  for (int i=0; i<atoi(argv[1]); i++)
    foo (i);
  cout << "time : " << t.elapsed() << endl;

  t.restart();
  for (int i=0; i<atoi(argv[1]); i++)
    foo2 (i);
  cout << "time : " << t.elapsed() << endl;
}

foo.cpp

int foo (int x) { return x++; }

Os resultados de funcionamento:. 1,8% acerto de desempenho para usar foo ligada ao invés de foo2 em linha

$ ./release/testlink.exe  100000000
time : 13.375
time : 13.14

E sim, as opções de otimização de vinculador (/ LTCG) estão ligados.

Answer 1

Eu não sou um especialista compilador, mas acho que o compilador tem muito mais informação disponível à disposição para otimizar como ela opera em uma árvore linguagem, ao contrário do vinculador que tem de conteúdo em si para operar na saída objeto, muito menos expressivo do que o código o compilador tem visto. Portanto, menos esforço é gasto pela equipe (s) vinculador e desenvolvimento compilador para fazer otimizações vinculador que poderia combinar, em teoria, os truques que o compilador faz.

BTW, eu sinto muito que eu distrair sua pergunta original na discussão LTCG. Agora eu entendo a sua pergunta foi um pouco diferente, mais preocupado com o tempo de ligação vs. compilação otimizações tempo estáticas possíveis / disponíveis.

Answer 2

Seu colega de trabalho está desatualizado. A tecnologia está aqui desde 2003 (na MS C ++ compilador): / LTCG . Fazer a ligação geração de código de tempo é lidar com exatamente este problema. Pelo que eu sei o GCC tem esta característica no radar para o compilador próxima geração.

LTCG não é só otimizar o código como inlining funções dos módulos, mas na verdade rearanges código para localidade de cache otimizar e ramificação para uma carga específica, consulte Perfil-guiada otimizações . Estas opções são usualy reservado apenas para lançamento aumenta à medida que a construção pode levar horas para terminar: vai ligar um executável instrumentada, executar uma carga de perfil e, em seguida, ligar novamente com os resultados de perfil. O link contém detalhes sobre o que exatamente é otimizado com LTCG:

Inlining - Por exemplo, se houver existe uma função A, que frequentemente chama a função B e função B é relativamente pequeno, em seguida, o perfil guiada optimizações vão in-line função B em função de A.

A especulação Chamada Virtual - Se um chamada virtual, ou outra chamada através de um ponteiro de função, muitas vezes alvo um determinada função, um perfil guiada optimização pode inserir um condicionalmente executado chamada direta para a função frequentemente segmentada, e a chamada direta pode ser embutido.

Register Allocation - Otimização com perfil de dados resulta em melhor registar alocação.

Basic Bloco Otimização - bloquear Básico otimização permite comumente executados blocos básicos que temporalmente executam dentro de um determinado intervalo de ser colocado em o mesmo conjunto de páginas (localidade). este minimiza o número de páginas usadas, minimizando assim sobrecarga de memória.

Tamanho / Speed ??Optimization - Funções onde o programa passa muito tempo pode ser otimizado para velocidade.

Função layout - Com base na chamada gráfico e perfilada chamador / receptor comportamento, funções que tendem a ser ao longo do mesmo caminho de execução são colocado na mesma seção.

Conditional Filial Otimização - Com as sondas de valor, perfil guiada otimizações podem descobrir se um determinado valor em uma instrução switch é usado mais frequentemente do que outros valores. este valor pode então ser puxado para fora da switch. O mesmo pode ser feito com if / else instruções onde o otimizador pode encomendar o if / else assim que ou o caso, ou então bloco é colocado em primeiro lugar, dependendo de qual bloco é mais frequentemente verdadeiro.

Dead Code Separação - O código que é não é chamado durante a criação de perfil é movido para uma secção especial que está apenso até o fim do conjunto de seções. Isso mantém efetivamente esta secção fora das páginas frequentemente utilizados.

Código EH Separação - O código EH, sendo excepcionalmente executado, pode muitas vezes, ser transferida para uma secção separada quando optimizações guiada por perfil pode determinar que as exceções ocorrem apenas em condições excepcionais.

Memória Intrinsics - A expansão da intrínsecos pode ser decidido melhor se pode ser determinado se um intrínseca é chamado com freqüência. Uma lata intrínseca também ser optimizada com base no bloco tamanho de movimentos ou cópias.

Answer 3

O seu colega de trabalho é mais esperto do que a maioria de nós. Mesmo que pareça uma abordagem bruto no início, projeto inlining em um único arquivo .cpp tem uma coisa que as outras abordagens como link-time-otimização não tem e não terá por enquanto - confiabilidade

No entanto, você perguntou isso há dois anos, e eu testemunhar que muita coisa mudou desde então (com g ++, pelo menos). Devirtualization é muito mais confiável, por exemplo.