BLOG C++

Complementando o post anterior…

Uma otimização que um sujeito poderia pensar em fazer no programa original seria, já que i e j não variam no loop mais interno, usar uma variável temporária para acumular a soma eliminando o acesso ao array, como no programa abaixo:

#include <cstdlib>

int main(int argc, char *argv[])
{
  const int N = 1000;
  typedef double Linha[N];
  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 j = 0; j < N; j++ ) {
      double t = 0;
      for( int k = 0; k < N; k++ )
        t += a[i][k] * b[k][j];
      c[i][j] = t;
    }  

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

Resultado:

O tempo de execução no g++ não muda: 15.95 segundos. O g++ já faz essa otimização internamente…

Já no compilador Intel, o tempo passa de 0.62 para 8.02 segundos… mais rápido que o g++,  mas bem mais lento que o programa original. Isso ocorre por que agora o otimizador não pode trocar a ordem dos loops, e daí não consegue nem vetorializar totalmente a multiplicação nem tornar o acesso à memória sequencial para fazer bom uso do cache.

Ou seja: o sujeito que se acha esperto fazendo a “melhoria” acima na verdade está atrapalhando o trabalho do otimizador…

“I drank what?” said Socrates…