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 arrayTempo por leitura dependenteCabe em
16 KB1,9 nsL1
64 KB3,1 nsentre L1 e L2
256 KB5,5 nsL2
1 MB8 nsL2
4 MB24 nsL3
16 MB48 nsL3
64 MB135 nsem grande parte memória principal
256 MB140 nsmemó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 acessoTempoPor elemento
em ordem43 ms0,64 ns
em ordem aleatória (por um array de índices)762 ms11,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)1248163264
Tempo por acesso1,6 ns1,8 ns2,6 ns4,2 ns6,4 ns9,2 ns11,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:

LayoutTempo
array de structs de 64 bytes32,5 ms
um array separado contendo só esse campo5,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óriaPor nó
nós alocados em ordem3,4 ns
nós espalhados130 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:

ElementosArray: inserir em uma posição aleatóriaLista: andar até a posição, depois inserirLista: inserir depois de um nó que você já tem
1 00037 ns0,9 µs24 ns
16 0000,5 µs48 µs30 a 40 ns
256 00012 µs4,2 ms75 a 100 ns
1 024 00074 a 87 µs61 a 69 ms100 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.

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:

DadosTempo
ordem aleatória693 ms
ordenados124 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:

nVarredura linearBusca binária
49 ns14 ns
1615 ns27 ns
6430 ns41 ns
25677 ns57 ns
1 024206 ns77 ns
16 3843 043 ns102 ns
262 14452 484 ns157 ns
1 048 576215 391 ns245 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:

GrandezaMenorMedianaMaior
Soma sequencial contra aleatória, razão15,619,020,6
Linhas primeiro contra colunas primeiro, razão10,512,312,6
Array de structs contra array de um campo, razão6,36,57,4
Dados de desvio ordenados contra aleatórios, razão5,05,75,8
Lista espalhada contra ordenada, razão39,440,541,8
Leitura de um array do tamanho do L1 (16 KB), ns1,81,82,8
Leitura de um array de 256 MB, ns152154156

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

7. Regras práticas

  1. 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.
  2. 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.
  3. 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.
  4. Mantenha os dados quentes pequenos. Tipos menores, uma struct sem campos não usados, um índice de int32 onde int64 não é necessário: mais registros por linha de cache e mais deles no cache.
  5. 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.
  6. 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.
  7. Meça. Use um profiler e contadores de hardware (o perf stat mostra 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

9. Coisas a mencionar em uma entrevista

Resumo rápido

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

Pratique este tema: CS Fundamentals

Mais guias