Le moyen le plus rapide de parcourir un tableau 2D?

Question

Je viens de tombé sur ce blog. L'auteur montre deux exemples de code qui boucle par le biais d'un rectangle et de calculer quelque chose (je suppose que le code informatique est juste un espace réservé). Sur l'un des exemple, il analyse le rectangle à la verticale, et sur l'autre horizontalement. Il dit alors que la seconde est plus rapide, et chaque programmeur doit savoir pourquoi. Maintenant, je ne dois pas être un programmeur, parce que pour moi, il est exactement le même. Quelqu'un peut-il expliquer que pour moi?

Merci.

Answer 1

Cohérence du cache. Lorsque vous scannez horizontalement, vos données seront plus proches les unes des autres en mémoire, vous aurez donc moins de ratés de cache et donc les performances seront plus rapides. Pour un rectangle suffisamment petit, cela n'aura pas d'importance.

Answer 2

Une réponse a été acceptée, mais je ne pense pas que c'est l'ensemble de l'histoire.

Oui, le cache est une grande partie de la raison de tous ces éléments doivent être stockés dans la mémoire de certains de l'ordre. Si vous index à travers eux, dans l'ordre où elles sont stockées, vous êtes susceptible d'avoir le moins de défauts de cache. Probable.

L'autre question (également mentionné par beaucoup de réponses) que pratiquement chaque processeur dispose d'un très entier rapide incrément de l'instruction. Ils n'ont généralement pas une très rapide "incrémenter par une quantité multipliée par ce deuxième arbirary montant". C'est ce que vous demandez quand vous index "contre le grain".

Un troisième problème, c'est de l'optimisation. Beaucoup d'efforts et de recherche a été mis sur l'optimisation des boucles de ce genre, et votre compilateur sera beaucoup plus susceptibles d'être en mesure de mettre l'un de ces optimisations en effet si vous index par le biais d'une certaine raisonnable sorte d'ordre.

Answer 3

Pour se développer sur les réponses précédentes un peu:

Habituellement, en tant que programmeurs, nous pouvons penser à nos programmes de mémoire adressable comme un plat de tableau d'octets, de 0x00000000 à 0xFFFFFFFF. Le système d'exploitation réserve de certaines de ces adresses (tous ceux inférieurs à 0x800000000, disons) pour son propre usage, mais nous pouvons faire ce que nous aimons avec les autres. Tous ces emplacements de mémoire de vivre dans la RAM de l'ordinateur, et lorsque l'on veut lire ou écrire à eux d'émettre des instructions appropriées.

Mais ce n'est pas vrai! Il y a un tas de complications d'altération que le simple modèle de processus de mémoire: la mémoire virtuelle, l'échange, et le cache.

Parler de la RAM prend un temps assez long. C'est beaucoup plus rapide que d'aller sur le disque dur, car il ne sont pas tout à faire tourner des assiettes ou des aimants impliqués, mais c'est encore assez lent par rapport aux normes d'un PROCESSEUR récent. Donc, lorsque vous essayez de lire à partir d'un endroit particulier de la mémoire, ton CPU n'est pas juste de lire qu'un emplacement dans un registre plus. Au lieu de cela, il lit cet emplacement, /et tout un tas de lieux à proximité/, dans une cache du processeur qui vit sur le CPU et peut être consulté à beaucoup plus rapidement que la mémoire principale.

Nous avons maintenant une plus compliqué, mais plus correct, vue sur le comportement de l'ordinateur. Quand on essaie de lire un emplacement dans la mémoire, nous avons d'abord regarder dans le cache du processeur pour voir si la valeur à l'emplacement en question est déjà y être stockées. Si elle l'est, nous utilisons la valeur dans le cache. Si ce n'est pas le cas, nous prenons un long voyage dans la mémoire principale, de récupérer la valeur ainsi que plusieurs de ses voisins et de les coller dans le cache, coups de pied sur une partie de ce que l'habitude d'être là pour faire de la place.

Maintenant, nous pouvons voir pourquoi le deuxième extrait de code est plus rapide que la première. Dans le deuxième exemple, nous avons d'abord accéder a[0], b[0], et c[0]. Chacune de ces valeurs est mis en cache, ainsi que leurs voisins, dire a[1..7], b[1..7], et c[1..7]. Puis, quand nous avons accès a[1], b[1], et c[1], ils sont déjà dans le cache, et nous pouvons les lire rapidement. Finalement, nous arrivons à a[8], et aller à la RAM de nouveau, mais sept fois sur huit, nous sommes en utilisant de nice le cache rapide de la mémoire au lieu de maladroit, lent de la mémoire RAM.

(Alors pourquoi ne pas y accède a, b, et c coup de pied hors de la cache? C'est un peu compliqué, mais en gros, le processeur décide de l'endroit où stocker une valeur donnée dans le cache par son adresse, afin que les trois objets qui ne sont pas à proximité les uns des autres dans l'espace sont peu susceptibles d'être mis en cache dans le même emplacement).

En revanche, pensez à le premier extrait de lbrandy post. Nous avons d'abord lu a[0], b[0], et c[0], la mise en cache a[1..7], b[1..7], et c[1..7]. Puis nous avons accès a[width], b[width], et c[width]. En supposant que la largeur est >= 8 (ça l'est probablement, ou autre chose, nous ne se soucient pas de ce genre de bas niveau d'optimisation), nous devons aller à la RAM de nouveau, la mise en cache d'un nouvel ensemble de valeurs. Au moment où nous arrivons à l' a[1], il aura probablement été mis à la porte de la cache pour faire de la place pour autre chose. Dans le pas-du-tout-rare cas d'un trio de tableaux qui sont plus grands que le cache du processeur, il est probable que /chaque/ lecture de manquer le cache, dégrader les performances énormément.

Cela a été un très haut niveau de discussion de moderne comportement de mise en cache. Pour quelque chose de plus approfondi et technique, cela ressemble à une complète pourtant lisible traitement du sujet.

Answer 4

Le cache est en effet la raison, mais si vous voulez connaître la chair de l'argument, vous pouvez jeter un oeil à la "Ce que chaque programmeur devrait savoir sur la mémoire" par U. Drepper:

http://people.redhat.com/drepper/cpumemory.pdf

Answer 5

Oui, "cohérence du cache" ... bien sûr, cela dépend, vous pouvez optimiser l'allocation de mémoire pour les analyses verticales. Traditionnellement, la mémoire vidéo est allouée de gauche à droite, de haut en bas, en remontant, je suis sûr, à l'époque des écrans CRT qui dessinaient des lignes de balayage de la même manière. En théorie, vous pouvez changer cela - tout cela pour dire qu'il n'y a rien d'intrinsèque dans la méthode horizontale.