Listy powiązane: chybienia cache i benchmarki

# Listy powiązane i chybienia pamięci podręcznej: dlaczego ustępują tablicom w rzeczywistych zadaniach

Listy powiązane wydają się idealne do dynamicznych operacji: wstawianie i usuwanie w O(1), brak przealokacji. Ale w praktyce często przegrywają z tablicami z powodu chybienia pamięci podręcznej. Każdy skok po wskaźniku next obciąża podsystem pamięci, zamieniając teoretyczne zalety w poważne spowolnienia.

Testy na 100 000 elementach pokazują różnicę:

| Operacja | Tablica | Lista powiązana | Opóźnienie |

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

| Sekwencyjne iterowanie | 70 µs | 179 µs | ×2,5 |

| Dostęp losowy | 95 µs | 2847 µs | ×30 |

| Wstawki na koniec | 42 µs | 1234 µs | ×29 |

Nawet wstawki, w których listy powinny dominować, wychodzą wolniej z powodu realokacji i chybienia pamięci podręcznej.

Mechanizm chybienia pamięci podręcznej

Linie pamięci podręcznej procesora przechwytywują 64 bajty naraz. W tablicy elementy leżą kolejno — jedno chybienie daje dostęp do 16 int. W liście powiązanej węzły są rozproszone po stercie:

// Typowy węzeł
struct node {
    int value;     // 4 bajty
    node *next;    // 8 bajtów
}; // 16 bajtów z paddingiem

Iterowanie po liście generuje chybienie na każdy węzeł (∼100 taktów opóźnienia). Dla 100 000 węzłów to 10 mln taktów w porównaniu do 625 tys. u tablicy. Tablica zużywa 400 KB, lista — 1,6 MB (4× narzut).

Koszty alokacji pamięci

Tworzenie listy wymaga 100 000 wywołań malloc():

for (int i = 0; i < 100000; i++) {
    node *n = malloc(sizeof(node)); // Przeszukiwanie sterty, metadane, fragmentacja
    n->value = i;
    n->next = head;
    head = n;
}

Tablica — jedno wywołanie. Różnica w benchmarkach: 42 µs wobec 1234 µs.

Rzadkie przypadki uzasadniające listy

Listy powiązane mają sens w wąskich scenariuszach:

• Intruzijne listy w jądrach (Linux list_head): węzły wbudowane w struktury, lepsza lokalność.
• Struktury bez blokad: atomowe CAS na wskaźnikach prostsze niż na tablicach.
• Małe statyczne zbiory danych z rzadkimi wstawkami.

Przykład stosu bez blokad Treiber'a:

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

Optymalizacje przy wymuszonym użyciu

Baseny obiektów

Wstępnie zaalokuj tablicę węzłów:

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

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

Szybkość: 287 µs (×4,3 do malloc, ale ×6,8 do tablicy).

Rozwinięte listy

Przechowuj kilka elementów na węzeł:

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

Iterowanie: 45 µs (lepiej niż standardowa lista, porównywalnie z tablicą dla dostępu sekwencyjnego).

Listy XOR

Oszczędność pamięci dzięki XOR prev^next:

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

// Iterowanie wymaga prowadzenia prev
node *next = (uintptr_t)prev ^ (uintptr_t)curr->xor_ptr;

Wady: złożoność debugowania, brak dwukierunkowego iterowania. Niezalecane.

Przypadek RTOS: dlaczego listy działają

W FreeRTOS planista używa tablicy list według priorytetów (32 poziomy):

list_head ready_tasks[MAX_PRIORITIES];

Sukces dzięki:

• Małym listom (1–5 zadań).
• Wbudowanym węzłom w task_struct.
• Operacjom O(1) według priorytetu.

Benchmark na Cortex-M4: wstawka 0,8 µs, usuwanie 0,6 µs.

Co jest ważne

• Pamięć podręczna dominuje: chybienia na wskaźnikach niszczą wydajność nawet w operacjach O(1).
• Narzut pamięci: 4× wzrost przez wskaźniki + fragmentacja.
• Dynamyczne tablice preferowane: amortyzowane wstawki O(1) bez kar pamięci podręcznej.
• Optymalizacje częściowo ratują: baseny i rozwinięte listy zbliżają, ale nie przeganiają.
• Wyjątek RTOS: wbudowane węzły + mały rozmiar uzasadniają wybór.

— Editorial Team