Hiérarchie mémoire
Pourquoi le parcours de la liste chaînée ci-dessus est-il généralement bien plus lent que la lecture séquentielle d’un tableau comportant le même nombre d’éléments ?
struct node { int val; struct node *next; };
for (p = head; p != NULL; p = p->next)
sum += p->val;- AL’adresse de l’élément suivant n’est connue qu’après lecture de l’élément courant, et les défauts surviennent un par un, en série
- BLes éléments d’une liste chaînée ne peuvent en aucun cas être placés dans le cache
- CDans un traitement à base de pointeurs, la prédiction de branchement du CPU échoue systématiquement
Afficher la réponse et l'explication
Réponse : A. L’adresse de l’élément suivant n’est connue qu’après lecture de l’élément courant, et les défauts surviennent un par un, en série
Dans une liste chaînée, l’adresse de l’élément suivant n’est connue qu’après lecture de p->next. Si les éléments sont dispersés en mémoire, chaque accès provoque un défaut ; comme l’adresse suivante est inconnue, plusieurs défauts ne peuvent pas se recouvrir, et la latence de la mémoire principale s’accumule intégralement à chaque élément. Avec un tableau, l’adresse suivante se calcule, ce qui permet le préchargement et le recouvrement des défauts. Les éléments d’une liste chaînée entrent aussi dans le cache, et le branchement de boucle, facile à prédire, n’échoue pas systématiquement.