Różnica O(1) vs O(log n): cache w strukturach danych

Dlaczego algorytmy O(1) przegrywają O(log n): cache i rzeczywista wydajność

W trakcie development bootloadera dla SoC RISC-V pojawił się problem: wyszukiwanie konfiguracji urządzeń w tabeli z 500 elementów zajmowało zbyt dużo czasu. Tablica hashująca z amortyzowaną złożonością O(1) powodowała czas ładowania o trzy rzędy wielkości wyższy niż 100 ms. Zastąpienie jej wyszukiwaniem binarnym po posortowanej tablicy z O(log n) przyspieszyło proces o 40%.

Profilowanie za pomocą perf pokazało różnicę w zachowaniu cache:

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

# Dvoichnyy poszukiwanie
$ perf stat -e cache-references,cache-misses ./bootloader_binsearch
    423,156 cache-references
     89,234 cache-misses (21.1% miss rate)

Missy cache w tablicy hashującej sięgały 71,5%, każda kosztowała ~100 taktów. Wyszukiwanie binarne zminimalizowało missy do 21,1% dzięki lokalności dostępu.

Tablica kontra lista powiązana: eksperyment

Porównanie sumowania 100 000 liczb całkowitych pokazało przepaść mimo identycznej O(n):

Massiv: 70 147 ns (17 557 410 clock)
Withvyazannyy spisok: 179 169 ns (44 740 656 clock)
Massiv in 2,55 raza bystree

Kod tablicy wykorzystuje sekwencyjny dostęp:

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];
}

Lista powiązana:

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;
}

Tablica wygrywa dzięki lokalności przestrzennej: linia cache (64 bajty) obejmuje 16 elementów naraz. Lista powiązana powoduje ~70% missów z powodu rozproszonych wskaźników.

Hierarchia pamięci i opóźnienia

Rzeczywiste systemy mają wielopoziomową hierarchię:

| Poziom | Rozmiar | Opóźnienie | Względem rejestru |

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

| Rejestry | ~256 B | 1 takt | 1× |

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

| L2 | 256 KB-1 MB| 12-15 taktów | 12× |

| L3 | 4-32 MB | 40-50 taktów | 40× |

| DRAM | GB | 100-200 taktów | 100× |

Jeden miss DRAM równa się 100 operacjom ALU. W osadzonych RISC-V:

• L1: 16-32 KB (w porównaniu do 64 KB na desktopach)
• Brak L3
• DRAM na 100 MHz

Zestaw roboczy >16 KB prowadzi do ciągłych missów.

Linie cache i lokalność

CPU ładuje linie 64-bajtowe. Sekwencyjny dostęp jest efektywny:

• Tablica: 94% trafień
• Losowy dostęp: częste missy
• Węzeł listy (16 B): 75% linii marnowane

Prefetcher pomaga przy sekwencyjnych wzorcach, ale zawodzi na wskaźnikach.

Co jest ważne

• Cache dominuje: missy kosztują 100 razy drożej niż operacje ALU
• Lokalność decyduje: O(n) z dobrym cache > O(log n) z złym
• Osadzone są surowsze: miniaturowe cache wymagają zmieszczenia się w L1
• Zawsze profilujcie: perf ujawnia rzeczywiste wąskie gardła
• Algorytmy ewoluują: podręczniki akademickie starzeją się na krzemie

— Editorial Team