CS Fundamentals Trainer · Guias
A hierarquia de memória e o Big-O na prática
Linhas de cache e localidade, por que o mesmo laço O(n) pode ser 18 vezes mais lento, ordem por linhas contra por colunas, layouts de structs, listas ligadas, predição de desvios e quando o fator constante vence o expoente, com experimentos medidos em C.
38 min de leitura
A notação Big-O diz como o trabalho cresce com a entrada: uma busca em hash é O(1), uma ordenação é O(n log n), a travessia de uma lista ligada é O(n). É a ferramenta certa para escolher entre um algoritmo quadrático e um linearítmico. É a ferramenta errada para escolher entre dois algoritmos da mesma ordem, e pode enganar em tamanhos pequenos, porque esconde um fator constante e, mais importante hoje, o fato de que nem todos os acessos à memória custam o mesmo. Uma leitura do cache L1 leva cerca de um nanossegundo; uma leitura da memória principal leva mais de cem vezes isso. Neste guia medi os dois efeitos com pequenos programas em C e Python (código no apêndice) e extraí as regras que decorrem deles.
A máquina era um servidor virtual de dois núcleos (Xeon a 2,1 GHz, linhas de cache de 64 bytes, um cache de dados L1 de 48 KB e 2 MB de L2 por núcleo). Todo número deste guia é específico dessa máquina e da forma como executei o teste: o modelo do processador e o tamanho dos seus caches, a velocidade da memória, o hipervisor e os vizinhos no mesmo host, a versão e as flags do compilador, o sistema operacional e o momento. Hardware diferente dá tempos absolutos diferentes, posições diferentes para os degraus na tabela de latência e proporções diferentes (uma CPU de desktop com um L2 maior, um chip de celular ou um servidor com prefetching diferente discordará de vários deles). Trate a forma dos resultados como a lição (o que cresce, o que fica plano, em que direção aponta cada efeito), não qualquer número isolado. A seção "Quanto confiar nesses números" diz quão repetíveis eles foram aqui e como medir na sua própria máquina.
1. A hierarquia de memória
Uma CPU faz algumas operações por nanossegundo, mas a memória principal (DRAM) não consegue entregar dados tão rápido. Os computadores cobrem a diferença com caches: memórias pequenas e rápidas entre a CPU e a RAM que guardam cópias dos dados usados recentemente.
Diagram: Each level is bigger and slower than the one above
A unidade de transferência é a linha de cache (64 bytes na maioria das CPUs hoje). Ler um byte traz a linha inteira para o cache; os 63 bytes seguintes passam a custar quase nada. Os programas são rápidos quando têm localidade: temporal (os mesmos dados de novo em breve) e espacial (dados perto do que acabou de ser usado). O hardware também faz prefetch: quando vê acessos avançando pela memória em um padrão regular, começa a carregar as linhas seguintes antes de o programa pedi-las.
Medindo a hierarquia
Para medir a latência de cada nível, construí um ciclo embaralhado aleatoriamente por um array e o segui: cada leitura precisa do resultado da anterior, então a CPU não pode sobrepô-las nem fazer prefetch. O tempo por passo, conforme o array cresce:
| Tamanho do array | Tempo por leitura dependente | Cabe em |
|---|---|---|
| 16 KB | 1,9 ns | L1 |
| 64 KB | 3,1 ns | entre L1 e L2 |
| 256 KB | 5,5 ns | L2 |
| 1 MB | 8 ns | L2 |
| 4 MB | 24 ns | L3 |
| 16 MB | 48 ns | L3 |
| 64 MB | 135 ns | em grande parte memória principal |
| 256 MB | 140 ns | memória principal |
Os degraus na tabela são os níveis de cache: cada vez que o working set ultrapassa um nível, a latência salta. Ler da memória principal foi cerca de 70 vezes mais lento que do L1. (A máquina virtual informa um L3 muito grande (260 MB) compartilhado com outros inquilinos do host, então o último degrau aparece tarde, e a quantidade de L3 que este programa realmente recebe depende do que os vizinhos estão fazendo. No seu computador os degraus estarão em tamanhos diferentes.) O significado prático é que a velocidade de um laço depende do tamanho dos dados que ele toca tanto quanto de quantos passos faz.
2. Sequencial contra aleatório: o mesmo Big-O, 18 vezes de diferença
Somei 64 milhões de inteiros (256 MB) duas vezes. Os dois laços fazem exatamente 64 milhões de somas, então os dois são O(n):
| Padrão de acesso | Tempo | Por elemento |
|---|---|---|
| em ordem | 43 ms | 0,64 ns |
| em ordem aleatória (por um array de índices) | 762 ms | 11,4 ns |
A ordem aleatória foi cerca de 18 vezes mais lenta para o mesmo número de operações. Em ordem, cada linha de cache trazida serve 16 inteiros e o prefetcher se mantém à frente do laço; em ordem aleatória, quase todo acesso é um cache miss que precisa esperar pela memória. O sistema de memória consegue sobrepor vários misses independentes, e é por isso que 11 ns é menos que a latência de 140 ns acima, mas não consegue escondê-los.
Stride: pagando pela linha inteira
Para ver a própria linha de cache, toquei o mesmo número de elementos do array com um passo (stride) crescente, em um array de 256 MB:
| Stride (ints) | 1 | 2 | 4 | 8 | 16 | 32 | 64 |
|---|---|---|---|---|---|---|---|
| Tempo por acesso | 1,6 ns | 1,8 ns | 2,6 ns | 4,2 ns | 6,4 ns | 9,2 ns | 11,1 ns |
Com stride 1, o acesso seguinte quase sempre está numa linha já carregada. Conforme o stride cresce, mais acessos precisam de uma linha nova, até que com 16 ints (64 bytes) cada acesso toca a sua própria linha. O custo continua subindo além disso, porque strides maiores também cruzam páginas e derrotam o prefetcher e o cache de tradução de endereços (veja sistemas operacionais sobre páginas e a TLB). O ponto: usar um int de cada linha de cache é pagar por dezesseis.
Percorra um pequeno cache, com um array disposto de forma contígua e com os mesmos elementos espalhados, e veja quais acessos acertam:
Interactive animation: cache lines
Com linhas de 64 bytes contendo 8 elementos cada, os 24 acessos em ordem tiveram 3 misses (13%), um por linha; no layout espalhado, os 24 deram miss. Esta é toda a história desta seção em miniatura.
3. O layout dos dados é uma escolha de algoritmo
Row-major contra column-major
Um array bidimensional em C, Go, Rust ou Java é armazenado linha após linha. Andar ao longo de uma linha toca endereços consecutivos; descer por uma coluna salta uma linha inteira a cada vez. Para uma matriz de 4096 por 4096 inteiros (64 MB), a soma percorrendo as linhas primeiro levou 10 ms e percorrendo as colunas primeiro 133 ms, 13 vezes mais, com aritmética idêntica. A ordem dos laços não é uma microotimização: pode ser o custo dominante. (Fortran, R e MATLAB armazenam colunas primeiro, então o conselho se inverte conforme a linguagem.) Os algoritmos em blocos ("tiled") para multiplicação de matrizes e processamento de imagens existem exatamente por isso: reordenam o trabalho para que um pequeno bloco de dados fique no cache enquanto é reutilizado.
Array de structs contra struct de arrays
Suponha que você tem 8 milhões de registros de 64 bytes cada e precisa somar um campo de 4 bytes:
| Layout | Tempo |
|---|---|
| array de structs de 64 bytes | 32,5 ms |
| um array separado contendo só esse campo | 5,0 ms |
O layout de structs carrega 64 bytes (uma linha inteira) para cada 4 bytes que usa, então move 16 vezes mais dados e leva cerca de 6,5 vezes mais tempo. Um layout de struct de arrays (colunar) mantém cada campo contíguo. É a ideia por trás dos bancos de dados colunares e de formatos analíticos como o Parquet, e por trás dos sistemas entidade-componente em jogos: quando as consultas tocam poucas colunas de muitas linhas, guarde as colunas juntas. Quando você lê registros inteiros um por vez, o layout por linhas é melhor, que é a mesma troca entre row stores e column stores em bancos de dados.
Listas ligadas
Uma lista ligada é O(n) para percorrer, e um array também. Construí uma lista de 4 milhões de nós (64 MB) e a percorri cinco vezes, com os nós dispostos em ordem na memória e depois com a mesma lista espalhada:
| Layout na memória | Por nó |
|---|---|
| nós alocados em ordem | 3,4 ns |
| nós espalhados | 130 ns |
A lista espalhada foi cerca de 38 vezes mais lenta, e cada leitura espera pela anterior, que é o caso de perseguição de ponteiros da primeira tabela. Uma lista construída alocando nós um após o outro muitas vezes fica em ordem no começo e se espalha conforme o programa roda, apaga e realoca. Mesmo a lista ordenada foi mais lenta que a soma do array (3,4 ns contra 0,64 ns), porque cada nó tem 16 bytes com um ponteiro e o laço é serializado pela dependência. É por isso que a sequência padrão na maioria das linguagens é um array dinâmico (ArrayList, Vec, slice, std::vector), que LinkedList tem tão poucos usos, e que "inserir no meio é O(1) com uma lista mas O(n) com um array" muitas vezes perde na prática: achar a posição custa uma travessia de qualquer modo e, abaixo de certo tamanho, deslocar um bloco contíguo é mais barato que perseguir ponteiros.
Quando dados contíguos não são a resposta
As medições acima tratam todas de leitura. O conselho sobre layout depende de como os dados são usados e, acima de tudo, de como eles mudam:
- Inserir ou apagar no meio de um array grande move tudo o que vem depois. Medi a inserção numa posição aleatória de um array de
intcommemmove, e a mesma inserção numa lista ligada cujos nós estão espalhados na memória:
| Elementos | Array: inserir em uma posição aleatória | Lista: andar até a posição, depois inserir | Lista: inserir depois de um nó que você já tem |
|---|---|---|---|
| 1 000 | 37 ns | 0,9 µs | 24 ns |
| 16 000 | 0,5 µs | 48 µs | 30 a 40 ns |
| 256 000 | 12 µs | 4,2 ms | 75 a 100 ns |
| 1 024 000 | 74 a 87 µs | 61 a 69 ms | 100 a 120 ns |
Quando você precisa achar a posição primeiro, o array vence por larga margem em todos os tamanhos (o memmove roda na largura de banda da memória, a caminhada na lista é uma cadeia de cache misses), e é por isso que a "inserção O(1)" de uma lista tão raramente compensa. Mas quando o array chega a centenas de milhares de elementos, cada inserção custa dezenas de microssegundos e cresce linearmente, e quando você já tem o nó (um cache LRU, em que uma tabela hash entrega a entrada e uma lista duplamente ligada a move para a frente; a fila de um escalonador; uma lista intrusiva em um kernel) a inserção na lista fica em cerca de 0,1 µs enquanto a do array continua crescendo. A comparação certa é a da operação inteira com o seu padrão de acesso real, nos seus tamanhos.
- Crescer um bloco contíguo pode movê-lo. Um array dinâmico que dobra de tamanho quando enche copia todos os seus elementos e invalida todo ponteiro e referência para dentro dele. Se outro código guarda endereços de elementos (observadores, grafos com arestas, handles), você precisa de armazenamento estável: uma lista ou um deque, um pool ou uma arena com índices em vez de ponteiros, ou uma estrutura em blocos. As adições são O(1) amortizado, mas uma adição pode custar uma cópia inteira, o que importa para código sensível a latência.
- Dados ordenados com muitas inserções precisam de uma estrutura, não de um array ordenado. Uma árvore balanceada, uma skip list ou uma B-tree mantém as chaves ordenadas com inserção O(log n); a B-tree é o compromisso no tema deste guia, com nós largos contendo arrays ordenados para que cada passo leia algumas linhas de cache. Para busca por chave sem ordem, uma tabela hash vence a varredura de um array quando n passa de algumas dezenas.
- Struct de arrays tem um custo nas escritas e no código. Atualizar ou mover um registro inteiro toca vários arrays (várias linhas de cache em vez de uma), adicionar ou apagar um registro significa manter todos os arrays em sincronia, e o código é mais difícil de ler. Mantenha o array de structs quando você lê e escreve registros inteiros, ou quando os registros são poucos.
- Escritores concorrentes. As estruturas contíguas compartilhadas entre threads sofrem de false sharing (duas threads escrevendo elementos diferentes na mesma linha de cache invalidam o cache uma da outra) e de locks grosseiros; dados por thread, padding ou estruturas projetadas para concorrência podem importar mais que o layout de uma varredura de thread única.
- Dados muito grandes, esparsos ou de tamanho variável. Uma tabela quase vazia, strings de muitos comprimentos diferentes e documentos aninhados não são bem servidos por um array plano simples; formatos comprimidos, esparsos ou colunares com dicionário são, e parte do ganho está em ler menos bytes, não na contiguidade.
- Dados pequenos. Abaixo de algumas dezenas de elementos o layout raramente importa; a clareza vence.
4. Desvios: o outro custo oculto
As CPUs modernas correm à frente prevendo para que lado vai cada if. Uma predição correta é barata, mas não é de graça: o desvio ainda ocupa um slot de instrução e um lugar nas tabelas do preditor, um desvio tomado pode limitar quantas instruções são buscadas por ciclo, um laço quente com muitos desvios pode estourar o preditor de modo que desvios diferentes interfiram uns nos outros (aliasing), e o trabalho feito no caminho previsto depende de uma especulação que a CPU precisa conseguir rastrear e, se estiver errada, desfazer. Uma predição errada joga fora o trabalho em andamento e custa cerca de 10 a 20 ciclos (o número exato depende do pipeline da CPU). Então a diferença de 5,6 vezes abaixo mede erros de predição; não significa que desvios previsíveis não custam nada, e uma formulação sem desvios pode ser um pouco mais rápida mesmo quando o desvio seria bem previsto (e mais lenta quando não seria, já que faz o trabalho dos dois lados). Somei os bytes maiores ou iguais a 128 em 32 milhões de bytes aleatórios, quatro vezes, primeiro com dados aleatórios e depois com os mesmos dados ordenados:
| Dados | Tempo |
|---|---|
| ordem aleatória | 693 ms |
| ordenados | 124 ms |
Os dados ordenados foram 5,6 vezes mais rápidos, com trabalho idêntico, porque o desvio fica então verdadeiro por uma longa sequência e falso por uma longa sequência, e o preditor quase sempre acerta (ainda não é de graça, só barato); com dados aleatórios ele erra cerca de metade das vezes. (Para fazer o teste tratar de desvios, forcei o compilador a manter o desvio com uma instrução asm vazia. Sem ela, um compilador otimizador tipicamente transformaria a condição em código sem desvios e não mostraria diferença. É um lembrete de que micro-benchmarks pedem cuidado.) A consequência para o projeto é leve, mas real: desvios dependentes de dados em um laço quente com dados imprevisíveis são caros, e dados ordenados, particionados ou em lotes ajudam.
5. Quando o Big-O e as constantes discordam
Entradas pequenas
Para n pequeno, o fator constante decide. Busquei em um array ordenado de inteiros com uma varredura linear e com uma busca binária (O(n) contra O(log n)), em posições aleatórias:
| n | Varredura linear | Busca binária |
|---|---|---|
| 4 | 9 ns | 14 ns |
| 16 | 15 ns | 27 ns |
| 64 | 30 ns | 41 ns |
| 256 | 77 ns | 57 ns |
| 1 024 | 206 ns | 77 ns |
| 16 384 | 3 043 ns | 102 ns |
| 262 144 | 52 484 ns | 157 ns |
| 1 048 576 | 215 391 ns | 245 ns |
Abaixo de cerca de 100 elementos o algoritmo "pior" vence, porque uma varredura linear tem desvios previsíveis e localidade perfeita, enquanto a busca binária tem um desvio imprevisível em cada passo. Acima de algumas centenas de elementos, o algoritmo O(log n) vence por uma margem crescente: com um milhão de elementos ele é quase mil vezes mais rápido. As bibliotecas padrão codificam esse conhecimento: as rotinas de ordenação passam para o insertion sort em partições pequenas, e as B-trees usam nós largos pesquisados linearmente ou com uma pequena busca binária dentro do nó, porque um nó é dimensionado para caber em algumas linhas de cache (ou em uma página de disco).
O mesmo efeito no Python, onde a sobrecarga do interpretador é grande e a busca é feita em C: um k in list custa 35 ns para 2 elementos e 360 ns para 64, enquanto k in set fica em 30 a 40 ns para qualquer tamanho (500 000 ns para uma lista de 100 000 contra 38 ns para o set). Construir um set de 1 000 itens custa 8,6 µs, cerca de duas varreduras da lista, então o set se paga depois de cerca de duas buscas. Para um punhado de itens a lista serve; a lição não é "use sempre um set", mas "saiba quantas buscas e quantos elementos".
O Big-O esconde a constante, a linguagem e o layout
Um algoritmo com expoente melhor pode perder para n realistas se tiver constantes grandes ou má localidade (algoritmos rápidos de multiplicação de matrizes, muitas estruturas em árvore, tabelas hash com encadeamento contra endereçamento aberto). E a linguagem multiplica as constantes: no teste em Python, somar 10 milhões de inteiros numa lista levou 63 ms e num array('q') 111 ms, porque o array precisa criar um inteiro Python para cada elemento que entrega; o array economiza memória (são 81 MB contra 80 MB de ponteiros mais 28 bytes para cada objeto inteiro, então uma lista Python de inteiros custa mais de 350 MB no total), mas não tempo. Os efeitos de cache deste guia são medidos em C porque a sobrecarga do Python os mascararia; em Python, o equivalente é empurrar os laços para bibliotecas escritas em C (NumPy, built-ins), que então desfrutam do layout contíguo.
6. Quanto confiar nesses números
Uma única execução de um benchmark dá uma amostra de uma grandeza ruidosa. Para ver o quanto, executei o programa C inteiro cinco vezes seguidas na mesma máquina e comparei os resultados:
| Grandeza | Menor | Mediana | Maior |
|---|---|---|---|
| Soma sequencial contra aleatória, razão | 15,6 | 19,0 | 20,6 |
| Linhas primeiro contra colunas primeiro, razão | 10,5 | 12,3 | 12,6 |
| Array de structs contra array de um campo, razão | 6,3 | 6,5 | 7,4 |
| Dados de desvio ordenados contra aleatórios, razão | 5,0 | 5,7 | 5,8 |
| Lista espalhada contra ordenada, razão | 39,4 | 40,5 | 41,8 |
| Leitura de um array do tamanho do L1 (16 KB), ns | 1,8 | 1,8 | 2,8 |
| Leitura de um array de 256 MB, ns | 152 | 154 | 156 |
Então a variação de execução para execução em uma máquina foi de cerca de 3% a 60% da mediana, dependendo da medição (as medições curtas do L1 e da soma sequencial, que duram apenas alguns milissegundos, são as menos estáveis), e as razões no texto (18, 13, 6,5, 5,6, 38) são execuções únicas que ficam dentro destas faixas ou perto delas, mas não são as medianas. Elas também mudariam com outra máquina, e as conclusões não. Uma forma justa de relatar os resultados é a mediana e a faixa de várias execuções, nunca um número só.
Como fazer benchmark para que o resultado signifique algo
- Aqueça, depois meça. A primeira execução paga page faults em memória nova (o guia de sistemas operacionais mostra 65 536 deles para 256 MB), caches frios e, em linguagens gerenciadas, a compilação JIT (veja compiladores e runtimes). Execute o trabalho uma ou mais vezes antes de cronometrá-lo e relate separadamente se a partida a frio é o que lhe interessa.
- Repita e olhe a dispersão. Execute cada medição muitas vezes (pelo menos 5 a 30, mais quando a variância é alta), relate a mediana ou um percentil com a faixa e não descarte nada em silêncio. Compare duas variantes com execuções intercaladas (A, B, A, B) para que um período lento da máquina afete as duas.
- Informe o compilador e suas flags.
-O0,-O2,-O3,-march=native, a otimização em tempo de ligação e a versão do compilador mudam os resultados, às vezes removendo a coisa que você queria medir (um laço cujo resultado não é usado, um desvio transformado em um move condicional, um cálculo tirado do laço). Use o resultado (um checksum impresso no final), inspecione o assembly gerado (gcc -S, um disassembler) do laço quente e use barreiras só quando tiver entendido o que elas escondem. Meu teste de desvios força o desvio de propósito com uma instruçãoasmvazia; sem ela o efeito desaparece. - Controle a CPU. O escalonamento de frequência e o turbo boost deixam uma CPU mais rápida quando está fria e ociosa e mais lenta quando está quente ou ocupada, e o clock muda durante a execução. Onde você controla a máquina, defina o governor de desempenho, desative o turbo ou anote isso, e deixe a máquina aquecer. Em uma máquina virtual você não pode (minhas execuções não têm nenhum controle de frequência).
- Isole a medição. Fixe o processo em um núcleo (
taskset), mantenha outro trabalho longe dele (e do seu irmão de hyper-threading), pare os jobs em segundo plano e prefira uma máquina com um vizinho quieto; em hosts de nuvem compartilhados, o uso de cache e memória dos vizinhos faz parte do seu resultado, o que é uma razão da dispersão acima. Desative a randomização do espaço de endereços e fixe o alocador somente quando precisar de layouts exatamente repetíveis. - Controle os dados. Use tamanhos realistas (os efeitos de cache aparecem quando os dados ultrapassam cada nível), inicialize a memória antes de cronometrar (a memória não tocada pode mapear toda para uma única página zero), tenha em mente o alinhamento e a ordem de alocação e anote se as transparent huge pages estão ligadas, já que elas mudam o custo da tradução de endereços.
- Confira a explicação com contadores. Se você afirma "cache misses", meça-os:
perf stat -e cache-misses,branch-misses,instructions,cyclesno Linux mostra se a hipótese se sustenta. Uma diferença de velocidade sem a diferença correspondente no contador pode ter outra causa. - Registre o ambiente (modelo da CPU, memória, kernel, compilador e flags, a data) ao lado dos números, para que alguém possa dizer depois por que eles não se reproduzem, e teste a conclusão na carga de trabalho real e não só em um micro-benchmark: um laço 10 vezes mais rápido isolado só importa se for uma parcela grande do tempo do programa.
7. Regras práticas
- Escolha o algoritmo primeiro pelo Big-O, depois pense no comportamento da memória. Uma abordagem O(n²) em 100 000 elementos não será salva por ser amigável ao cache.
- Prefira dados contíguos para trabalho de muita leitura e varredura: arrays e vetores em vez de estruturas ligadas, colunas em vez de registros ao varrer poucos campos, estruturas planas em vez de árvores cheias de ponteiros nos caminhos quentes. Isto é um padrão para a travessia, não uma lei para toda carga de trabalho; "Quando dados contíguos não são a resposta", acima, diz quando o custo de mudar os dados, a necessidade de referências estáveis ou o padrão de acesso apontam para outro lugar.
- Percorra a memória em ordem. Faça laços na ordem em que os dados estão armazenados, processe em blocos que caibam no cache e ordene ou agrupe o trabalho para que os acessos fiquem próximos.
- Mantenha os dados quentes pequenos. Tipos menores, uma
structsem campos não usados, um índice deint32ondeint64não é necessário: mais registros por linha de cache e mais deles no cache. - Evite desvios imprevisíveis nos laços mais quentes quando puder, ordenando, particionando ou usando aritmética no lugar de um
if, mas só depois de medir que isso importa. Desvios previsíveis são baratos, não de graça, e uma versão sem desvios nem sempre é mais rápida. - Faça menos trabalho por elemento antes de fazê-lo mais rápido: agrupar em lotes, sair cedo e filtrar antes de calcular eliminam misses por completo.
- Meça. Use um profiler e contadores de hardware (o
perf statmostra cache misses e erros de predição de desvios no Linux), faça benchmark com tamanhos e dados realistas, repita as execuções e cuidado com compiladores que otimizam fora aquilo que você queria medir.
As mesmas ideias um nível acima
A hierarquia continua além da CPU: da RAM ao SSD é outro fator de mil, e do disco à rede outro. É por isso que os mesmos princípios aparecem no projeto de sistemas: os índices de banco de dados são B-trees com nós dimensionados para uma página de disco; as estratégias de cache põem os dados quentes em uma camada mais rápida e menor; o comportamento de swap e de page cache em sistemas operacionais é a mesma história do working set; os índices de busca comprimem as posting lists para ler menos bytes; e a observabilidade diz qual nível está lento em produção.
8. Erros comuns
- Enunciar a complexidade sem dizer o que é n, ou ignorar que a constante pode dominar nos tamanhos que você tem.
- Trocar um array por uma lista ligada "porque a inserção é O(1)".
- Iterar um array 2D na ordem errada, ou um column store linha por linha.
- Otimizar um laço que não está no caminho quente; meça primeiro.
- Fazer benchmark com dados que cabem no cache e depois rodar com dados que não cabem (ou o contrário).
- Acreditar em um micro-benchmark que o compilador pode ter apagado, ou cuja primeira execução incluiu o carregamento dos dados.
- Tratar tabelas hash como sempre O(1) sem custo: cada busca costuma ser pelo menos um cache miss em uma tabela grande.
- Citar um número de benchmark como um fato, sem a máquina, as flags do compilador, o número de execuções e a dispersão.
- Transformar toda coleção em um array plano sem perguntar como ela é modificada: inserções grandes no meio, referências estáveis e escritores concorrentes podem mudar a resposta.
9. Coisas a mencionar em uma entrevista
- Que o Big-O trata de crescimento, não de velocidade, e que a hierarquia de memória acrescenta um fator de 100 entre o L1 e a RAM.
- Linhas de cache e localidade (espacial e temporal), com o exemplo da travessia row-major contra column-major.
- Por que os arrays vencem as listas ligadas na prática, e quando isso muda.
- Array de structs contra struct de arrays, e a ligação com o armazenamento colunar.
- Predição de desvios e o exemplo do array ordenado.
- Que entradas pequenas podem favorecer o algoritmo "pior", e que as bibliotecas reais trocam de estratégia pelo tamanho.
- Que você faria profiling antes de otimizar, e o que olharia (cache misses, erros de predição de desvios).
- Como você faria um benchmark direito: aquecimento, repetições com a mediana e a faixa, comparação intercalada, flags do compilador e assembly conferido, frequência da CPU e isolamento, contadores para confirmar a causa.
- Quando dados contíguos não são a escolha certa (grandes inserções no meio, ponteiros estáveis, chaves ordenadas, escritas concorrentes) e que um desvio corretamente previsto é barato, não de graça.
Resumo rápido
- Um acesso à memória custa de cerca de 2 ns (L1) a cerca de 140 ns (RAM) no teste, um fator de 70; linhas de cache de 64 bytes são o que se move.
- A mesma soma O(n) foi 18 vezes mais lenta em ordem aleatória; uma matriz percorrida primeiro por colunas foi 13 vezes mais lenta; uma lista ligada espalhada foi 38 vezes mais lenta que uma ordenada; um layout de structs custou 6,5 vezes quando só um campo era necessário.
- Desvios previsíveis são baratos, não de graça, e os mal previstos importam: dados ordenados rodaram 5,6 vezes mais rápido para o mesmo trabalho.
- Estes são resultados de uma máquina virtual: cinco execuções repetidas deram razões que variaram de cerca de 5% a 25% da mediana, e outro hardware diferirá mais. Relate medianas e faixas, e meça na sua própria máquina e carga de trabalho.
- Os layouts contíguos vencem em varreduras e buscas, mas não em toda carga de trabalho: inserir no meio de um array de um milhão de elementos custou cerca de 80 µs, contra cerca de 0,1 µs quando você já tem um nó da lista; referências estáveis, chaves ordenadas e escritores concorrentes podem decidir de outra forma.
- Para n pequeno o algoritmo mais simples vence (a varredura linear venceu a busca binária até cerca de 100 elementos); para n grande o melhor Big-O vence por ordens de grandeza.
- Use o Big-O para escolher o algoritmo e a hierarquia de memória para escolher o layout, e meça antes de otimizar.
Apêndice: o código dos experimentos
O programa em C foi compilado com gcc -O2 e executado em um pequeno servidor virtual de dois núcleos; leva cerca de meio minuto e precisa de cerca de 800 MB de memória. As tabelas deste guia vêm de execuções únicas; cinco execuções repetidas (seção 6) variaram de alguns por cento a cerca de 60 por cento da mediana, dependendo da medição, e os resultados diferem muito entre máquinas, então os valores das tabelas acima estão arredondados e as razões são a lição. O programa não fixa o processo em um núcleo, não controla a frequência da CPU nem relata a sua própria variância, então esses controles são exatamente o que você deve acrescentar ao executá-lo de novo. Dois detalhes importam para um teste justo: os arrays são escritos antes de serem lidos (a memória que só foi alocada pode mapear toda para uma única página zero compartilhada, o que torna todo acesso rápido) e o teste de desvios usa uma instrução asm vazia para impedir o compilador de substituir o desvio por código sem desvios. O script em Python mede o interpretador, onde os efeitos de cache ficam em grande parte escondidos pela própria sobrecarga do interpretador.
Níveis de cache, ordem de acesso, layout e desvios (C)
// gcc -O2 -o mem mem.c
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec * 1e-9; }
static uint64_t rng = 88172645463325252ULL;
static uint64_t xr(void) { rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; return rng; }
// 1. pointer chasing through a random cycle: every load depends on the previous one
static double chase(size_t bytes) {
size_t n = bytes / sizeof(size_t);
size_t *next = malloc(n * sizeof(size_t)), *perm = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) perm[i] = i;
for (size_t i = n - 1; i > 0; i--) { size_t j = xr() % (i + 1); size_t t = perm[i]; perm[i] = perm[j]; perm[j] = t; }
for (size_t i = 0; i < n; i++) next[perm[i]] = perm[(i + 1) % n]; // one cycle through all slots
size_t steps = 20000000, p = 0; double t0 = now();
for (size_t i = 0; i < steps; i++) p = next[p];
double dt = now() - t0; volatile size_t sink = p; (void)sink; free(next); free(perm);
return dt / steps * 1e9;
}
// 2. summing 64M ints: in order, or in a random order
static void seq_vs_random(void) {
size_t n = 64u << 20; int *a = malloc(n * sizeof(int)); size_t *idx = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) { a[i] = (int)i; idx[i] = i; }
for (size_t i = n - 1; i > 0; i--) { size_t j = xr() % (i + 1); size_t t = idx[i]; idx[i] = idx[j]; idx[j] = t; }
long s = 0; double t0 = now(); for (size_t i = 0; i < n; i++) s += a[i]; double t1 = now();
for (size_t i = 0; i < n; i++) s += a[idx[i]]; double t2 = now();
printf("sum of %zu ints (%zu MB): in order %.0f ms (%.2f ns each), random order %.0f ms (%.2f ns each), ratio %.1fx [%ld]\n",
n, n * 4 >> 20, (t1 - t0) * 1e3, (t1 - t0) / n * 1e9, (t2 - t1) * 1e3, (t2 - t1) / n * 1e9, (t2 - t1) / (t1 - t0), s % 7);
free(a); free(idx);
}
// 3. stride: touch every k-th int of a 256 MB array, the same number of touches each time
static void stride(void) {
size_t n = 64u << 20; int *a = malloc(n * sizeof(int)); for (size_t i = 0; i < n; i++) a[i] = (int)i; long s = 0; // written first: untouched calloc pages would all share one zero page
printf("stride (ints) : ");
for (size_t k = 1; k <= 256; k *= 2) {
size_t touches = 8u << 20; double t0 = now(); size_t i = 0;
for (size_t r = 0; r < touches; r++) { s += a[i]; i += k; if (i >= n) i -= n; }
printf("%zu:%.2fns ", k, (now() - t0) / touches * 1e9);
}
printf("[%ld]\n", s); free(a);
}
// 4. matrix: row by row against column by column
static void matrix(void) {
size_t N = 4096; int *m = malloc(N * N * sizeof(int)); for (size_t i = 0; i < N * N; i++) m[i] = 1; long s = 0;
double t0 = now(); for (size_t r = 0; r < N; r++) for (size_t c = 0; c < N; c++) s += m[r * N + c];
double t1 = now(); for (size_t c = 0; c < N; c++) for (size_t r = 0; r < N; r++) s += m[r * N + c];
double t2 = now();
printf("%zux%zu ints: row by row %.0f ms, column by column %.0f ms, ratio %.1fx [%ld]\n", N, N, (t1 - t0) * 1e3, (t2 - t1) * 1e3, (t2 - t1) / (t1 - t0), s % 7); free(m);
}
// 5. array of structs against struct of arrays, when only one field is needed
typedef struct { int id; int x; double pad[6]; } Rec; // 64 bytes per record
static void aos_soa(void) {
size_t n = 8u << 20; Rec *r = malloc(n * sizeof(Rec)); int *xs = malloc(n * sizeof(int));
for (size_t i = 0; i < n; i++) { r[i].id = (int)i; r[i].x = 1; xs[i] = 1; }
long s = 0; double t0 = now(); for (size_t i = 0; i < n; i++) s += r[i].x; double t1 = now();
for (size_t i = 0; i < n; i++) s += xs[i]; double t2 = now();
printf("sum one field of %zu records: array of 64-byte structs %.1f ms, separate int array %.1f ms, ratio %.1fx [%ld]\n", n, (t1 - t0) * 1e3, (t2 - t1) * 1e3, (t1 - t0) / (t2 - t1), s % 7);
}
// 6. a linked list laid out in memory order against the same list shuffled in memory
typedef struct Node { struct Node *next; long v; } Node;
static void lists(void) {
size_t n = 4u << 20; Node *pool = malloc(n * sizeof(Node)); size_t *ord = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) ord[i] = i;
for (int shuffled = 0; shuffled < 2; shuffled++) {
if (shuffled) for (size_t i = n - 1; i > 0; i--) { size_t j = xr() % (i + 1); size_t t = ord[i]; ord[i] = ord[j]; ord[j] = t; }
for (size_t i = 0; i < n; i++) { pool[ord[i]].v = 1; pool[ord[i]].next = i + 1 < n ? &pool[ord[i + 1]] : NULL; }
long s = 0; double t0 = now(); for (int rep = 0; rep < 5; rep++) for (Node *p = &pool[ord[0]]; p; p = p->next) s += p->v;
double dt = now() - t0; printf("traverse a list of %zu nodes (%zu MB) x5: nodes %s in memory %.0f ms (%.2f ns per node) [%ld]\n", n, n * sizeof(Node) >> 20, shuffled ? "scattered" : "in order", dt * 1e3, dt / (5.0 * n) * 1e9, s % 7);
}
}
// 7. branch prediction: count values >= 128 in unsorted and in sorted data
static int cmp(const void *a, const void *b) { return *(const unsigned char *)a - *(const unsigned char *)b; }
static void branches(void) {
size_t n = 32u << 20; unsigned char *d = malloc(n); for (size_t i = 0; i < n; i++) d[i] = xr() & 255; long c = 0;
double t0 = now(); for (int r = 0; r < 4; r++) for (size_t i = 0; i < n; i++) { if (d[i] >= 128) { c += d[i]; asm volatile("" ::: "memory"); } }
double t1 = now(); qsort(d, n, 1, cmp); double t2 = now();
for (int r = 0; r < 4; r++) for (size_t i = 0; i < n; i++) { if (d[i] >= 128) { c += d[i]; asm volatile("" ::: "memory"); } }
double t3 = now(); printf("conditional sum over %zu random bytes x4: unsorted %.0f ms, sorted %.0f ms, ratio %.1fx [%ld]\n", n, (t1 - t0) * 1e3, (t3 - t2) * 1e3, (t1 - t0) / (t3 - t2), c % 7);
}
// 8. linear scan against binary search in a sorted array, by size
static int lin(const int *a, int n, int x) { int i = 0; while (i < n && a[i] < x) i++; return i; }
static int bin(const int *a, int n, int x) { int lo = 0, hi = n; while (lo < hi) { int m = (lo + hi) / 2; if (a[m] < x) lo = m + 1; else hi = m; } return lo; }
static void search(void) {
printf("search in sorted ints, ns per lookup (linear / binary): ");
for (int n = 4; n <= 1 << 20; n *= 4) {
int *a = malloc(n * sizeof(int)); for (int i = 0; i < n; i++) a[i] = 2 * i;
int q = 200000; int *k = malloc(q * sizeof(int)); for (int i = 0; i < q; i++) k[i] = (int)(xr() % (2 * n));
long s = 0; double t0 = now(); for (int i = 0; i < q; i++) s += lin(a, n, k[i]); double t1 = now();
for (int i = 0; i < q; i++) s += bin(a, n, k[i]); double t2 = now();
printf("n=%d: %.0f/%.0f ", n, (t1 - t0) / q * 1e9, (t2 - t1) / q * 1e9); if (s == 42) putchar(' '); free(a); free(k);
if (n >= 1 << 14) { }
}
printf("\n");
}
int main(void) {
printf("pointer chasing, ns per dependent load:\n");
size_t sizes[] = {16u<<10, 32u<<10, 64u<<10, 256u<<10, 1u<<20, 2u<<20, 4u<<20, 16u<<20, 64u<<20, 256u<<20};
for (int i = 0; i < 10; i++) printf(" %6zu KB: %6.2f ns\n", sizes[i] >> 10, chase(sizes[i]));
seq_vs_random(); stride(); matrix(); aos_soa(); lists(); branches(); search();
return 0;
}
Big-O contra fatores constantes em Python
import timeit, random, bisect
# 1. membership: list (O(n)) against set (O(1) average), by size; the key is found at the end of the list
print("x in list / x in set, ns per lookup (key at the end of the list):")
for n in (2, 4, 8, 16, 64, 1000, 100000):
data = list(range(n)); s = set(data); k = n - 1
tl = min(timeit.repeat(lambda: k in data, number=20000, repeat=5)) / 20000 * 1e9
ts = min(timeit.repeat(lambda: k in s, number=20000, repeat=5)) / 20000 * 1e9
print(f" n={n:>6}: list {tl:>9.0f} set {ts:>5.0f}")
# 2. the cost of building the set: when a lookup structure pays off
n = 1000; data = list(range(n))
build = min(timeit.repeat(lambda: set(data), number=2000, repeat=5)) / 2000 * 1e6
scan = min(timeit.repeat(lambda: (n - 1) in data, number=2000, repeat=5)) / 2000 * 1e6
print(f"building a set of {n} items takes {build:.1f} us; one worst-case scan of the list takes {scan:.1f} us, so the set wins after about {build/scan:.0f} lookups")
# 3. the same sum over a list of Python ints and over a list of floats from an array: the constant factors of the language
import array, sys
n = 10_000_000; lst = list(range(n)); arr = array.array("q", range(n))
t1 = min(timeit.repeat(lambda: sum(lst), number=1, repeat=3)); t2 = min(timeit.repeat(lambda: sum(arr), number=1, repeat=3))
print(f"sum of {n} ints: list {t1*1e3:.0f} ms ({sys.getsizeof(lst)//1_000_000} MB of pointers plus {sys.getsizeof(5)} bytes per int object), array('q') {t2*1e3:.0f} ms ({sys.getsizeof(arr)//1_000_000} MB)")
Inserindo no meio: um array contra uma lista (C)
// mutation.c: inserting in the middle: a contiguous array (memmove) against a linked list, as the collection grows.
// gcc -O2 -o mutation mutation.c
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec * 1e-9; }
static uint64_t rng = 88172645463325252ULL;
static uint64_t xr(void) { rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; return rng; }
typedef struct Node { int v; struct Node *next; } Node;
int main(void) {
printf("%10s %28s %34s %30s\n", "n", "array: insert at random pos", "list: find pos by walking + insert", "list: insert at a known node");
for (size_t n = 1000; n <= 4000000; n *= 4) {
int *a = malloc((n + 1000) * sizeof(int)); for (size_t i = 0; i < n; i++) a[i] = (int)i;
int reps = n < 100000 ? 2000 : 200; size_t len = n;
double t0 = now();
for (int r = 0; r < reps; r++) { size_t p = xr() % len; memmove(a + p + 1, a + p, (len - p) * sizeof(int)); a[p] = -1; len++; if (len >= n + 1000) len = n; }
double ta = (now() - t0) / reps;
// a list whose nodes are scattered in memory (as after many allocations and frees)
Node **nodes = malloc(n * sizeof(Node *)); for (size_t i = 0; i < n; i++) nodes[i] = malloc(sizeof(Node));
for (size_t i = n - 1; i > 0; i--) { size_t j = xr() % (i + 1); Node *t = nodes[i]; nodes[i] = nodes[j]; nodes[j] = t; }
for (size_t i = 0; i < n; i++) { nodes[i]->v = (int)i; nodes[i]->next = i + 1 < n ? nodes[i + 1] : NULL; }
int lreps = n < 100000 ? 500 : 20;
t0 = now();
for (int r = 0; r < lreps; r++) { size_t p = xr() % n; Node *x = nodes[0]; for (size_t k = 0; k < p; k++) x = x->next; Node *nn = malloc(sizeof(Node)); nn->v = -1; nn->next = x->next; x->next = nn; }
double tl = (now() - t0) / lreps;
t0 = now(); int kreps = 100000;
for (int r = 0; r < kreps; r++) { Node *x = nodes[xr() % n]; Node *nn = malloc(sizeof(Node)); nn->v = -1; nn->next = x->next; x->next = nn; }
double tk = (now() - t0) / kreps;
printf("%10zu %25.0f ns %31.0f ns %27.0f ns\n", n, ta * 1e9, tl * 1e9, tk * 1e9);
free(a);
}
return 0;
}
Compile com gcc -O2 -o mutation mutation.c. Os tempos são por inserção, em média sobre 20 a 100 000 inserções dependendo do tamanho, de duas execuções na mesma máquina virtual; variam alguns por cento.
Fontes
- Ulrich Drepper, What Every Programmer Should Know About Memory (2007), ainda a melhor explicação longa de caches, TLBs e prefetching.
- Randal Bryant e David O'Hallaron, Computer Systems: A Programmer's Perspective, capítulo 6 sobre a hierarquia de memória e a localidade.
- John Hennessy e David Patterson, Computer Architecture: A Quantitative Approach, os capítulos sobre projeto da hierarquia de memória.
- A lista "latency numbers every programmer should know" de Jeff Dean, amplamente copiada, e a versão interativa ao longo dos anos de Colin Scott, para ordens de grandeza; os valores reais dependem do hardware.
- A pergunta do Stack Overflow Why is processing a sorted array faster than processing an unsorted array? para o experimento de predição de desvios.
- A documentação do
perfdo Linux para medir cache misses e erros de predição de desvios.
Pratique este tema: CS Fundamentals