Vazební seznamy: chyby cache a benchmarks

# Spojové seznamy a chyby cache: proč zaostávají za poli v reálných úkolech

Spojové seznamy se zdají být ideální pro dynamické operace: vložení a odstranění za O(1), žádné přerozdělování. Ale v praxi často prohrávají s poli kvůli chybám cache. Každý přechod přes ukazatel next zatěžuje podsystém paměti a mění teoretické výhody v zpomalení.

Testování na 100 000 prvcích ukazuje rozdíl:

| Operace | Pole | Spojový seznam | Zpoždění |

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

| Sekvenční procházení | 70 μs | 179 μs | ×2,5 |

| Náhodný přístup | 95 μs | 2847 μs | ×30 |

| Vložení na konec | 42 μs | 1234 μs | ×29 |

Dokonce i vložení, kde seznamy měly dominovat, jsou pomalejší kvůli realokacím a chybám cache.

Mechanismus chyb cache

Cache linky procesoru zachytávají 64 bajtů najednou. V poli leží prvky připojeně – jedna chyba umožňuje přístup k 16 int. V spojovém seznamu jsou uzly rozházené po hromádce:

// Typický uzel
struct node {
    int value;     // 4 bajty
    node *next;    // 8 bajtů
}; // 16 bajtů s paddingem

Procházení seznamu generuje chybu na každý uzel (∼100 taktů zpoždění). Pro 100 000 uzlů to znamená 10 milionů taktů oproti 625 tisícům u pole. Pole zabírá 400 KB, seznam 1,6 MB (4× overhead).

Náklady na alokaci paměti

Vytvoření seznamu vyžaduje 100 000 volání malloc():

for (int i = 0; i < 100000; i++) {
    node *n = malloc(sizeof(node)); // Hledání v hromádce, metadata, fragmentace
    n->value = i;
    n->next = head;
    head = n;
}

Pole stačí jedno volání. Rozdíl v benchmarku: 42 μs proti 1234 μs.

Vzácné scénáře, kde se spojové seznamy ospravedlňují

Spojové seznamy mají místo v úzkých případech:

• Intruzivní seznamy v jádrech (Linux list_head): uzly jsou vestavěné do struktur, lokalita je vyšší.
• Lock-free struktury: atomární CAS na ukazatele je jednodušší než na pole.
• Malé statické datasety s vzácnými vloženími.

Příklad lock-free zásobníku Treiberova:

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

Optimalizace pro nucené použití

Používání púl objektů

Předem alokujte pole uzlů:

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

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

Rychlost: 287 μs (×4,3 rychlejší než malloc, ale ×6,8 pomalejší než pole).

Rozvinuté seznamy

Ukládejte několik prvků na uzel:

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

Procházení: 45 μs (lepší než standardní seznam, srovnatelné s polem pro sekvenční přístup).

XOR-seznamy

Úspora paměti díky XOR prev^next:

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

// Procházení vyžaduje vedení prev
node *next = (uintptr_t)prev ^ (uintptr_t)curr->xor_ptr;

Nevýhody: složitost ladění, žádný obousměrný průchod. Nedoporučuje se.

Případ RTOS: proč seznamy fungují

V FreeRTOS plánovač používá pole seznamů podle priorit (32 úrovní):

list_head ready_tasks[MAX_PRIORITIES];

Úspěch díky:

• Malým seznamům (1–5 úkolů).
• Vestavěným uzlům v task_struct.
• O(1) operacím podle priority.

Benchmark na Cortex-M4: vložení 0,8 μs, odstranění 0,6 μs.

Co je důležité

• Cache dominuje: chyby na ukazatele ničí výkon i v O(1) operacích.
• Overhead paměti: 4× růst kvůli ukazatelům + fragmentace.
• Dynamická pole jsou preferovaná: amortizované O(1) vložení bez cache penalizace.
• Optimalizace pomáhají částečně: púly a rozvinuté seznamy se přibližují, ale nepřekonávají.
• RTOS-výjimka: vestavěné uzly + malá velikost ospravedlňují volbu.

— Editorial Team