O(1) vs O(log n) Lücke: Cache in Datenstrukturen

Warum O(1)-Algorithmen gegen O(log n) verlieren: Cache und Leistung in der Praxis

Bei der Entwicklung eines Bootloaders für einen RISC-V SoC stießen wir auf ein Problem: Die Suche nach Gerätekonfigurationen in einer Tabelle mit 500 Elementen dauerte zu lange. Eine Hashtabelle mit amortisierter O(1)-Komplexität führte zu Bootzeiten von über 100 ms – drei Größenordnungen schlechter. Der Wechsel zu binärer Suche in einem sortierten Array mit O(log n) beschleunigte es um 40 %.

Profiling mit perf offenbarte den Unterschied im Cache-Verhalten:

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

# Binäre Suche
$ perf stat -e cache-references,cache-misses ./bootloader_binsearch
    423,156 cache-references
     89,234 cache-misses (21.1% miss rate)

Cache-Misses in der Hashtabelle erreichten 71,5 %, jede kostet ~100 Zyklen. Binäre Suche reduzierte die Misses auf 21,1 % dank besserer Zugriffs-Lokalität.

Array vs. verkettete Liste: Ein Experiment

Summierung von 100.000 Ganzzahlen zeigte einen riesigen Abstand, obwohl beide O(n) sind:

Array: 70.147 ns (17.557.410 Zyklen)
Verkettete Liste: 179.169 ns (44.740.656 Zyklen)
Array ist 2,55× schneller

Der Array-Code nutzt sequentiellen Zugriff:

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

Verkettete Liste:

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

Das Array siegt dank räumlicher Lokalität: Eine Cachezeile (64 Bytes) lädt 16 Elemente auf einmal. Die verkettete Liste löst ~70 % Misses durch verstreute Zeiger aus.

Speicherhierarchie und Latenzen

Reale Systeme haben eine mehrstufige Hierarchie:

| Ebene | Größe | Latenz | Relativ zu Registern |

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

| Register | ~256 B | 1 Zyklus | 1× |

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

| L2 | 256 KB-1 MB| 12-15 Zyklen | 12× |

| L3 | 4-32 MB | 40-50 Zyklen | 40× |

| DRAM | GB | 100-200 Zyklen| 100× |

Ein einzelner DRAM-Miss entspricht 100 ALU-Operationen. In embedded RISC-V:

• L1: 16-32 KB (vs. 64 KB auf Desktops)
• Kein L3
• DRAM bei 100 MHz

Ein Working Set >16 KB bedeutet ständige Misses.

Cachezeilen und Lokalität

CPUs laden 64-Byte-Zeilen. Sequentieller Zugriff glänzt:

• Array: 94 % Treffer
• Zufälliger Zugriff: Häufige Misses
• Listenknoten (16 B): 75 % der Zeile verschwendet

Hardware-Prefetching hilft bei sequentiellen Mustern, scheitert aber an Zeigern.

Wichtige Erkenntnisse

• Cache dominiert: Misses kosten 100× mehr als ALU-Ops
• Lokalität regiert: O(n) mit gutem Cache > O(log n) mit schlechtem Cache
• Embedded ist anspruchsvoller: Winzige Caches verlangen Passgenauigkeit in L1
• Immer profilieren: perf deckt echte Engpässe auf
• Algorithmen entwickeln sich: Lehrbücher altern auf Silizium

— Editorial Team