Rozdíl O(1) vs O(log n): cache v datových strukturách

Proč algoritmy O(1) prohrávají O(log n): cache a reálný výkon

Při vývoji zavaděče pro SoC RISC-V vznikl problém: hledání konfigurací zařízení v tabulce se 500 prvky zabíralo příliš mnoho času. Hash tabulka s amortizovanou složitostí O(1) dávala čas načítání o tři řády vyšší než 100 ms. Nahrazení binárním hledáním v seřazeném poli s O(log n) zrychlilo proces o 40 %.

Profilování s perf ukázalo rozdíl v chování cache:

# Hash tabulka
$ perf stat -e cache-references,cache-misses ./bootloader_hash
  1,247,832 cache-references
    892,441 cache-misses (71.5% miss rate)

# Binární hledání
$ perf stat -e cache-references,cache-misses ./bootloader_binsearch
    423,156 cache-references
     89,234 cache-misses (21.1% miss rate)

Chyby cache v hash tabulce dosahovaly 71,5 %, každá stála ~100 cyklů. Binární hledání snížilo chyby na 21,1 % díky lokalitě přístupu.

Pole proti spojenému seznamu: experiment

Srovnání sečtení 100 000 celých čísel ukázalo rozdíl navzdory stejné O(n):

Pole: 70 147 ns (17 557 410 cyklů)
Spojený seznam: 179 169 ns (44 740 656 cyklů)
Pole je 2,55× rychlejší

Kód pole využívá sekvenční přístup:

int array[100000];
for (int i = 0; i < 100000; i++) {
    array[i] = i;
}
long long sum = 0;
for (int i = 0; i < 100000; i++) {
    sum += array[i];
}

Spojený seznam:

typedef struct node {
    int value;
    struct node *next;
} node_t;

node_t *head = NULL;
for (int i = 0; i < 100000; i++) {
    node_t *node = malloc(sizeof(node_t));
    node->value = i;
    node->next = head;
    head = node;
}

long long sum = 0;
node_t *curr = head;
while (curr) {
    sum += curr->value;
    curr = curr->next;
}

Pole vítězí díky prostorové lokalitě: linka cache (64 bajtů) zachytí 16 prvků najednou. Spojený seznam způsobuje ~70% chyb kvůli rozptýleným ukazatelům.

Hierarchie paměti a zpoždění

Reálné systémy mají víceúrovňovou hierarchii:

| Úroveň | Velikost | Zpoždění | Relativně k registru |

|------------|------------|------------|----------------------|

| Registry | ~256 B | 1 cyklus | 1× |

| L1 | 32-64 KB | 3-4 cykly | 3× |

| L2 | 256 KB-1 MB| 12-15 cyklů| 12× |

| L3 | 4-32 MB | 40-50 cyklů| 40× |

| DRAM | GB | 100-200 cyklů | 100× |

Jeden cache miss DRAM je ekvivalentní 100 ALU operacím. V vestavěných RISC-V:

• L1: 16-32 KB (vs 64 KB na desktopu)
• Žádná L3
• DRAM na 100 MHz

Pracovní množina >16 KB vede k neustálým chybám.

Linky cache a lokalita

CPU načítá 64bajtové linky. Sekvenční přístup je efektivní:

• Pole: 94% zásahů
• Náhodný přístup: časté chyby
• Uzol seznamu (16 B): 75% linky nevyužito

Předvídavé načítání (prefetcher) pomáhá se sekvenčními vzory, ale selhává u ukazatelů.

Co je důležité

• Cache dominuje: chyby stojí 100× více než ALU operace
• Lokalita rozhoduje: O(n) s dobrým cachem > O(log n) se špatným
• Vestavěné jsou přísnější: malé cache vyžadují ve fit do L1
• Vždy profilujte: perf odhalí skutečné úzká místa
• Algoritmy se vyvíjejí: učebnice stárnou na křemíku

— Editorial Team