Pourquoi ne cache localité d'importance pour les performances de la baie?

Dans la suite de blog il y a une déclaration au sujet de l'avantage de tableaux sur les listes chaînées:

Tableaux ont une meilleure localité de cache qui peuvent faire une grosse différence dans la performance.

Ça veut dire quoi? Je ne comprends pas comment la localité de cache peut fournir un énorme avantage en termes de performances.

Si vous comprenez comment cache fonctionne, alors vous aurez également à comprendre 1) "Localité de Référence" est une Bonne Chose, et 2) l'accès aux données à partir de baies est généralement plus susceptibles d'avoir une bonne "localité" que l'accès à ces mêmes données à partir d'une liste.
Une chose à noter est que même si c'est vrai, une liste liée individuellement combiné avec une zone contiguë de l'allocation peut être un atout énorme, principalement parce que les éléments de transfert d'un conteneur à un autre implique pointeur de la logique. Si vous regardez à la disposition de la mémoire de ceux, cependant, il est contigu et ressemble à un tableau avec seulement des liens vers le prochain élément dans le tableau, et il est donc encore cache-friendly (au moins jusqu'à ce que la liste est tout rénové).

InformationsquelleAutor Vaibhav Mishra | 2012-08-22

78

Voir ma réponse sujet spatiale et temporelle de la localité.

En particulier, les tableaux sont des blocs de mémoire contigus, sorte de gros morceaux d'eux sera chargé dans le cache lors du premier accès. Cela le rend relativement rapide pour accéder à l'avenir des éléments de la matrice. Les listes liées d'autre part ne sont pas nécessairement dans des blocs de mémoire contigus, et pourrait conduire à plus de défauts de cache, ce qui augmente le temps qu'il faut pour y accéder.

Envisager la suite de possibles mises en mémoire pour un tableau data et liste lié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 une boucle dans ce tableau, le premier accès à ffff 0000 nous obligerait à aller à la mémoire de récupérer (une très lent fonctionnement en cycles CPU). Cependant, après le premier accès au reste de la matrice sera dans le cache, et les demandes d'accès serait beaucoup plus rapide. Avec la liste liée, le premier accès à la ffff 1000 serait également nous obliger à aller à la mémoire. Malheureusement, le processeur mémoire cache la mémoire directement autour de ce lieu, disons tout le chemin jusqu'à ffff 2000. Comme vous pouvez le voir, ce n'est pas réellement la capture de l'un des autres éléments de la liste, ce qui signifie que lorsque nous allons à l'accès l_data->next, nous allons encore avoir à aller à la mémoire.
- Notez que la localité de listes liées peut être améliorée grâce à l'utilisation d'un pool de mémoire. Mais vous avez encore le problème que 'suivant' pointeurs de prendre de l'espace supplémentaire.
- fait un bon point parce que c'est souvent la façon dont les listes chaînées sont mis en œuvre
- Maintenant, j'ai obtenu ce que "Cache manque dans la liste Liée" signifie.
InformationsquelleAutor brc
7

Généralement, lors de l'utilisation d'un tableau et que vous accéder à des éléments qui sont à proximité les uns des autres. Cela est particulièrement vrai lors de l'accès à un tableau de manière séquentielle.

Lorsque vous accéder à la mémoire, un morceaux sont mis en cache à différents niveaux. La localité de Cache fait référence à la probabilité d'une succession d'opérations en cours dans le cache et donc d'être plus rapide. Dans un tableau, vous maximisez les chances de séquentielles accès à l'élément de l'être dans le cache.

Avec des listes, par contre-exemple, il n'y a aucune garantie que les éléments qui apparaissent séquentiellement dans la liste sont réellement disposés près de l'autre dans la mémoire. Cela signifie moins de cache, et de la dégradation des performances.
- Cela dépend beaucoup du processeur et de la mémoire de l'architecture, cependant. Les processeurs qui sont conçus pour la programmation orientée objet, par exemple, généralement, ne se soucient pas de la localité, tout simplement parce que de par la définition de "orienté objet" vous ne pouvez pas garantir la localité de toute façon.
- Donc, ne vous dire que les programmes écrits en langages OOP ne pas utiliser les caches efficacement, ou il y a plus de cache dans ce cas, par rapport à un programme écrit dans un langage procédural?
InformationsquelleAutor paddy

Vous devez vous connecter pour publier un commentaire.