Cuidado com arrays multidimensionais!

Você provavelmente nunca pensou nisso seriamente, mas a ordem com que usa um array multidimensional pode interferir muito na performance de sua rotina. É bom lembrar que a declaração de, por exemplo, um array bidimensional é apenas uma dica para o compilador dos tamanhos de cada “linha” do array, que será tratado como um array unidimensional normal através do ponteiro para o primeiro item. Quer dizer, a declaração:

int a[20][30];

Alocará um espaço de 2400 bytes na memória (20 \cdot 30 \cdot 4) com ‘a’ apontando para o item, a[0][0]. A notação de arrays indica ao compilador como este deve calcular o endereço de um item qualquer. Na declaração acima temos um bloco de memória cujo endereço de qualquer item pode ser calculado como:

p=a+(N_{cols}\cdot i + j) \cdot sizeof(int)

Onde a é o endereço do primeiro item do array (a[0][0]), N_{cols} é o número de colunas, os índices i e j correspondem ao número da linha e coluna desejados, respectivamente. O ponteiro p conterá o endereço dessa posição. Assim, ao tentar acessar a[2][3], estamos, na realidade, usando um ponteiro p, onde:

int a[20][30], *p;

/* Isto... */
a[2][3] = 0;

/* É a mesma coisa que isto: */
p = (int *)a + (30*2 + 3);
*p = 0;

É claro, não estou considerando a fronteira de uma única linha nesse cálculo… Dado esse background, qual das duas funções abaixo é a mais rápida?

/* SIZE é definido em tempo de compilação! */
int a[SIZE][SIZE];

/* Escreve uma linha inteira a cada vez. */
void f(void)
{
  int i, j;

  for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
      a[i][j] = 1;
}

/* Escreve uma coluna inteiro a cada vez. */
void g(void)
{
  int i, j;

  for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
      a[j][i] = 1; /* note o i e j */
}

Acredito que a maioria de vocês responderia uma de duas coisas:

  1. Ambas as rotinas gastam o mesmo tempo, ou;
  2. A primeira é mais rápida porque atualiza o array sequencialmente.

É razoável pensar que a resposta número 2 seja a correta, mas infelizmente nem sempre isso acontece… Existe um caso onde a função g será mais rápida que f e, para entender o que acontece, temos que obter algumas informações do processador:

$ lscpu | grep '^L1d'
L1d cache: 32K
$ cat /proc/cpuinfo | grep 'clflush size' | uniq
clflush size : 64

Toda rotina que lida com uma maçaroca de dados contidos na memória precisa levar em conta o cache L1d. No processador que usei para testes o cache L1d tem 32 KB de tamanho e é dividido em linhas de 64 bytes cada. Isso nos dá uma capacidade máxima de 512 linhas para o cache L1d. Se tivéssemos um array de ints, bidimensional, com dimensões de 16 linhas e 16 colunas, cada linha do array caberia exatamente numa linha de cache (16\cdot sizeof(int) = 64 bytes) e, obviamente, usaríamos 16 linhas do cache.

Fazendo SIZE=16 e se todo o array já estiver no cache L1d, a função f gasta duas vezes menos ciclos do que a função g. Se o array não estiver no cache então o acesso ao primeiro item de cada uma das linhas do array precisará ser carregada para o mesmo (prefetch). A função g, neste caso, carregará todas as linhas ao terminar as iterações do loop interno, na primeira iteração do loop externo, ficando mais rápida. Sei que isso causa estranheza, já que ambas as funções realizarão, em teoria, o mesmo número de prefetches. Eis cada caso:

f(): PEEEEEEEEEEEEEEEEPEEEEEEEEEEEEEEEE...
g(): PEPEPEPEPEPEPEPEPEPEPEPEPEPEPEPEEEEEEEEEEEEEEEEE...

A diferença é que f realizará 16 prefetches (P) para cada uma das linhas e depois de cada prefetch realizará 16 escritas (E). A função g, por outro lado, realizará 16 pares de prefetch-e-escrita seguido de 240 escritas. Prefetches lêem uma linha inteira do cache. No primeiro caso temos 16 blocos de operações precedidas por um prefetch, no segundo, temos 16 prefetches com suas operações seguidas de 15 operações.

Eis uma tabela comparativa de performance das duas rotinas, em linhas gerais:

Cabe no cache L1d? Está toda no cache L1d? Função mais rápida (ganho%)
Não N/A f (quase duas vezes ou mais)
Sim Sim f (>= 20%)
Sim Não g (>= 20%)

No caso do array não caber no cache L1d, ambas as rotinas terão que realizar prefetches de qualquer maneira e ambas realizarão “evicts” e “prefetches”, mas f fará de maneira mais espaçada e, por isso, é mais rápida… Neste caso, segundo meus testes, a diferença de performance de f em relação a g pode até mesmo ultrapassar um fator de 10, sendo o fator mínimo medido é de 2 vezes ou mais.

Uma maneira de colocar todo o array no cache L1d, se ele couber lá, é usando a instrução PREFETCHW ou usando a função __builtin_prefetch do GCC:

extern int a[][SIZE];
char *p = (char *)a + SIZE*(SIZE*sizeof(int) - 1);

for (;p >= a; p -= CACHELINE_SIZE)
  __builtin_prefetch(p, 1);
  /* O segundo parâmetro significa 'escrita' */

Onde CACHELINE_SIZE é, no meu caso, 64 (bytes).

Um jeito mais simples, mas pouco performático, é escrever em todo o array, mas isso consome um bocado de tempo e nem sempre é uma boa idéia. A vantagem é que você não terá que encontrar apenas um endereço por linha de cache:

memset(a, 0, sizeof(a));
Anúncios