CPU cache, locality & false sharing

Em setembro de 2014, na CppCon em Bellevue, Mike Acton — então engineering director da Insomniac Games (estúdio por trás de Ratchet & Clank, Spider-Man) — subiu ao palco com uma palestra que ficaria conhecida pelo título "Data-Oriented Design and C++". O argumento era polêmico para uma audiência de OOP: a orientação a objetos clássica, com sua ênfase em encapsulamento e hierarquia, ignora sistematicamente o que o hardware moderno realmente faz com seu código. A tese de Acton: "The purpose of all programs, and all parts of those programs, is to transform data from one form to another". Programas eficientes desenham layout de dados primeiro, código depois.

O argumento de Acton se ancorava em fato físico conhecido por engenheiros de jogos e sistemas embarcados há décadas, mas ignorado pela maioria do mainstream: RAM é lenta, cache é rápido, e a diferença entre as duas é enorme. Acessar um dado que está em L1 cache custa ~1 ns; o mesmo dado em RAM custa ~80 ns. Fator 80×. Como o hardware busca dados, e como os dados estão organizados em memória, definem se cada acesso vai ser hit (rápido) ou miss (lento).

Em sistemas web típicos, esse fator é diluído por I/O dominante (banco, rede). Mas em hot paths computacionais — game engines, ML inference, ferramentas de build, processamento de mídia, hot paths de bancos e brokers de mensagem —, locality de cache vira a diferença entre adequado e impressionante. Sêniores que tocam hot path precisam saber o que acontece debaixo, mesmo se na maior parte do trabalho a preocupação é distante.

Este conceito articula a hierarquia de cache moderna, explica o que são cache lines e como prefetcher de hardware funciona, mostra os padrões de acesso que exploram cache (locality espacial e temporal) e os que destroem (random access em estrutura grande, false sharing). Os exemplos vão dos clássicos (sequencial vs random sobre array) até os contraintuitivos (false sharing em contadores concorrentes). O conceito conecta com 04 (concorrência) e 08 (alocação) do módulo anterior; aqui o foco é o nível de cache da CPU.

A hierarquia moderna — L1, L2, L3, RAM

CPU moderna não acessa RAM diretamente para cada operação. Entre o registrador e a RAM, há três níveis de cache, cada um menor e mais rápido que o seguinte. Em CPU típica de servidor 2026 (Intel Xeon, AMD EPYC, ARM Graviton):

NÍVEL    TAMANHO    LATÊNCIA   COMPARTILHADO
L1d      32–48 KB   ~1 ns      por core (privado)
L1i      32–48 KB   ~1 ns      por core (privado, instruções)
L2       512K–2 MB  ~3 ns      por core (privado)
L3 (LLC) 16–256 MB  ~10 ns     entre cores (compartilhado)
RAM      GB         ~80 ns     entre cores

L1 é dividida em L1d (data) e L1i (instruções). L2 unifica os dois. L3 (Last-Level Cache, ou LLC) é compartilhada por todos os cores do mesmo socket — e é exatamente aí que a coordenação entre threads vira interessante (e onde false sharing vive).

Cada nível é "filtrado" pelo anterior. Acesso a dado tenta L1 primeiro; se miss, tenta L2; se miss, tenta L3; se miss, vai à RAM. Cada miss é mais caro que o anterior. Programa eficiente em performance é programa cujo padrão de acesso mantém os dados no nível mais próximo possível da CPU.

Cache line — a unidade de transferência

A CPU não busca dado byte a byte. Busca em unidades chamadas cache lines, de tamanho fixo — tipicamente 64 bytes em arquiteturas x86_64 modernas (alguns ARM têm 128 bytes). Quando você lê 1 byte de RAM, a CPU traz 64 bytes em volta dele para o cache. Os 63 bytes adicionais ficam disponíveis grátis — se você usar.

Esse fato simples define quase tudo sobre performance de cache. Iterar sequencialmente sobre um array explora cache line: você lê um elemento, os 8 vizinhos (em array de int de 8 bytes) já estão em cache, próximo acesso é hit. Iterar aleatoriamente sobre o mesmo array destrói cache: cada elemento é em cache line diferente, miss em cada acesso.

Em estruturas de dados, isso muda decisões fundamentais. Lista encadeada (cada nó alocado separadamente, com ponteiro para o próximo) tem péssima locality: cada node->next é tipicamente cache miss. Array contíguo de structs tem ótima locality: iterar é sequencial, prefetcher do hardware antecipa as próximas cache lines. Em hot paths, array beats lista encadeada por fator de 5–20×, mesmo que a complexidade assintótica seja a mesma O(n).

Os dois tipos de locality

Cache funciona porque programas exibem dois padrões de acesso a dados:

Locality espacial. Se você acessa um endereço, provavelmente vai acessar endereços próximos em breve. Iterar sobre array, ler campos de uma struct em sequência — todos exploram locality espacial. O prefetcher de hardware reconhece o padrão e busca cache lines à frente preventivamente.

Locality temporal. Se você acessa um endereço, provavelmente vai acessar o mesmo endereço de novo em breve. Loop que opera sobre o mesmo elemento, função chamada várias vezes com mesmos argumentos — exploram locality temporal. Cache mantém os dados recentemente acessados.

Programas com bom locality acessam padrões previsíveis; programas com péssima locality acessam aleatoriamente em estrutura grande. A regra do design é simples: organize dados para que padrões de acesso explorem as duas localities.

Struct of Arrays vs Array of Structs

O padrão mais célebre do data-oriented design é a escolha entre AoS e SoA — Array of Structs e Struct of Arrays. Considere o cenário: você tem 10.000 entidades com posição (x, y, z) e velocidade (vx, vy, vz). Como armazenar?

Array of Structs (AoS): a forma OOP natural.

struct Particle {
    float x, y, z;        // 12 bytes
    float vx, vy, vz;     // 12 bytes
    // 24 bytes por struct, sem padding
}
Particle particles[10000];

// update positions
for (int i = 0; i < 10000; i++) {
    particles[i].x += particles[i].vx * dt;
    particles[i].y += particles[i].vy * dt;
    particles[i].z += particles[i].vz * dt;
}

O acesso lê x, vx juntos (locality boa dentro da struct). O problema aparece em outro cenário — operação que só toca posição:

// só lê posições, não velocidades
for (int i = 0; i < 10000; i++) {
    sum_x += particles[i].x;
}

Cada cache line de 64 bytes traz ~2.5 structs (24 bytes cada), e portanto contém os x, y, z, vx, vy, vz de várias particles. Você lê só x de cada, mas a CPU trouxe os 23 bytes de y, z, vx, vy, vz que vão ser ignorados. Banda de memória desperdiçada — você usa só ~17% do que foi trazido para cache.

Struct of Arrays (SoA): a forma data-oriented.

struct ParticleSystem {
    float* x;     // array de 10000 floats contíguos
    float* y;
    float* z;
    float* vx;
    float* vy;
    float* vz;
}

// só lê posições
for (int i = 0; i < 10000; i++) {
    sum_x += system.x[i];
}

Agora cada cache line traz 16 floats consecutivos do array x. Banda de memória 100% usada para o cálculo. Performance pode ser 4–8× melhor para operações que tocam um subset dos campos.

Quando AoS ganha: operações que tocam vários campos simultaneamente (update de posição+velocidade ao mesmo tempo). Quando SoA ganha: operações que tocam um ou poucos campos sobre todas as entidades. Em um sistema com várias operações distintas, a escolha é trade-off — e às vezes vale ter ambas as representações (vetor de structs de imutáveis + arrays paralelos de mutáveis).

Game engines modernas (ECS — Entity Component System) usam SoA religiosamente. Unity DOTS (Data-Oriented Technology Stack), Unreal Engine 5 com Mass Entity, Bevy em Rust — todos exploram a ideia. Em domínio de aplicação web, raramente vale a complicação; em hot paths numéricos (ML, simulação, processamento de mídia), o ganho compensa.

False sharing — o bug invisível em código concorrente

O fenômeno mais surpreendente em CPU cache é false sharing. Acontece quando duas threads escrevem em variáveis que são logicamente independentes mas fisicamente residem na mesma cache line. Por causa do protocolo de coerência de cache (MESI ou variantes), cada escrita força invalidação da cache line nas outras CPUs, criando tráfego de coordenação ao nível de cache que destrói performance.

O exemplo canônico: dois contadores, cada um incrementado por uma thread diferente.

// caso ruim — false sharing
struct Contadores {
    long counter1;       // thread A incrementa
    long counter2;       // thread B incrementa
    // ambos cabem na mesma cache line de 64 bytes
};

// thread A
for (int i = 0; i < 1_000_000_000; i++) c.counter1++;

// thread B (em paralelo)
for (int i = 0; i < 1_000_000_000; i++) c.counter2++;

Conceitualmente, as threads não compartilham nada — cada uma escreve em variável própria. Mas a cache line é compartilhada fisicamente, e o protocolo MESI exige que cada CPU "ganhe" a cache line antes de escrever, invalidando a cópia da outra. O resultado: o que deveria ser perfeitamente paralelo vira sequencial, e pior — vira sequencial com overhead de coordenação. Performance pode ser 10× pior que sequencial single-thread.

A solução é forçar as variáveis a ficarem em cache lines diferentes, com padding:

// caso bom — sem false sharing
struct ContadoresPadded {
    long counter1;
    char padding[56];    // empurra counter2 para próxima cache line
    long counter2;
};

Ou em linguagem com suporte a alinhamento explícito, usar atributo:

// C# 9+
[StructLayout(LayoutKind.Explicit, Size = 128)]  // 2 cache lines
public struct PaddedCounter
{
    [FieldOffset(0)]   public long Value;
    // o resto é padding
}

// Java tem @Contended (sun.misc.Contended em pré-9, jdk.internal.vm.annotation.Contended em 9+)

// Go: sem atributo dedicado, mas idiomático é
type PaddedCounter struct {
    value uint64
    _pad  [56]byte    // padding manual
}

O experimento que mostra cache em ação

Os números acima ficam abstratos até você medir em sua máquina. O experimento abaixo executa em todas as linguagens mainstream e mostra a hierarquia de cache diretamente.

using System.Diagnostics;

const int N = 64 * 1024 * 1024 / sizeof(int);   // 64 MB de ints
var arr = new int[N];
for (int i = 0; i < N; i++) arr[i] = i;

// sequencial — locality espacial perfeita
var sw = Stopwatch.StartNew();
long sum = 0;
for (int i = 0; i < N; i++) sum += arr[i];
sw.Stop();
Console.WriteLine($"sequencial: {sw.Elapsed.TotalMilliseconds:F2} ms");

// strided — pula cache lines
sw.Restart();
sum = 0;
for (int stride = 0; stride < 16; stride++)
    for (int i = stride; i < N; i += 16)
        sum += arr[i];
sw.Stop();
Console.WriteLine($"strided 16: {sw.Elapsed.TotalMilliseconds:F2} ms");

// random — pessimo
var rnd = new Random(42);
var indices = Enumerable.Range(0, N).OrderBy(_ => rnd.Next()).ToArray();
sw.Restart();
sum = 0;
for (int i = 0; i < N; i++) sum += arr[indices[i]];
sw.Stop();
Console.WriteLine($"random:     {sw.Elapsed.TotalMilliseconds:F2} ms");

# Python tem GIL, então threading não paraleliza CPU bem.
# multiprocessing tem overhead de IPC. Para demonstrar false
# sharing, vamos usar numpy + numba.

import numpy as np
from numba import njit, prange
import time

# array compartilhado entre "threads" via prange (paralelo OpenMP-like)
N = 100_000_000
data = np.zeros(8, dtype=np.int64)    # 8 int64 = 64 bytes = 1 cache line

@njit(parallel=True)
def increment_close(data, n):
    for thread in prange(2):
        for i in range(n):
            data[thread] += 1     # data[0] e data[1] na mesma cache line!

@njit(parallel=True)
def increment_far(data, n):
    for thread in prange(2):
        for i in range(n):
            data[thread * 7] += 1  # data[0] e data[7]: 56 bytes apart, cache lines diferentes

t0 = time.perf_counter()
increment_close(data.copy(), N)
print(f"close (false sharing):   {time.perf_counter() - t0:.2f}s")

t0 = time.perf_counter()
increment_far(data.copy(), N)
print(f"far (sem false sharing): {time.perf_counter() - t0:.2f}s")

package main

import (
    "fmt"
    "sync"
    "sync/atomic"
    "time"
)

const iterations = 100_000_000

// versão ruim: contadores adjacentes
type Bad struct {
    a uint64
    b uint64
    // a e b cabem na mesma cache line (16 bytes < 64)
}

// versão boa: padding entre contadores
type Good struct {
    a   uint64
    _   [56]byte    // padding até completar 64 bytes
    b   uint64
    _   [56]byte
}

func runBad() time.Duration {
    var b Bad
    var wg sync.WaitGroup
    wg.Add(2)
    start := time.Now()
    go func() {
        defer wg.Done()
        for i := 0; i < iterations; i++ {
            atomic.AddUint64(&b.a, 1)
        }
    }()
    go func() {
        defer wg.Done()
        for i := 0; i < iterations; i++ {
            atomic.AddUint64(&b.b, 1)
        }
    }()
    wg.Wait()
    return time.Since(start)
}

func runGood() time.Duration {
    var g Good
    var wg sync.WaitGroup
    wg.Add(2)
    start := time.Now()
    go func() {
        defer wg.Done()
        for i := 0; i < iterations; i++ {
            atomic.AddUint64(&g.a, 1)
        }
    }()
    go func() {
        defer wg.Done()
        for i := 0; i < iterations; i++ {
            atomic.AddUint64(&g.b, 1)
        }
    }()
    wg.Wait()
    return time.Since(start)
}

func main() {
    fmt.Printf("false sharing:    %v\n", runBad())
    fmt.Printf("sem false sharing: %v\n", runGood())
}

Prefetching — a ajuda silenciosa do hardware

A CPU moderna não espera você pedir dado para começar a buscá-lo. O prefetcher observa o padrão de acesso e busca cache lines à frente preventivamente. Há prefetcher de hardware (na CPU, transparente) e prefetch de software (instruções como __builtin_prefetch em GCC).

O hardware prefetcher reconhece padrões simples: sequencial (forward, backward), strided regular. Não reconhece random nem indireção via ponteiro. Por isso iterar array é fast (prefetcher antecipa); iterar lista encadeada é slow (impossível antecipar — o próximo endereço só é conhecido após carregar o nó atual).

A consequência prática: arrays venceram listas encadeadas em quase todo cenário em hardware moderno. A vantagem teórica de O(1) para inserção em meio de lista raramente compensa a penalidade de cache. Em C++, std::vector superando std::list em quase tudo é sintoma; em Java/.NET, ArrayList superando LinkedList; em Python, list é sempre array; em Go, []T é o default e container/list é raramente usado.

O que isso significa para você no dia a dia

A maior parte do trabalho de aplicação web não toca hot paths sensíveis a cache. Não vale otimizar manualmente para cache no controlador HTTP. Mas há casos em código de aplicação que ganham significativamente com awareness:

Loops sobre coleções grandes em hot path. Iterar sobre um milhão de objetos, somando ou transformando — sequencial sobre array vence indireção. Considere List<T> sobre LinkedList<T>; ImmutableArray sobre estruturas com ponteiros.

Structs vs classes em .NET. Struct pequena (até ~16 bytes) frequentemente é mais rápida que classe — sem boxing, sem alocação no heap, melhor locality em arrays. Para ValueObjects de domínio, struct é frequentemente a escolha certa.

Concorrência em counters / state. Múltiplas threads atualizando estado adjacente é receita para false sharing. Em .NET, PaddedAtomic; em Java, @Contended; em Go, padding manual em struct.

Layout de objetos hot. Em .NET, [StructLayout(LayoutKind.Sequential, Pack=1)] pode ajudar a compactar struct. Em Go, ordenar campos do maior para o menor reduz padding interno (compilador insere padding para alinhar).

Quando NÃO se preocupar com cache

Para a maioria das aplicações de produto, cache não é o gargalo. Antes de gastar tempo otimizando layout de cache, verifique:

O sistema é I/O-bound? Se 95% do tempo é em banco/rede, otimizar cache CPU é desperdício. Foque no I/O.

O profile mostra hot path com cache miss? Sem evidência de cache miss dominante, otimização especulativa. Use perf stat em Linux para medir cache misses; se o ratio é baixo, não vale tempo.

O ônus de manutenção compensa o ganho? Layout SoA ou padding manual torna código mais difícil de ler. Em hot path bem identificado e estável, compensa. Em código que muda toda semana, custo é alto demais.

Padrões reconhecíveis no profile

Cache miss é difícil de ver em profile padrão (CPU profile mede tempo, não mostra causa). Ferramentas que ajudam:

perf stat (Linux) mede counters de hardware:

perf stat -e cache-misses,cache-references,cycles,instructions ./meu_programa
# saída:
#   X cache-misses
#   Y cache-references
#   ratio = X/Y * 100%
# acima de 10% é alto; investigar layout

Intel VTune e AMD uProf são profilers comerciais que mostram cache miss por linha de código. Em hot paths críticos, são ferramenta apropriada.

perf c2c (Linux moderno, baseado em eBPF) detecta especificamente false sharing contention.

Por que importa para a sua carreira

Conhecimento de cache CPU separa sêniores que tocam hot path de sêniores que tocam só borda. Em entrevistas para vagas em sistemas críticos (engines, brokers, databases, ML inference), perguntas sobre cache line e false sharing são reais — não apenas curiosidade acadêmica. Em pos-mortem de "performance estranha" (sistema rápido em testes, lento em produção; escalabilidade subaprouvel), false sharing é causa candidata frequente, e quem reconhece o sintoma encurta diagnóstico em horas. Em discussão de design de estruturas de dados em sistema de alto throughput, articular SoA vs AoS é vocabulário que distingue. Mesmo em times que não tocam hot path, o conhecimento forma a base para entender por que certos benchmarks falham — "essa otimização melhorou 5%, e era esperado 30%; provavelmente cache miss continuou alto".

Como praticar

1. Reproduzir a hierarquia de cache. Implemente o experimento sequencial vs random vs strided em sua linguagem principal. Varie o tamanho do array de 1 KB até 1 GB; plote o tempo por elemento em função do tamanho. Você vai ver "patamares" correspondentes a L1, L2, L3, RAM. Esse gráfico, uma vez visualizado, fixa a hierarquia permanentemente.
2. Demonstrar false sharing. Implemente o experimento de Go (ou equivalente em C# ou C++) que compara contadores adjacentes vs paddados. Meça a diferença em sua máquina. Plote como função do número de threads. Identifique a fronteira entre "rápido" e "false sharing começa a doer". Esse exercício torna o fenômeno tangível.
3. Auditoria de hot path. Em algum sistema seu, identifique um loop quente que opera sobre coleção grande. Use perf stat -e cache-misses,cache-references (ou equivalente no Windows: ETW + WPA) para medir o ratio. Se acima de 10%, hipótese é cache miss dominante. Refatore para layout mais cache-friendly (array contíguo, struct compacta). Mensure de novo. Documente o antes/depois — esse é o tipo de trabalho que gera respeito do time.