Écart O(1) vs O(log n) : Cache dans les Structures de Données

## Pourquoi les algorithmes O(1) perdent face à O(log n) : Cache et performances réelles

Durant le développement d'un bootloader pour un SoC RISC-V, nous avons rencontré un problème : la recherche de configurations de périphériques dans une table de 500 éléments prenait trop de temps. Une table de hachage avec une complexité amortie O(1) entraînait des temps de démarrage supérieurs à 100 ms — trois ordres de grandeur pires. Passer à une recherche binaire sur un tableau trié en O(log n) a accéléré les choses de 40 %.

Le profilage avec perf a révélé la différence de comportement du cache :

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

# Recherche binaire
$ perf stat -e cache-references,cache-misses ./bootloader_binsearch
    423,156 cache-references
     89,234 cache-misses (21.1% miss rate)

Les misses de cache dans la table de hachage atteignaient 71,5 %, chacune coûtant ~100 cycles. La recherche binaire a réduit les misses à 21,1 % grâce à une meilleure localité d'accès.

Tableau vs Liste chaînée : Une expérience

La somme de 100 000 entiers a révélé un écart énorme malgré les deux en O(n) :

Tableau : 70 147 ns (17 557 410 cycles)
Liste chaînée : 179 169 ns (44 740 656 cycles)
Le tableau est 2,55 fois plus rapide

Le code du tableau utilise un accès séquentiel :

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

Liste chaînée :

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

Le tableau l'emporte grâce à la localité spatiale : une ligne de cache (64 bytes) charge 16 éléments d'un coup. La liste chaînée provoque ~70 % de misses à cause des pointeurs dispersés.

Hiérarchie mémoire et latences

Les systèmes réels ont une hiérarchie à plusieurs niveaux :

| Niveau | Taille | Latence | Relatif aux registres |

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

| Registres | ~256 B | 1 cycle | 1× |

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

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

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

| DRAM | GB | 100-200 cycles | 100× |

Un seul miss DRAM équivaut à 100 opérations ALU. Dans RISC-V embarqué :

• L1 : 16-32 KB (contre 64 KB sur les ordinateurs de bureau)
• Pas de L3
• DRAM à 100 MHz

Un jeu de données >16 KB signifie des misses constants.

Lignes de cache et localité

Les CPU chargent des lignes de 64 bytes. L'accès séquentiel excelle :

• Tableau : 94 % de hits
• Accès aléatoire : misses fréquents
• Nœud de liste (16 B) : 75 % de la ligne gaspillée

Le préchargement matériel aide les motifs séquentiels mais échoue sur les pointeurs.

Enseignements principaux

• Le cache domine : les misses coûtent 100 fois plus que les ops ALU
• La localité règne : O(n) avec bon cache > O(log n) avec mauvais cache
• L'embarqué est plus dur : de petits caches exigent de rentrer en L1
• Toujours profiler : perf révèle les vrais goulots d'étranglement
• Les algorithmes évoluent : les manuels vieillissent sur silicium

— Editorial Team