Por que meu programa fica lento ao fazer loop sobre exatamente 8192 elementos?

755

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.

casperOne
fonte
67
@bokan acontece quando o tamanho é múltiplo do passo crítico do cache.
Luchian Grigore
5
@Mysticial, não importa, expõe o mesmo problema exato; o código pode ser diferente, mas basicamente as duas perguntas são feitas ao mesmo tempo (e seus títulos são definitivamente semelhantes).
Griwes 04/04/12
33
Você não deve processar a imagem usando uma matriz de duas dimensões, se desejar alto desempenho. Considere todos os pixels em um estado bruto e processe-os como uma matriz de uma dimensão. Faça esse desfoque em duas passagens. Primeiro adicione valor aos pixels adjacentes usando uma soma deslizante de 3 pixels: slideSum + = src [i + 1] -src [i-1]; dest [i] = slideSum; Em seguida, faça o mesmo verticalmente e divida ao mesmo tempo: dest [i] = (src [largura i] + src [i] + src [i + largura]) / 9. www-personal.engin.umd.umich.edu/~jwvm/ece581/18_RankedF.pdf
bokan
8
Na verdade, há duas coisas acontecendo aqui. Não é apenas superalinhamento.
Mysticial
7
(Apenas um nitpick menor em sua resposta para o primeiro segmento de código, que seria bom se todas as suas chaves para loops tinha..)
Trevor Boyd Smith

Respostas:

954

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:

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;
}

Primeiro observe que os dois loops internos são triviais. Eles podem ser desenrolados da seguinte maneira:

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

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.

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

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:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

Loops Externos Intercambiados:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds
Mysticial
fonte
217
Também observarei que desenrolar os loops internos não afeta o desempenho. O compilador provavelmente faz isso automaticamente. Desenrolei-os com o único objetivo de me livrar deles para facilitar a identificação do problema com os laços externos.
Mysticial
29
E você pode acelerar esse código por outro fator de três, armazenando em cache as somas ao longo de cada linha. Mas essa e outras otimizações estão fora do escopo da pergunta original.
Eric Postpischil
34
@ClickUpvote Este é realmente um problema de hardware (cache). Não tem nada a ver com o idioma. Se você tentasse em qualquer outro idioma que compila ou JITs para código nativo, provavelmente verá os mesmos efeitos.
Mysticial 4/12
19
@ClickUpvote: Você parece um pouco equivocado. Aquele "segundo laço" era apenas místico desenrolando os laços internos à mão. Isso é algo que seu compilador quase certamente fará de qualquer maneira, e o Mystical apenas fez isso para tornar o problema com os loops externos mais óbvios. Não é de forma alguma algo que você deveria se preocupar em fazer a si mesmo.
Lily Ballard
154
ESTE é um exemplo perfeito de uma boa resposta para SO: faz referência a perguntas semelhantes, explica passo a passo como você o abordou, explica o problema, explica como CORRIGIR o problema, possui ótima formatação e até mesmo um exemplo do código em execução na sua máquina. Obrigado pela sua contribuição.
precisa saber é o seguinte
57

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:

pointer + (x + y*width)*(sizeOfOnePixel)

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:

8193: 4392 ms
8192: 9570 ms

Versão do Mystical:

8193: 2393 ms
8192: 2190 ms

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:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

Duas passagens usando uma matriz 1D e endereçamento como este:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

O cache de uma passagem horizontal soma apenas uma linha à frente, para que eles permaneçam no cache:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

Conclusão:

  • Não há benefícios em usar vários ponteiros e apenas incrementos (pensei que teria sido mais rápido)
  • Armazenar em cache somas horizontais é melhor do que computá-las várias vezes.
  • Dois passes não são três vezes mais rápidos, apenas duas vezes.
  • É possível obter 3,6 vezes mais rápido usando uma única passagem e armazenando em cache um resultado intermediário

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.

Bokan
fonte
9
"Acho que é pelo menos três vezes mais rápido" - gostaria de fazer backup dessa reivindicação com algumas métricas ou citações?
Adam Rosenfield
8
@AdamRosenfield "Eu acho" = suposição! = "É" = reivindicação. Não tenho métrica para isso e gostaria de fazer um teste. Mas o meu exige 7 incrementos, 2 sub, 2 add e uma div por pixel. Cada loop usando menos var local do que o registro na CPU. O outro exige 7 incrementos, 6 decrementos, 1 div e entre 10 e 20 mul para endereçamento, dependendo da otimização do compilador. Além disso, cada instrução no loop exige o resultado da instrução anterior, descartando os benefícios da arquitetura superescalar dos Pentiums. Então tem que ser mais rápido.
Bokan
3
A resposta para a pergunta original é sobre efeitos de memória e cache. O motivo pelo qual o código do OP é tão lento é que seu padrão de acesso à memória passa por colunas, e não por linhas, que tem uma localidade de referência de cache muito baixa. É particularmente ruim no 8192 porque as linhas consecutivas acabam usando as mesmas linhas de cache em um cache mapeado diretamente ou com baixa associatividade, portanto, a taxa de perda de cache é ainda mais alta. A troca dos loops fornece um enorme aumento de desempenho, aumentando muito a localidade do cache.
Adam Rosenfield
1
Bem feito, esses são alguns números impressionantes. Como você descobriu, tudo se resume ao desempenho da memória - o uso de vários ponteiros com incrementos não trouxe nenhum benefício.
Adam Rosenfield
2
@ AdamRosenfield Fiquei bastante preocupado esta manhã porque não consegui reproduzir os testes. Parece que o aumento de desempenho é apenas com o compilador Visual C ++. Usando o gcc, há apenas uma pequena diferença.
bokan 6/09/12