Pourquoi l'ordre des boucles d'affecter les performances lors de l'itération sur un tableau 2D?

possible Duplicate:

laquelle de ces deux boucles est la plus efficace en termes de temps et de performances de cache

ci-dessous deux programmes qui sont presque identiques sauf que j'ai changé les variables i et j autour. Ils courent tous les deux en temps différent. Quelqu'un pourrait-il expliquer pourquoi cela se produit?

Version 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Version 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}
312
demandé sur Community 2012-03-30 06:17:32
la source

7 ответов

Comme d'autres l'ont dit, le problème est le magasin à l'emplacement de la mémoire dans le tableau: x[i][j] . Voici un petit aperçu pourquoi:

vous avez un tableau bidimensionnel, mais la mémoire dans l'ordinateur est de nature unidimensionnelle. Donc, tandis que vous imaginez votre tableau comme ceci:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

votre ordinateur le stocke en mémoire comme une seule ligne:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

dans le 2e exemple, vous accédez au tableau en faisant une boucle au-dessus du 2e exemple numéro premier, i.e.:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

signifie que vous les frappez tous dans l'ordre. Maintenant, regardez la 1ère version. Vous faites:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

à cause de la façon dont C a disposé le tableau 2-d en mémoire, vous lui demandez de sauter partout. Mais maintenant, pour la bosse: Pourquoi est-ce important? Tous les accès de mémoire sont les mêmes, non?

non: à cause des caches. Les données de votre mémoire sont amenées au CPU en petits morceaux (appelé 'lignes de cache'), typiquement 64 octets. Si vous avez des entiers de 4 octets, cela veut dire que vous avez 16 entiers consécutifs dans un joli petit paquet. C'est en fait assez lent pour récupérer ces morceaux de mémoire; votre CPU peut faire beaucoup de travail dans le temps qu'il faut pour une seule ligne de cache à charger.

regardez maintenant en arrière l'ordre des accès: le second exemple est (1) saisir un morceau de 16 ints, (2) les modifier tous, (3) répéter 4000*4000/16 fois. C'est agréable et rapide, et le CPU a toujours quelque chose à travailler.

Le premier exemple est (1) prenez un morceau de 16 ints, (2) modifier un seul d'entre eux, (3) répétez les 4000*4000 fois. Cela va nécessiter 16 fois le nombre de "fetches" de mémoire. Votre CPU devra en fait passer du temps assis à attendre que ce souvenir apparaisse, et pendant qu'il est assis autour de vous, vous perdez un temps précieux.

Remarque Importante:

Maintenant que vous avez la réponse, Voici une note intéressante: il n'y a aucune raison inhérente que votre deuxième exemple doit être le plus rapide. Par exemple, dans le Fortran, le premier exemple serait rapide et le second lent. C'est parce qu'au lieu d'étendre les choses en "lignes" conceptuelles comme C le fait, Fortran se développe en "colonnes", i.e.:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

la disposition de C s'appelle 'row-major' et celle de Fortran 'colonne-major'. Comme vous pouvez le voir, il est très important de sachez si votre langage de programmation est ligne-majeure ou colonne-majeure! Voici un lien pour plus d'informations: http://en.wikipedia.org/wiki/Row-major_order

536
répondu Robert Martin 2016-05-07 18:28:52
la source

rien à voir avec l'assemblage. Cela est dû à cache manque .

C Les matrices multidimensionnelles sont stockées avec la dernière dimension comme la plus rapide. Ainsi, la première version manquera le cache à chaque itération, alors que la seconde ne le fera pas. La deuxième version devrait donc être nettement plus rapide.

Voir aussi: http://en.wikipedia.org/wiki/Loop_interchange .

62
répondu Oliver Charlesworth 2012-03-30 06:20:03
la source
La Version 2 de

fonctionnera beaucoup plus rapidement car elle utilise le cache de votre ordinateur mieux que la version 1. Si vous y pensez, les tableaux ne sont que des zones contiguës de mémoire. Lorsque vous demandez un élément dans un tableau, votre système d'exploitation introduira probablement une page mémoire dans le cache qui contient cet élément. Cependant, puisque les prochains éléments sont aussi sur cette page (parce qu'ils sont contigus), le prochain accès sera déjà en cache! C'est ce que fait la version 2 pour accélérer.

Version 1, d'un autre côté, est l'accès aux éléments par colonne, et non par ligne. Ce type d'accès n'est pas contigu au niveau de la mémoire, de sorte que le programme ne peut pas profiter de la mise en cache de L'OS autant.

22
répondu Oleksi 2012-03-30 06:21:45
la source

la raison est cache-local data access. Dans le second programme vous scannez linéairement à travers la mémoire qui bénéficie de la mise en cache et de la préfetching. Le modèle d'utilisation de la mémoire de votre premier programme est beaucoup plus étalé et a donc un comportement de cache pire.

12
répondu Variable Length Coder 2012-03-30 06:22:38
la source

outre les autres excellentes réponses sur les hits de cache, il y a aussi une différence d'optimisation possible. Votre deuxième boucle est susceptible d'être optimisé par le compilateur en quelque chose d'équivalent à:

  for (j=0; j<4000; j++) {
    int *p = x[j];
    for (i=0; i<4000; i++) {
      *p++ = i+j;
    }
  }

C'est moins probable pour la première boucle, car il aurait besoin d'incrémenter le pointeur "p" avec 4000 à chaque fois.

EDIT: p++ et même *p++ = .. peut être compilé en un seul PROCESSEUR d'instructions dans la plupart des CPU. *p = ..; p += 4000 ne peut pas, il est donc moins avantageux de l'optimiser. C'est aussi plus difficile, parce que le compilateur doit connaître et utiliser la taille du tableau intérieur. Et il ne se produit pas que souvent dans la boucle interne en code normal (il se produit seulement pour les tableaux multidimensionnels, où le dernier indice est maintenu constant dans la boucle, et le deuxième avant-dernier est pas), donc l'optimisation est moins d'une priorité.

10
répondu fishinear 2016-03-07 18:02:48
la source

cette ligne le coupable:

x[j][i]=i+j;

La deuxième version utilise la mémoire continue donc sera beaucoup plus rapide.

j'ai essayé avec

x[50000][50000];

et le temps d'exécution est de 13s pour la version1 contre 0,6 s pour la version2.

8
répondu Nicolas Modrzyk 2012-03-30 06:29:24
la source

j'essaie de donner une réponse générique.

parce que i[y][x] est un raccourci pour *(i + y*array_width + x) en C (essayer la classe int P[3]; 0[P] = 0xBEEF; ).

comme vous itérez sur y , vous itérez sur des morceaux de taille array_width * sizeof(array_element) . Si vous avez cela dans votre boucle interne, alors vous aurez des itérations array_width * array_height au-dessus de ces morceaux.

en renversant la commande, vous aurez seulement array_height bloc-itérations, et entre tout fragment-itération, vous aurez array_width itérations de sizeof(array_element) .

alors que sur des processeurs x86-vraiment anciens cela n'avait pas d'importance, de nos jours x86 fait beaucoup de préfetching et de mise en cache de données. Vous produisez probablement beaucoup de cache manque dans votre itération plus lente-ordre.

3
répondu Sebastian Mach 2012-03-30 19:20:15
la source