Camada Zero · 12 · Hierarquia de Memória & Cache

Você ouve o tempo todo que acesso à memória é O(1). É uma mentira útil. Entre o registrador e o disco tem 6 ordens de grandeza de latência, e o cache decide quase tudo. Roda os padrões de acesso aqui embaixo e olha o hit rate despencar quando você perde a localidade.
← voltar à trilha
0Hits
0Misses
0%Hit rate
0Ciclos (miss = 100x hit)
Cada linha aqui é uma cache line (carrega de uma vez). O cache só segura 3 linhas por vez (LRU). Escolha o padrão e rode: olha quem fica verde (hit) e quem fica vermelho (miss).
na RAM (fora do cache) linha no cache hit miss
A CPU nunca lê 1 byte da RAM. Ela puxa uma cache line inteira (64 bytes) de uma vez. Se você lê em sequência, os vizinhos já vieram junto e saem de graça (localidade espacial). Se você pula pela memória, cada acesso é um miss e paga ~100x mais. É por isso que array contíguo ganha de lista encadeada na vida real, mesmo com o mesmo Big-O.
NívelLatência~Tamanho
Registrador<1 ns~ bytes
L1~1 ns~64 KB
L2~4 ns~1 MB
L3~15 ns~32 MB
RAM~100 ns~GBs
SSD~100 µs~TBs
Disco~10 ms~TBs

Loop cache-friendly vs não (Go)

// rápido: percorre na ordem da memória (row-major)
sum := 0
for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
        sum += m[i][j] // contíguo: cache hit
    }
}

// lento: pula uma linha inteira a cada passo
for j := 0; j < n; j++ {
    for i := 0; i < n; i++ {
        sum += m[i][j] // stride = n: cache miss toda hora
    }
}
Mesmo algoritmo, mesmo O(n²). Só trocando a ordem dos loops a versão de cima costuma rodar várias vezes mais rápido. O relógio mede cache; o Big-O não.

🧠 Desafio — Memória & Cache

Roda os padrões de acesso aqui de cima antes de responder. As duas últimas são de reflexão: escreve a sua e só então revela o modelo.

🔧 Prática — ache o bug

Os dois loops são O(n²), mas um é ~10x mais lento. Clica na linha que mata o cache.