Palavras-chave: C, memória, cache, performance, velocidade
Todo processador hoje em dia possui memória cache, que ajuda a melhorar a performance, armazenando os dados mais recentemente acessados, para acesso mais rápido pelo processador.
O que nós freqüentemente ignoramos é que a organização dos dados e o padrão de acesso à memória podem aproveitar muito bem ou simplesmente estragar a ajuda que a cache nos dá.
Vamos comparar duas versões de um programa que soma os elementos de uma matriz, e seus tempos de execução:
/* matriz1 */
#define N 10000
#define M 15000
static int m[N][M];
int main()
{
int i, j, soma = 0;
for (j = 0; j < M; j++) /* coluna a coluna */
for (i = 0; i < N; i++)
soma += m[i][j];
return 0;
}
/* matriz2 */
#define N 10000
#define M 15000
static int m[N][M];
int main()
{
int i, j, soma = 0;
for (i = 0; i < N; i++) /* linha a linha */
for (j = 0; j < M; j++)
soma += m[i][j];
return 0;
}
$ time -p ./matriz1 real 1.44 user 1.38 sys 0.05
$ time -p ./matriz2 real 0.78 user 0.72 sys 0.05
Conseguimos quase cortar pela metade o tempo de execução (de 1,38 para 0,72 segundos), apenas modificando a ordem em que os elementos da matriz são acessados. No segundo caso, os dados são acessados linha a linha (seqüencialmente na memória), aproveitando que blocos de memória contendo elementos vizinhos já foram carregados na memória cache.
Olá! :) Gostaria, se você me permite, de comentar 2 coisas:
1. Não teria um pequeno bug no exemplo 1? Acho que no primeiro for() deveria ser um j M.
2. A sua dica é bem interessante, mas normalmente (eu pelo menos faço) já se faz o “jeito certo”, isto é, no dia-a-dia da programação, quando temos que percorrer uma matriz NxM já o fazemos “naturalmente”, linha a linha.
Assim, se você tivesse outras sugestões de como podemos explorar melhor o cache dos processadores, seria bem mais interessante.
Obrigado pela sua atenção e parabéns pela dica! :)
Ops, o wordpress “comeu” o sinal. No primeiro comentário, leia:
“Acho que no primeiro for() deveria ser um j MENOR que M ao invés de j MAIOR que M.”
Olá,
1. Sim. Obrigado pela correção
2. Se você já percorre linha a linha, ótimo. :)
Às vezes dependendo da abstração, alguém pode fazer do jeito diferente sem imaginar que a diferença que isso faz. Daí a dica. Suponha que as linhas sejam chamadas de “coordenada y” e colunas de “coordenada x”. Nesse caso não dá vontade de fazer
for (x=0;...) for (y=0;...)? Em mim dá, e já fiz assim, antes de aprender. :)Olá,
realmente, sob este aspecto, você está certíssimo. Então fica registrado, mais algum amigo programador estiver lendo estes comentários e tiver mais alguma sugestão de código “jeito certo” (que explore melhor o cache dos processadores) que se manifeste! :)
Obrigado pela atenção e, novamente, obrigado pela dica! :)
Olá!
Adenilson, não tem como você continuar o seu post? Achei ele bem interessante…. :~
[]’s
P.S. Como faz pra postar código? Fui postar e meu código também foi “comido”…
Adenilson, Eu,
A área de comentários aceita códigos HTML, então ao colocar caracteres especiais é preciso mascará-los. São apenas três, coloquei lá na página “Sobre”, mas vou replicar aqui para facilitar:
< deve ser <
> deve ser >
& deve ser &
Podem mandar os códigos atualizados que eu apago o comentário truncado, se for o caso.
Abraço e valeu!
Aurélio
Valeu pela dica. Vou tentar novamente:
Geralmente em processamento de imagens/video, costuma-se utilizar um vetor V[n] onde n = cols * rows * color_channels.
Pode-se acessar qualquer elemento da matriz usando-se o offset. Com
isso, é possível fazer uma operacao em todos o elementos em 1 único loop (for) ao invés de n_loops = dimensao_matriz.
Ficaria algo como:
int size = N * M * CHANNELS;
char *vector = malloc(size * sizeof(char));
for (int i = 0; i < size; ++i)
sum += vector[i];
ao invés de:
char vector[N][M][CHANNELS];
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
for (int z = 0; z < CHANNELS; ++z)
sum += vector[i][j][z];
No caso de haver 3 canais de cor (R, G, B), a forma de representar os canais geralmente é com os 3 canais em sequência no vetor: RGB RGB RGB RGB (para uma matrix [2][2][3]). Existem outras maneiras de se representar os canais de cor no vetor, e.g. RRRR GGGG BBBB.
Muito legal.
Isso mostra que é relevante SIM analisarmos a localidade de referência nos nossos programas.
Nesse caso, foi explorada a localidade de referência espacial em uma instância maior. Mais sobre o assunto:
http://informatica.hsw.uol.com.br/cache6.htm
http://en.wikipedia.org/wiki/Locality_of_reference