Pourquoi l'ordre des boucles affecte-t-il les performances lors de l'itération sur un tableau 2D?

360

Vous trouverez ci-dessous deux programmes qui sont presque identiques, sauf que j'ai inversé les variables iet j. Ils fonctionnent tous les deux en des temps différents. 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; }
   }
}
marque
la source
26
en.wikipedia.org/wiki/…
Brendan Long
7
Pouvez-vous ajouter des résultats de référence?
naught101
3
Connexe: stackoverflow.com/questions/9888154/…
Thomas Padron-McCarthy
14
@ naught101 Les benchmarks afficheront une différence de performances de 3 à 10 fois. C'est de base C / C ++, je suis complètement perplexe quant à la façon dont cela a obtenu autant de votes ...
TC1
12
@ TC1: Je ne pense pas que ce soit aussi basique; peut-être intermédiaire. Mais il ne faut pas s'étonner que les trucs "basiques" aient tendance à être utiles à plus de gens, d'où les nombreuses upvotes. De plus, c'est une question difficile à google, même si elle est "basique".
LarsH

Réponses:

595

Comme d' autres l' ont dit, la question est le magasin à l'emplacement de mémoire dans le tableau: x[i][j]. Voici un peu pourquoi:

Vous disposez d'un tableau bidimensionnel, mais la mémoire de l'ordinateur est intrinsèquement unidimensionnelle. Donc, pendant 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 sur 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 2ème exemple, vous accédez au tableau en bouclant d'abord sur le 2ème numéro, c'est-à-dire:

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

Cela signifie que vous les frappez tous dans l'ordre. Regardez maintenant la 1ère version. Tu fais:

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

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

Non: à cause des caches. Les données de votre mémoire sont transférées vers le CPU en petits morceaux (appelés «lignes de cache»), généralement 64 octets. Si vous avez des entiers de 4 octets, cela signifie que vous obtenez 16 entiers consécutifs dans un petit ensemble soigné. Il est en fait assez lent de récupérer ces morceaux de mémoire; votre processeur peut faire beaucoup de travail dans le temps nécessaire pour charger une seule ligne de cache.

Revenons maintenant à l'ordre des accès: Le deuxième exemple est (1) saisir un morceau de 16 pouces, (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) saisir un morceau de 16 pouces, (2) modifier un seul d'entre eux, (3) répéter 4000 * 4000 fois. Cela va nécessiter 16 fois le nombre de "récupérations" de la mémoire. Votre processeur devra en fait passer du temps à attendre que cette mémoire apparaisse, et pendant qu'il est assis, vous perdez un temps précieux.

Note importante:

Maintenant que vous avez la réponse, voici une note intéressante: il n'y a aucune raison inhérente pour que votre deuxième exemple soit le plus rapide. Par exemple, à Fortran, le premier exemple serait rapide et le second lent. En effet, au lieu d'étendre les choses en "lignes" conceptuelles comme le fait C, Fortran se développe en "colonnes", c'est-à-dire:

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 est appelée «ligne majeure» et celle de Fortran est appelée «colonne principale». Comme vous pouvez le voir, il est très important de savoir si votre langage de programmation est majeur en ligne ou en colonne! Voici un lien pour plus d'informations: http://en.wikipedia.org/wiki/Row-major_order

Robert Martin
la source
14
Ceci est une réponse assez approfondie; c'est ce que j'ai appris en traitant des échecs de cache et de la gestion de la mémoire.
Makoto
7
Vous avez les «première» et «deuxième» versions dans le mauvais sens; le premier exemple fait varier le premier index de la boucle interne et sera l'exemple à exécution plus lente.
caf
Très bonne réponse. Si Mark veut en savoir plus sur de telles choses, je recommanderais un livre comme Write Great Code.
2012 à 13h59
8
Points bonus pour avoir souligné que C a changé l'ordre des lignes de Fortran. Pour le calcul scientifique, la taille du cache L2 est tout, car si tous vos tableaux correspondent à L2, le calcul peut être effectué sans passer par la mémoire principale.
Michael Shopsin
4
@birryree: Ce que tout programmeur doit savoir sur la mémoire est également une bonne lecture.
caf
68

Rien à voir avec l'assemblage. Cela est dû à des échecs de cache .

Les tableaux multidimensionnels C sont stockés avec la dernière dimension comme la plus rapide. Ainsi, la première version manquera le cache à chaque itération, contrairement à la deuxième version. La deuxième version devrait donc être beaucoup plus rapide.

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

Oliver Charlesworth
la source
23

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

La version 1, quant à elle, accède aux éléments par colonne et non par ligne. Ce type d'accès n'est pas contigu au niveau de la mémoire, donc le programme ne peut pas profiter autant de la mise en cache du système d'exploitation.

Oleksi
la source
Avec ces tailles de tableau, le gestionnaire de cache dans le processeur plutôt que dans le système d'exploitation est probablement responsable ici.
krlmlr
12

La raison en est l'accès aux données en cache local. Dans le deuxième programme, vous balayez linéairement la mémoire qui bénéficie de la mise en cache et de la prélecture. Le modèle d'utilisation de la mémoire de votre premier programme est beaucoup plus étendu et a donc un comportement de cache pire.

Codeur à longueur variable
la source
11

Outre les autres excellentes réponses sur les hits de cache, il existe également une différence d'optimisation possible. Votre deuxième boucle est susceptible d'être optimisée 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;
    }
  }

Cela est moins probable pour la première boucle, car il faudrait incrémenter le pointeur "p" avec 4000 à chaque fois.

EDIT: p++ et même *p++ = ..peut être compilé en une seule instruction CPU dans la plupart des CPU. *p = ..; p += 4000ne peut donc pas être optimisé. C'est aussi plus difficile, car le compilateur doit connaître et utiliser la taille du tableau interne. Et cela ne se produit pas souvent dans la boucle interne en code normal (cela se produit uniquement pour les tableaux multidimensionnels, où le dernier index est maintenu constant dans la boucle, et l'avant-dernier est étagé), donc l'optimisation est moins prioritaire .

fishinear
la source
Je ne comprends pas ce que signifie «parce qu'il faudrait sauter le pointeur« p »avec 4000 à chaque fois».
Veedrac
@Veedrac Le pointeur devrait être incrémenté de 4000 à l'intérieur de la boucle intérieure: p += 4000isop++
fishinear
Pourquoi le compilateur trouverait-il cela un problème? iest déjà incrémenté d'une valeur non unitaire, étant donné qu'il s'agit d'un incrément de pointeur.
Veedrac
J'ai ajouté plus d'explications
fishinear
Essayez de taper int *f(int *p) { *p++ = 10; return p; } int *g(int *p) { *p = 10; p += 4000; return p; }dans gcc.godbolt.org . Les deux semblent compiler essentiellement les mêmes.
Veedrac
7

Cette ligne le coupable:

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

La deuxième version utilise une mémoire continue sera donc sensiblement plus rapide.

J'ai essayé avec

x[50000][50000];

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

Nicolas Modrzyk
la source
4

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

Parce que i[y][x]c'est un raccourci pour *(i + y*array_width + x)en C (essayez le chic int P[3]; 0[P] = 0xBEEF;).

En parcourant y, vous parcourez des morceaux de taille array_width * sizeof(array_element). Si vous avez cela dans votre boucle intérieure, vous aurezarray_width * array_height itérations sur ces morceaux.

En retournant la commande, vous n'aurez que array_heightdes itérations de bloc, et entre toute itération de bloc, vous n'aurez que des array_widthitérations sizeof(array_element).

Alors que sur les très anciens processeurs x86, cela n'avait pas beaucoup d'importance, de nos jours le x86 fait beaucoup de prélecture et de mise en cache des données. Vous produisez probablement de nombreux échecs de cache dans votre ordre d'itération plus lent.

Sebastian Mach
la source