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

Question

Vous trouverez ci-dessous deux programmes qui sont presque identiques, sauf que j'ai interverti l'option i et j variables autour. Les deux s'exécutent dans 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; }
   }
}

Answer 1

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

Vous avez un tableau à deux dimensions, mais la mémoire de l'ordinateur est par nature unidimensionnelle. Donc, alors 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 sous la forme d'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 deuxième exemple, vous accédez au tableau en bouclant d'abord sur le deuxième nombre, c'est-à-dire.. :

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

Ce qui signifie que vous les frappez tous dans l'ordre. Maintenant, regardez la 1ère version. Tu le 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 à deux dimensions en mémoire, vous lui demandez de sauter partout. Mais maintenant, l'argument massue : 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 transmises à l'unité centrale par petits morceaux (appelés "lignes de cache"), généralement de 64 octets. Si vous avez des entiers de 4 octets, cela signifie que vous obtenez 16 entiers consécutifs dans un petit paquet bien ordonné. L'extraction de ces morceaux de mémoire est en fait assez lente ; votre CPU peut effectuer beaucoup de travail dans le temps nécessaire au chargement d'une seule ligne de cache.

Maintenant, regardez l'ordre des accès : Le deuxième exemple consiste à (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 sur lequel travailler.

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

Note importante :

Maintenant que vous avez la réponse, voici une remarque intéressante : il n'y a aucune raison inhérente pour que votre deuxième exemple soit le plus rapide. Par exemple, en Fortran, le premier exemple serait rapide et le second lent. C'est parce qu'au lieu de développer les choses en "lignes" conceptuelles comme le fait le C, Fortran 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 du C est appelée "row-major" et celle du Fortran "column-major". Comme vous pouvez le constater, il est très important de savoir si votre langage de programmation est de type "row-major" ou "column-major" ! Voici un lien pour plus d'informations : http://en.wikipedia.org/wiki/Row-major_order

Answer 2

Rien à voir avec l'assemblage. Cela est dû à manques dans le cache .

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

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

Answer 3

La version 2 fonctionnera beaucoup plus rapidement car elle utilise mieux le cache de votre ordinateur que la version 1. Si vous y réfléchissez, les tableaux ne sont que des zones contiguës de la mémoire. Lorsque vous demandez un élément d'un tableau, votre système d'exploitation va probablement placer dans le cache une page de mémoire qui contient cet élément. Cependant, comme les éléments suivants se trouvent également sur cette page (parce qu'ils sont contigus), l'accès suivant sera déjà dans le cache ! C'est ce que fait la version 2 pour augmenter sa vitesse.

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, et le programme ne peut donc pas profiter autant de la mise en cache du système d'exploitation.

Answer 4

La raison en est l'accès aux données par le cache. Dans le second programme, vous balayez linéairement la mémoire, ce qui bénéficie de la mise en cache et de la préextraction. Le modèle d'utilisation de la mémoire de votre premier programme est beaucoup plus étalé et a donc un comportement de cache moins bon.

Answer 5

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é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 elle devrait incrémenter le pointeur "p" de 4000 à chaque fois.

EDIT : p++ et même *p++ = .. peut être compilé en une seule instruction CPU dans la plupart des CPU. *p = ..; p += 4000 ne le peut pas, il y a donc moins d'intérêt à l'optimiser. C'est également plus difficile, car le compilateur doit connaître et utiliser la taille du tableau interne. Et cela ne se produit pas si souvent dans la boucle interne d'un code normal (cela ne se produit que pour les tableaux multidimensionnels, où le dernier indice est maintenu constant dans la boucle, et l'avant-dernier est déplacé), l'optimisation est donc moins prioritaire.