Pourquoi la localité du cache est-elle importante pour les performances des matrices ?

Question

Dans la suite de l'article blog il y a une déclaration sur l'avantage des tableaux par rapport aux listes chaînées :

Les baies ont une meilleure localisation du cache, ce qui peut faire une grande différence en termes de performances.

Qu'est-ce que cela signifie ? Je ne comprends pas comment la localité du cache peut apporter un énorme avantage en termes de performances.

Answer 1

Voir ma réponse sur la localité spatiale et temporelle .

En particulier, les tableaux sont des blocs de mémoire contigus, de sorte que de grandes parties d'entre eux seront chargées dans le cache lors du premier accès. Il est donc relativement rapide d'accéder aux futurs éléments du tableau. En revanche, les listes chaînées ne se trouvent pas nécessairement dans des blocs de mémoire contigus et peuvent entraîner un plus grand nombre d'erreurs de cache, ce qui augmente le temps nécessaire pour y accéder.

Considérons les configurations de mémoire suivantes pour un tableau data et liste chaînée l_data de grandes structures

Address      Contents       | Address      Contents
ffff 0000    data[0]        | ffff 1000    l_data
ffff 0040    data[1]        |   ....
ffff 0080    data[2]        | ffff 3460    l_data->next
ffff 00c0    data[3]        |   ....
ffff 0100    data[4]        | ffff 8dc0    l_data->next->next
                            | ffff 8e00    l_data->next->next->next
                            |   ....
                            | ffff 8f00    l_data->next->next->next->next

Si nous voulions parcourir ce tableau en boucle, le premier accès à ffff 0000 nous obligerait à aller dans la mémoire pour la récupérer (une opération très lente en termes de cycles de CPU). Cependant, après le premier accès, le reste du tableau se trouverait dans la mémoire cache et les accès suivants seraient beaucoup plus rapides. Avec la liste chaînée, le premier accès à ffff 1000 nous obligerait également à nous rendre à la mémoire. Malheureusement, le processeur mettra en cache la mémoire qui entoure directement cet emplacement, c'est-à-dire jusqu'à ffff 2000 . Comme vous pouvez le voir, cela ne capture aucun des autres éléments de la liste, ce qui signifie que lorsque nous accédons à l_data->next Nous devrons à nouveau faire appel à la mémoire.

Answer 2

En général, lorsqu'on utilise un tableau, on accède à des éléments qui sont proches les uns des autres. C'est particulièrement vrai lorsqu'on accède à un tableau de manière séquentielle.

Lorsque vous accédez à la mémoire, une partie de celle-ci est mise en cache à différents niveaux. Localité du cache fait référence à la probabilité que des opérations successives se trouvent dans la mémoire cache et soient donc plus rapides. Dans un tableau, vous maximisez les chances que les accès séquentiels aux éléments soient dans la mémoire cache.

Dans le cas des listes, par exemple, rien ne garantit que les éléments qui apparaissent de manière séquentielle dans la liste sont effectivement disposés les uns à côté des autres dans la mémoire. Cela signifie moins d'accès au cache et une dégradation des performances.