Código cache-friendly em C++: o que é e por que é importante para a velocidade

Seu código está lento, embora o algoritmo seja ideal? Talvez ele não seja "amigo" do cache

Você já escreveu código em C++ que, em teoria, deveria funcionar rapidamente, mas na prática fica lento? Ou notou que percorrer uma matriz bidimensional por linhas e por colunas dá velocidades diferentes, embora a complexidade do algoritmo seja a mesma? Se sim, você se deparou com o cache-friendly e seu oposto — o código cache-unfriendly.

Hoje vamos analisar o que isso significa no nível do hardware, por que o cache não é apenas "mais uma memória", mas a chave para o desempenho, e como escrever código que o processador vai "amar". Sem abstrações complexas — apenas C++ e exemplos claros.

Por que o processador não pode simplesmente ler da memória RAM?

A velocidade do processador aumentou milhares de vezes nas últimas décadas, enquanto a velocidade da memória RAM (DRAM) aumentou apenas dezenas de vezes. Imagine um piloto de Fórmula 1 (processador) que precisa parar a cada segundo para abastecer (dados) de um caminhão que anda a 30 km/h (memória RAM). Triste e lento.

A solução é o cache da CPU: uma memória pequena, mas muito rápida, embutida diretamente no chip. Ela armazena cópias dos dados usados com frequência. Quando o processador precisa de dados, ele primeiro verifica o cache (L1 — o mais rápido, depois L2, L3). Somente se os dados não estiverem lá (cache miss), ele vai para a lenta memória RAM.

Aqui estão as latências aproximadas (em ciclos do processador):

\n
• Cache L1: ~3-5 ciclos
\n
• Cache L2: ~10-20 ciclos
\n
• Cache L3: ~30-50 ciclos
\n
• Memória RAM: ~100-300 ciclos
\n

A diferença entre L1 e RAM é de 50 a 100 vezes. É por isso que o código cache-friendly em C++ pode ser várias vezes mais rápido do que sua contraparte "não amigável".

Princípio da localidade: como o cache decide o que armazenar

O cache não copia um único byte — ele trabalha com blocos (cache lines), geralmente de 64 bytes. Quando você lê uma variável, o processador carrega todo o bloco que contém essa variável. E ele aposta em dois princípios:

\n
• Localidade espacial (Spatial locality): se você lê um elemento do array arr[i], provavelmente precisará em breve de arr[i+1].
\n
• Localidade temporal (Temporal locality): se você leu dados agora, provavelmente os acessará novamente em breve.
\n

Código cache-friendly é um código que maximiza o uso desses princípios. Vamos ver como isso funciona na prática.

Exemplo 1: Percorrendo uma matriz bidimensional — o clássico do gênero

Cache-unfriendly (código ruim)

const int SIZE = 1024;\nint matrix[SIZE][SIZE];\n\n// Percorrendo por colunas (column-major)\nfor (int j = 0; j < SIZE; ++j) {\n    for (int i = 0; i < SIZE; ++i) {\n        matrix[i][j] = i + j;\n    }\n}\n

Em C++, os arrays são armazenados em ordem row-major (por linhas). Ou seja, os elementos da linha matrix[0][0], matrix[0][1], matrix[0][2]... estão na memória sequencialmente. O loop externo por j (colunas) força o processador a pular por toda a linha a cada passo — cada acesso a matrix[i][j] é, muito provavelmente, um cache miss. O processador gasta tempo carregando novos blocos, enquanto os dados anteriores do cache são descartados.

Cache-friendly (código bom)

// Percorrendo por linhas (row-major)\nfor (int i = 0; i < SIZE; ++i) {\n    for (int j = 0; j < SIZE; ++j) {\n        matrix[i][j] = i + j;\n    }\n}\n

Agora percorremos a memória sequencialmente. Assim que carregamos o bloco com matrix[0][0], os próximos 15 elementos (com int de 4 bytes) já estão no cache! Isso proporciona um ganho de velocidade de 5 a 10 vezes