Verknüpfte Listen: Cache-Verfehlungen und Benchmarks

# Verkettete Listen und Cache-Verfehlungen: Warum sie Arrays in realen Anwendungen unterliegen

Verkettete Listen wirken ideal für dynamische Operationen: O(1)-Einfügungen und -Löschungen, keine Neuzuweisungen. In der Praxis verlieren sie jedoch oft gegen Arrays wegen Cache-Verfehlungen. Jeder Sprung über den next-Pointer belastet das Speichersystem und macht theoretische Vorteile zu Engpässen.

Tests mit 100.000 Elementen zeigen die Lücke:

| Vorgang | Array | Verkettete Liste | Rückstand |

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

| Sequentieller Durchlauf | 70 μs | 179 μs | ×2,5 |

| Zufallszugriff | 95 μs | 2847 μs | ×30 |

| Anhängen | 42 μs | 1234 μs | ×29 |

Sogar Einfügungen, bei denen Listen überlegen sein sollten, sind langsamer wegen Neuzuweisungen und Cache-Verfehlungen.

Mechanismus der Cache-Verfehlungen

CPU-Cache-Lines laden jeweils 64 Bytes. In einem Array liegen die Elemente sequentiell – ein Miss gibt Zugriff auf 16 ints. In einer verketteten Liste sind die Knoten über den Heap verteilt:

// Typical node
struct node {
    int value;     // 4 bytes
    node *next;    // 8 bytes
}; // 16 bytes with padding

Das Durchlaufen der Liste erzeugt einen Miss pro Knoten (~100 Takte Verzögerung). Bei 100.000 Knoten sind das 10 Millionen Takte gegenüber 625.000 für das Array. Das Array benötigt 400 KB, die Liste – 1,6 MB (4× Overhead).

Kosten der Speicherverwaltung

Das Erstellen der Liste erfordert 100.000 malloc()-Aufrufe:

for (int i = 0; i < 100000; i++) {
    node *n = malloc(sizeof(node)); // Heap search, metadata, fragmentation
    n->value = i;
    n->next = head;
    head = n;
}

Array – ein Aufruf. Benchmark-Unterschied: 42 μs vs. 1234 μs.

Seltene Szenarien, in denen Listen sinnvoll sind

Verkettete Listen eignen sich für Nischenfälle:

• Intrusive Listen in Kernen (Linux list_head): Knoten eingebettet in Strukturen, bessere Lokalität.
• Lock-free Strukturen: atomare CAS auf Zeigern einfacher als bei Arrays.
• Kleine statische Datensätze mit seltenen Einfügungen.

Beispiel für Treibers lock-free Stack:

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

void push(node_t **head, node_t *node) {
    do {
        node->next = *head;
    } while (!atomic_compare_exchange(head, &node->next, node));
}

Optimierungen, wenn Sie sie unbedingt nutzen müssen

Objektpools

Vorab ein Array von Knoten allokieren:

#define POOL_SIZE 10000
node_t pool[POOL_SIZE];
int idx = 0;

node_t *alloc() {
    return idx < POOL_SIZE ? &pool[idx++] : NULL;
}

Geschwindigkeit: 287 μs (×4,3 vs. malloc, aber ×6,8 vs. Array).

Entrollte Listen

Mehrere Elemente pro Knoten speichern:

#define N 16
typedef struct {
    int values[N];
    int count;
    struct node *next;
} unrolled_t;

Durchlauf: 45 μs (besser als Standardliste, vergleichbar mit Array bei sequentiellen Zugriffen).

XOR-Verkettete Listen

Speicher sparen durch XOR von prev^next:

typedef struct {
    int value;
    node *xor_ptr; // prev ^ next
} xor_node;

// Traversal requires tracking prev
node *next = (uintptr_t)prev ^ (uintptr_t)curr->xor_ptr;

Nachteile: Komplexität beim Debuggen, kein bidirektionaler Durchlauf. Nicht empfohlen.

RTOS-Fall: Warum Listen dort funktionieren

In FreeRTOS verwendet der Scheduler ein Array von Listen nach Priorität (32 Stufen):

list_head ready_tasks[MAX_PRIORITIES];

Erfolg durch:

• Kleine Listen (1–5 Tasks).
• Knoten eingebettet in task_struct.
• O(1)-Operationen nach Priorität.

Benchmark auf Cortex-M4: Einfügung 0,8 μs, Löschung 0,6 μs.

Wichtige Erkenntnisse

• Cache dominiert: Zeiger-Verfehlungen zerstören die Leistung selbst bei O(1)-Operationen.
• Speicher-Overhead: 4× Wachstum durch Zeiger + Fragmentierung.
• Dynamische Arrays bevorzugt: amortisierte O(1)-Einfügungen ohne Cache-Strafen.
• Optimierungen helfen ein wenig: Pools und entrollte Listen verringern die Lücke, überholen aber nicht.
• RTOS-Ausnahme: eingebettete Knoten + kleine Größe rechtfertigen die Wahl.

— Editorial Team