BLOG C++

Otimização Final – g++

No post Quer velocidade no C++? Faça a coisa certa…, mostrei como podemos ajudar o otimizador do g++ sem escovar bits. Agora, mostro que tipo de escovação de bits é aceitável, e produz bons resultados. Note que ainda assim, o tempo final continua maior que o do compilador Intel.

Basicamente, podemos ajudar o compilador a identificar partes dos loops que contém dados invariantes. O novo programa, ao invés de ter os três loops aninhados, possui uma chamada a uma função para fazer a multiplicação por linha. No entanto, essa função é inline, de modo que é expandida no código. A princípio, isso não deveria melhorar o desempenho, porém o fato de passarmos parâmetros dá uma dica importante ao compilador: os parâmetros não mudam. Nem sempre o otimizador consegue descobrir isso.

#include <cstdlib>

const int N = 1000;
typedef double Linha[N];

inline void multiplicaPorLinha( Linha& ci, const double aik, const Linha& bk ) {
  for( int j = 0; j < N; j++ )
    ci[j] += aik * bk[j];
}

int main(int argc, char *argv[])
{
  Linha * const a = new Linha[N],
        * const b = new Linha[N],
        * const c = new Linha[N];

  srand(1);
  for( int i = 0; i < N; i++ )
    for( int j = 0; j < N; j++ ) {
      a[i][j] = rand()/(rand()+0.1);
      b[i][j] = rand()/(rand()+0.1);
      c[i][j] = 0;
    }

  for( int i = 0; i < N; i++ )
    for( int k = 0; k < N; k++ )
      multiplicaPorLinha( c[i], a[i][k], b[k] );

  delete [] a;
  delete [] b;
  delete [] c;
}

Essa otimização sozinha já reduz o tempo de 2.79 segundos para 2.22 segundos. Mas além disso, se estivermos amarrados ao Dev-Cpp, podemos trocar a linha de comando para otimizar para o K8 ao invés do Pentium 4 – o motivo é que quase todas as novas CPUs, mesmo as Intel, são compatíveis com o K8, e o código que o g++ gera para o K8 é melhor que o gerado para o Pentium 4, especialmente por causa do conjunto de instruções sse3. Linha de comando:

-O3 -funroll-loops -fprefetch-loop-arrays -march=k8 -msse3

Resultado: 1.80 segundos. Por último, se você instalar o g++ 4.40 (para Windows, MingW), pode usar a seguinte linha de argumentos:

-O3 -funroll-loops -fprefetch-loop-arrays -march=core2 -msse4

Agora sim para Intel Core 2. Resultado: 1.62 segundos… 10x mais rápido que o programa com opção -O3, 1.62 x mais rápido que o post anterior, e 11% mais rápido que para o K8.

Infelizmente essa otimização faz com que o compilador Intel perca umpouco de desempenho: agora fica com 1.2 segundos, o dobro do tempo anterior, embora ainda mais rápido que o g++. Não consegui descobrir porque isso ocorreu…

Rio 2016!!!!