Listes chaînées : échecs de cache et benchmarks

# Listes chaînées et misses de cache : Pourquoi elles font pâle figure face aux tableaux dans les tâches réelles

Les listes chaînées semblent idéales pour les opérations dynamiques : insertions et suppressions en O(1), pas de réallocations. Mais en pratique, elles perdent souvent face aux tableaux à cause des misses de cache. Chaque saut via le pointeur next surcharge le sous-système mémoire, transformant les avantages théoriques en goulots d'étranglement.

Des tests sur 100 000 éléments montrent l'écart :

| Opération | Tableau | Liste chaînée | Retard |

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

| Parcours séquentiel | 70 μs | 179 μs | ×2.5 |

| Accès aléatoire | 95 μs | 2847 μs | ×30 |

| Ajouts | 42 μs | 1234 μs | ×29 |

Même les insertions, où les listes devraient dominer, finissent plus lentes à cause des réallocations et des misses de cache.

Mécanisme des misses de cache

Les lignes de cache du CPU récupèrent 64 octets à la fois. Dans un tableau, les éléments sont disposés de manière séquentielle — un miss donne accès à 16 entiers. Dans une liste chaînée, les nœuds sont dispersés dans le tas :

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

Parcourir la liste génère un miss pour chaque nœud (~100 cycles de délai). Pour 100 000 nœuds — c'est 10 millions de cycles contre 625 000 pour le tableau. Le tableau utilise 400 Ko, la liste — 1,6 Mo (surcharge ×4).

Coûts d'allocation mémoire

Créer la liste nécessite 100 000 appels malloc() :

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

Tableau — un appel. Différence en benchmark : 42 μs vs. 1234 μs.

Scénarios rares où les listes sont justifiées

Les listes chaînées ont du sens dans des cas de niche :

• Listes intrusives dans les noyaux (Linux list_head) : nœuds intégrés dans les structures, meilleure localité.
• Structures sans verrou : CAS atomique sur pointeurs plus simple que sur tableaux.
• Petits ensembles statiques avec insertions rares.

Exemple de pile sans verrou de Treiber :

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

Optimisations quand on doit les utiliser

Pools d'objets

Pré-allouer un tableau de nœuds :

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

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

Vitesse : 287 μs (×4,3 vs. malloc, mais ×6,8 vs. tableau).

Listes déroulées

Stocker plusieurs éléments par nœud :

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

Parcours : 45 μs (mieux que liste standard, comparable au tableau pour l'accès séquentiel).

Listes liées par XOR

Économiser de la mémoire via XOR de 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;

Inconvénients : complexité de débogage, pas de parcours bidirectionnel. Non recommandé.

Cas RTOS : Pourquoi les listes marchent là

Dans FreeRTOS, le planificateur utilise un tableau de listes par priorité (32 niveaux) :

list_head ready_tasks[MAX_PRIORITIES];

Succès dû à :

• Listes petites (1–5 tâches).
• Nœuds intégrés dans task_struct.
• Opérations O(1) par priorité.

Benchmark sur Cortex-M4 : insertion 0,8 μs, suppression 0,6 μs.

Enseignements clés

• Le cache domine : les misses de pointeurs tuent les performances même en opérations O(1).
• Surcharge mémoire : ×4 due aux pointeurs + fragmentation.
• Tableaux dynamiques préférés : insertions amorties O(1) sans pénalités de cache.
• Optimisations aident un peu : pools et listes déroulées réduisent l'écart mais ne surpassent pas.
• Exception RTOS : nœuds intégrés + petite taille justifient le choix.

— Editorial Team