Pourquoi une liste chaînée est plus lente qu'un tableau : le rôle du cache du CPU

Cette vidéo explique pourquoi les tableaux sont plus rapides que les listes chaînées, en raison de la continuité mémoire et de la gestion du cache par le processeur.

Un tableau stocke ses éléments côte à côte dans la mémoire. Le CPU, qui communique avec la mémoire (une opération lente, d'environ 100 cycles), utilise une technique de spéculation : il charge d'avance les données suivantes dans son cache rapide. Ainsi, quand le programme accède au deuxième élément, il est déjà disponible localement.

En revanche, une liste chaînée est constituée de nœuds dispersés à des adresses mémoire arbitraires. Chaque nœud pointe vers le suivant, mais sans garantie de proximité physique. Le CPU ne peut donc pas prédire où se trouve l'élément suivant. À chaque accès, il doit effectuer un aller-retour coûteux vers la mémoire principale, ce qui ralentit considérablement l'exécution.

Exemple : Imaginez un tableau de 8 entiers. Si vous lisez le premier, le CPU charge automatiquement les 7 suivants dans le cache. Lire le deuxième est instantané. Avec une liste chaînée, lire le premier ne charge que ce nœud. Pour lire le deuxième, le CPU doit chercher son adresse en mémoire, payant le coût complet de l'accès.