Lidando com os Caches de maneira prática

Pode ter parecido que otimizar o código é uma coisa muito complicada… Não é! Neste artigo curtinho vou dar uma ou duas dicas sobre otimizações sob a perspectiva do uso eficiente dos caches (L1, L2 e L3, se houver).

Nos processadores modernos (Core 2, i3, i5 e i7, principalmente) temos o cache L1 (o cache mais interno do processador) com tamanho de 64 kB (32 kB para dados e 32 kB para instruções) e é este cache que você deve se preocupar mais (o cache L2 pode ter de 512 kB até 16 MB, pelo que sei). Todos os caches são organizados em “linhas”. Cada linha tem 64 bytes de tamanho (bytes… não “bits”!). O objetivo dos caches é manter no inteior do processaor porções da memória do sistema (da RAM). Esses caches são muitas vezes mais rápidos do que a memória dinâmica contida nos “pentes” de memória do seu computador.

Cada vez que o processador tentar ler um endereço de memória ele verificará antes se esses dados já estão no cache. Se estiverem, temos um cache hit, se não estiverem, temos um cache miss. A cada vez que ocorrer um cache miss o processador tentará ler uma linha (64 bytes) do cache L2 para o cache L1. Se houver um cache miss no cache L2 também, este tentará ler a linha do cache L3 (se existir) ou da memória RAM. Enquanto essa linha é lida para os diversos níveis de cache, o processador fica em estado de espera (idle state). Por isso cache misses são extremamente prejudiciais para a performance.

A conclusão é óbvia: Para termos excelente performance temos que garantir que os dados que estamos manipulando e as instruções que estamos executando estejam no cache L1, evitando cache misses e obtendo apenas cache hits.

Num artigo anterior eu disse que cruzar a fronteira de uma linha do cache, mesmo que ambas as linhas estejam no cache, pode causar uma pequena degradação de performance. Isso porque duas verificações deverão ser feitas. A coisa pode piorar se obtivermos um cache hit numa linha e um cache miss na outra. Então, evitar cruzar a barreira de uma linha é interessante. Como fazer isso?

Se cada linha tem 64 bytes isso significa que os 6 primeiros bits do endereço dizem a posição em uma linha. É claro que não vamos ficar contando bytes aqui… Uma regra geral é a mesma que usamos para a pilha: Mantenha suas variáveis alinhadas por DWORD (32 bits). Isso também vale para as variáveis locais (já que pilha está na memória e, portanto, é cacheável). Uma forma de fazer isso é declarando todos os tipos int e ponteiros primeiro, deixando os tipos short em segundo lugar e os char por último.

  char s[63];
  int x;

No exemplo acima é provável que ‘s’ esteja contido completamente em uma linha de cache, mas ‘x’ pode ter o seu primeiro byte na mesma linha e os 3 restantes na linha seguinte. Se usarmos ‘x’ como índice num loop, por exemplo, duas verificações no cache serão feitas, causando penalidades (hits ou misses). A simples inversão da declaração das variáveis pode melhorar muito a situação. A variável ‘x’ ficaria totalmente dentro de uma linha de cache e ‘s’ teria apenas 3 bytes na segunda linha. Já que ‘s’ é do tipo char, jamais termos duas verificações no cache para quaisquer dos itens de ‘s’.

Você pode estar se perguntando se não seria melhor alinhar as variáveis pelo início do cache (ou seja, tendo os 6 primeiros bits do endereço zerados)… Seria muito bom, mas seu programa ficaria maior (tanto a imagem binária quando a imagem ocupada na memória). Teríamos disperdício de bytes. E isso ainda causa um mal-uso do cache… No exemplo anterior, colocando ‘x’ antes de ‘s’, teríamos uma linha de cache com apenas 4 bytes ocupados (com a variável ‘x’ – os outros 60 seriam disperdiçados). Daí, para evitar disperdícios é sensato usarmos alinhamento por DWORD. Afinal, esse é o tamanho dos registradores, e do tipo int – que é o tipo mais usado, de qualquer maneira.

Quanto às instruções: É interessante manter o alinhamento também para as funções e em loops. Se conseguirmos manter uma função toda numa linha de cache, tanto melhor (só que isso é bem difícil de fazer – só se sua função for pequenininha!). O mesmo se aplica a um loop… Já que é difícil manter tudo em uma linha, pelo menos preocupe-se em manter a função e seus loops dentro do cache L1. Funções e loops muito extensos podem ser maiores que 32 kB e, nesses cacos, diversas linhas do cache serão invalidadas e recarregadas do cache L2 ou até mesmo da memória… Se não tomar cuidado a performance meticulosamente calculada pode degradar em bem mais de 100% ou até bem mais (em teoria, cada 8 bytes lidos da RAM tomam 1 ciclo de máquina adicional – ler o cache L2 inteiro pode gastar até 262144 ciclos extras!!!). É claro que o cache L1 não vai ser invalidado todo de uma vez só, mas a cada vez que o processador realiza um salto além da fronteira dos 32 kB, um conjunto novo de instruções precisa ser lido da RAM (ou do cache L2, se não houver cache miss nele), dai vocẽ pode ter a degradação acumulada dos 256 kciclos extras!

Resumindo:

  • Mantenha seus dados alinhados por DWORD e, se possível, ordenados por tamanho para não cruzar a fronteira dos 64 bytes;
  • Mantenha suas funções e loops relativamente pequenos (menores que 32 kB);

Qualquer coisa além disso é fine-tunning e precisa de medições meticulosas. Como eu não quero exagerar, as duas dicas acima atendem quase todas as necessidades de performance, em relação aos caches.

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s