À complexité égale, la mémoire décide

On somme les éléments d'un tableau de $n$ entiers, puis ceux d'une chaîne de $n$ maillons — même complexité $\Theta (n)$, cinq parcours à chaque fois. La chaîne est construite de deux manières : maillons alloués dans l'ordre du chaînage, puis maillons alloués dans un ordre permuté. Mesuré sans optimisation :

n = 1 000 000   tableau 0,004 s   chaine ordonnee 0,006 s   chaine dispersee 0,091 s
n = 8 000 000   tableau 0,034 s   chaine ordonnee 0,050 s   chaine dispersee 3,882 s
                                            x 1,5                     x 115

Le résultat est plus intéressant que « le tableau gagne ». Une chaîne dont les maillons se suivent en mémoire n'est que $1,5$ fois plus lente que le tableau — ce facteur-là est le prix du pointeur à suivre et de la mémoire doublée. Une chaîne dont les maillons sont dispersés est $115$ fois plus lente. Ce n'est donc pas le chaînage qui coûte, c'est la dispersion.

L'explication. Le processeur ne lit pas la mémoire octet par octet : il en charge des lignes de $64$ octets dans un cache, et il devine à l'avance quelles lignes seront demandées quand les accès sont réguliers. Un parcours de tableau lui donne raison à chaque fois : une seule lecture de mémoire principale sert seize entiers. Un parcours de chaîne dispersée le prend systématiquement à contre-pied : chaque maillon est une ligne nouvelle, et l'adresse du suivant n'est connue qu'après avoir lu le maillon courant — impossible d'anticiper.

Ce qu'il faut en retenir, et ce qu'il ne faut surtout pas en conclure.

• Le facteur $115$ est une constante. Il ne change aucun ordre de grandeur, et il ne rachètera jamais un $\Theta (n^2)$ mis à la place d'un $\Theta (n\log n)$. La complexité se raisonne d'abord.
• Mais une constante de $115$ mérite qu'on la connaisse. Elle explique pourquoi les bibliothèques réelles préfèrent les tableaux dynamiques aux listes chaînées chaque fois que le profil d'opérations le permet, et pourquoi les structures « par blocs » — un tableau de petits tableaux — existent.
• Elle explique aussi que la mesure du cours est honnête mais incomplète : le tableau ne gagne pas parce qu'il est un tableau, il gagne parce qu'il est contigu. Une chaîne dont on alloue les maillons d'un seul bloc, dans l'ordre, récupère presque tout.

Avec optimisation (-O2), l'écart s'accroît encore — le compilateur vectorise le parcours de tableau et ne peut rien faire de la chaîne — mais la mesure ci-dessus, faite à -O0, est la plus honnête : elle compare deux boucles qui font toutes deux exactement $n$ additions.