Quer velocidade no C++? Não faça a coisa errada…
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…
Zimbrão, há algum jeito de saber estas coisas de antemão? Ou só tentando otimizar e testando? Ou o esforço seria o de conhecer as técnicas de otimização uma a uma em cada situação?
Quero dizer… há algumas “linhas gerais” pra nortear a otimização?
Bom,
primeiro é preciso conhecer a arquitetura da máquina, o que ela oferece – para saber por exemplo a influência da localidade dos dados no cache, e saber que existe prefetching, pipeline, branchs em paralelo, operações vetoriais etc. Para isso é só acompanhar as novidades dos fabricantes, principalmente Intel e AMD.
Segundo, saber o que o compilador oferece de otimização e como ele trabalha, quais os pontos fortes e fracos. Isso só lendo o manual de cada compilador.
Terceiro, que serve de regra geral, escreva o código da maneira mais clara possível – no sentido não só humano, mas passando pro compilador o máximo de dicas: usar const, evitar ponteiros etc, e evitar otimizações que tornem o código mais obscuro.
Por último, testar!!
[]s
Sim, programo sempre para humanos, da forma mais legível possível. Só depois de testes para averigüar o desempenho e depois de constatado e localizado um problema é que otimizo. De qualquer forma, ter uns guidelines para nortear a otimização é sempre bom.
Ainda assim só otimizo pra um hardware específico em última instância, a não ser que os requisitos já limitem o hardware a priori.
Obrigado.