Aqui está o extrato do programa em questão. A matriz img[][]tem o tamanho SIZE × SIZE e é inicializada em:
img[j][i] = 2 * j + i
Então, você cria uma matriz res[][], e cada campo aqui é criado para ser a média dos 9 campos ao seu redor na matriz img. A borda é deixada em 0 para simplificar.
for(i=1;i<SIZE-1;i++)
for(j=1;j<SIZE-1;j++) {
res[j][i]=0;
for(k=-1;k<2;k++)
for(l=-1;l<2;l++)
res[j][i] += img[j+l][i+k];
res[j][i] /= 9;
}
Isso é tudo o que há no programa. Por uma questão de completude, eis o que vem antes. Nenhum código vem depois. Como você pode ver, é apenas inicialização.
#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
img[j][i] = (2*j+i)%8196;
Basicamente, este programa é lento quando SIZE é múltiplo de 2048, por exemplo, os tempos de execução:
SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs
O compilador é o GCC. Pelo que sei, isso se deve ao gerenciamento de memória, mas não sei muito sobre esse assunto, e é por isso que estou perguntando aqui.
Também como corrigir isso seria bom, mas se alguém pudesse explicar esses tempos de execução, eu já ficaria feliz o suficiente.
Eu já conheço o malloc / free, mas o problema não é a quantidade de memória usada, é apenas o tempo de execução, então não sei como isso ajudaria.
fonte
Respostas:
A diferença é causada pelo mesmo problema de superalinhamento das seguintes questões relacionadas:
Mas isso é apenas porque há outro problema com o código.
A partir do loop original:
Primeiro observe que os dois loops internos são triviais. Eles podem ser desenrolados da seguinte maneira:
Então, isso deixa os dois circuitos externos nos quais estamos interessados.
Agora podemos ver que o problema é o mesmo nesta pergunta: Por que a ordem dos loops afeta o desempenho ao iterar em uma matriz 2D?
Você está iterando a matriz em colunas, em vez de em linhas.
Para resolver esse problema, você deve trocar os dois loops.
Isso elimina todo o acesso não seqüencial completamente, para que você não tenha mais lentidão aleatória em grandes potências de dois.
Core i7 920 a 3,5 GHz
Código original:
Loops Externos Intercambiados:
fonte
Os seguintes testes foram feitos com o compilador Visual C ++, pois é usado pela instalação padrão do Qt Creator (acho que sem sinalizador de otimização). Ao usar o GCC, não há grande diferença entre a versão do Mystical e meu código "otimizado". Portanto, a conclusão é que as otimizações do compilador resolvem melhor a micro otimização do que os humanos (finalmente eu). Deixo o resto da minha resposta como referência.
Não é eficiente processar imagens dessa maneira. É melhor usar matrizes de dimensão única. O processamento de todos os pixels é feito em um loop. O acesso aleatório aos pontos pode ser feito usando:
Nesse caso em particular, é melhor calcular e armazenar em cache a soma de três grupos de pixels horizontalmente porque eles são usados três vezes cada.
Eu fiz alguns testes e acho que vale a pena compartilhar. Cada resultado é uma média de cinco testes.
Código original pelo usuário1615209:
Versão do Mystical:
Duas passagens usando uma matriz 1D: primeira passagem para somas horizontais, segunda para soma vertical e média. Endereçamento de duas passagens com três ponteiros e apenas incrementos como este:
Duas passagens usando uma matriz 1D e endereçamento como este:
O cache de uma passagem horizontal soma apenas uma linha à frente, para que eles permaneçam no cache:
Conclusão:
Tenho certeza de que é possível fazer muito melhor.
NOTA Observe que eu escrevi esta resposta para abordar questões gerais de desempenho, e não o problema de cache explicado na excelente resposta do Mystical. No começo, era apenas pseudo-código. Me pediram para fazer testes nos comentários ... Aqui está uma versão completamente refatorada com testes.
fonte