C: Performance: uso eficiente da memória cache

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.

This entry was posted in C. Bookmark the permalink.

8 Responses to C: Performance: uso eficiente da memória cache

  1. Eu says:

    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! :)

  2. Eu says:

    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.”

  3. 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. :)

  4. Eu says:

    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! :)

  5. Eu says:

    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”…

  6. 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 &lt;
    > deve ser &gt;
    & deve ser &amp;

    Podem mandar os códigos atualizados que eu apago o comentário truncado, se for o caso.

    Abraço e valeu!

  7. Adenilson Cavalcanti says:

    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.

  8. André Taiar says:

    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

Leave a Reply

Your email address will not be published. Required fields are marked *