Por que a adição de arrays é mais rápida em dois loops do que em um: análise de erros C++

Por que a adição de arrays é mais rápida em dois loops do que em um? Análise do erro clássico do C++

Você já escreveu um código que parecia intuitivamente correto, mas funcionava devagar? E então, ao dividir um loop em dois, obteve uma aceleração de 2 a 3 vezes? Uma dor familiar. No Stack Overflow, há uma pergunta lendária que acumulou milhares de visualizações e centenas de comentários: «Why are elementwise additions much faster in separate loops than in a combined loop?». Hoje vamos analisar esse fenômeno de forma simples, com exemplos de código em C++ e sem teorias complicadas.

Isso não é mágica. São cache misses e a forma como o processador realmente acessa a memória. Se você programa em C++ e quer que seu código voe — leia com atenção. No final do artigo, há ações concretas que podem ser aplicadas agora mesmo.

O cerne do problema: dois loops vs um

Imagine que temos dois grandes arrays a e b, e queremos realizar a adição elemento a elemento e, em seguida, a multiplicação de cada elemento. A intuição sugere: «Vamos fazer um único loop para não ficar alternando o processador!».

Veja como fica o loop combinado:

const int N = 1000000;\nfloat a[N], b[N];\n\n// Um loop — faz tudo de uma vez\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];  // adição\n    a[i] = a[i] * 2.0f;  // multiplicação\n}

E agora dois loops separados:

// Primeiro loop — apenas adição\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];\n}\n\n// Segundo loop — apenas multiplicação\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] * 2.0f;\n}

É lógico supor que a primeira opção é mais rápida: menos custos indiretos na organização do loop. Mas na prática, é o contrário — a segunda opção geralmente é 2 a 3 vezes mais rápida. Por quê? Bem-vindo ao mundo da hierarquia de cache.

Cache misses: o principal inimigo do desempenho

Processadores modernos não acessam a memória RAM diretamente toda vez. Eles usam cache — uma memória rápida localizada no próprio chip. O cache tem vários níveis (L1, L2, L3), e cada nível seguinte é mais lento, mas maior.

Quando seu código lê ou escreve dados, o processador carrega um bloco inteiro (cache line) no cache — geralmente 64 bytes. Se a próxima requisição cair no mesmo bloco, é um hit (acerto). Se não, é um miss (erro), e o processador precisa esperar os dados da RAM lenta. Um único miss pode custar centenas de ciclos.

Agora, voltemos ao nosso exemplo. No loop combinado, em cada iteração acessamos a[i] e b[i] duas vezes: primeiro para leitura, depois para escrita. Enquanto trabalhamos com a[0] e b[0], o cache carrega suas cache lines. Mas na próxima iteração, vamos para a[1] e b[1] — pode ocorrer um miss se os dados estiverem em linhas de cache diferentes. Como resultado, ficamos constantemente «puxando» a memória, forçando o cache a recarregar.

Nos dois loops separados, é diferente. O primeiro loop lê sequencialmente a[i] e b[i] e escreve o resultado de volta. Os dados são lineares — o cache é previsível e funciona perfeitamente (localidade espacial). O segundo loop percorre novamente o mesmo array a — os dados já estão quentes no cache L1. Praticamente não há misses.

Principais erros que matam o desempenho

Erro nº 1 — misturar operações com diferentes arrays em um único loop. Se você puder dividir a lógica em duas passagens (especialmente com grandes volumes de dados) — faça isso. O cache agradecerá.

Erro nº 2 — ignorar o tamanho da cache line. 64 bytes equivalem a aproximadamente 16 floats ou 8 doubles. Se seus arrays têm passos estranhos ou você salta pelos índices de forma não sequencial, você garante cache misses.

Erro nº 3