Por que 8192 elementos estão travando seu código C++? Análise

Introdução: O número mágico 8192 e seu código ficando mais lento

Você já notou que seu código C++, que funcionava perfeitamente com 1000 ou 10000 elementos, de repente começa a ficar lento exatamente com 8192? Não, isso não é um bug do compilador nem uma maldição de programadores antigos. Este é um exemplo clássico de como a arquitetura do processador pode transformar seu algoritmo rápido em uma tartaruga.

Esta história começou com uma pergunta lendária no Stack Overflow: "Why is my program slow when looping over exactly 8192 elements?", que acumulou milhares de visualizações e se tornou um verdadeiro meme no mundo da High Performance Computing. Hoje, em 2025, com processadores ainda mais complexos, entender este problema não é apenas um fato curioso, mas uma habilidade real que diferencia um desenvolvedor júnior de um engenheiro que escreve código rápido.

Neste artigo, vamos analisar o que acontece sob o capô do seu processador, por que o tamanho 8192 (e seus múltiplos) são uma "zona vermelha" e como escrever código que seja consistentemente rápido com qualquer dado. Vamos lá!

1. Anatomia do problema: Cache misses e associatividade

Para entender a raiz do problema, precisamos observar a estrutura de um processador moderno. A operação mais lenta é o acesso à memória RAM. Para acelerar o acesso, o processador usa cache — uma memória pequena, mas muito rápida, localizada diretamente no chip.

1.1. Como o cache funciona (de forma bem resumida)

\n
• Cache L1: O mais rápido e menor (~32 KB por núcleo).
\n
• Cache L2: Um pouco mais lento, mas maior (~256-512 KB).
\n
• Cache L3: Compartilhado por todos os núcleos, o maior (vários MB).
\n

Os dados são carregados no cache não byte a byte, mas em blocos — cache lines (geralmente 64 bytes). Se o processador solicitar dados que não estão no cache, ocorre um cache miss, e ele é forçado a esperar o carregamento da RAM. Isso pode levar centenas de ciclos.

1.2. A maldição do 8192: Associatividade do cache

O cache não é apenas uma grande cesta. Ele é organizado em conjuntos (sets). Cada endereço de memória só pode ser colocado em um desses conjuntos. Isso é chamado de set-associative cache.

Imagine um estacionamento onde as vagas são agrupadas em fileiras. Seu carro (endereço de memória) só pode estacionar em uma fileira específica (conjunto). Se todas as vagas nessa fileira estiverem ocupadas, você precisa tirar um dos carros (despejar uma cache line) para liberar espaço.

Para muitos processadores modernos, os caches L1 e L2 são set-associative de 8 vias. Isso significa que cada conjunto pode ter 8 cache lines.

Agora, o ponto chave: o tamanho da cache line é de 64 bytes (512 bits). Se você estiver trabalhando com um array de int (4 bytes), uma cache line contém 16 elementos.

Ao percorrer um array com um passo igual a uma potência de dois, todos os elementos que você acessa podem ser mapeados para o mesmo conjunto de cache. Por exemplo, se você pegar cada 16º elemento, todos eles competirão pelos mesmos 8 slots no conjunto. Quando há mais elementos do que slots (por exemplo, ao percorrer um array de 8192 elementos que são mapeados para um único conjunto), o cache começa constantemente a "despejar" dados antigos e carregar novos. Isso é chamado de cache thrashing.

8192 é 2^13. Com um certo layout de dados na memória, exatamente esse número de elementos "acerta" perfeitamente as limitações de associatividade de um cache L1 típico (32 KB / 64 bytes = 512 conjuntos, e 8192 / 16 = 512, que se encaixa perfeitamente em cada conjunto).

2. Demonstração do problema em C++

Vamos ver um código que reproduz esse problema. Mediremos o tempo de percorrer um array bidimensional com diferentes passos.

#include <iostream>\n#include <vector>\n#include <chrono>\n\nconst int SIZE