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

Ci-dessous sont deux programmes qui sont presque identiques, sauf que je suis passé de la i et j variables autour de. Ils s'exécutent dans des quantités différentes de temps. 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; }
   }
}
  • en.wikipedia.org/wiki/...
  • Pouvez-vous ajouter quelques résultats d'un benchmark?
  • Connexes: stackoverflow.com/questions/9888154/...
  • Les benchmarks montrent une différence de performance de n'importe où entre 3 à 10 fois. C'est basic, C/C++, je suis complètement perplexe sur la manière dont cela a beaucoup de votes...
  • je pense que ce problème est lié au chargement de la matrice de la page à la mémoire en OS de pagination de la politique
  • Pourquoi dois-je toujours manquer de la haute-vote des questions?
  • Je pense que la question pourrait être non seulement pour les c de.
  • Je ne pense pas que c'est que de base, peut-être des intermédiaires. Mais il ne faut pas s'étonner que la "base" des trucs a tendance à être utile au plus grand nombre, d'où les nombreuses upvotes. En outre, c'est une question qui est difficile à google, même si elle est "de base".
  • J'ai ajouté ce test en javascript jsperf.com/2-dimensional-array-loops et vous pouvez vérifier l'effet n'
  • Je n'ai jamais dit que c'est de base en général, je l'ai dit c'est basic, C/C++. Ces langues sont déjà bien avancés par eux-mêmes. "Trucs et sorcellerie" comme cela vient avec eux comme une donnée, et toute personne faisant usage d'entre eux devraient se familiariser à l'avance. Il y a un couple de plus, sur le dessus de ma main, à l'aide de postfix incrementors au lieu de préfixe sur STL itérateurs pour éviter de faire une copie superflue, mais je le prends vous obtenez l'essentiel. Ils vous donnent tous la corde, vous devez vous accrocher et aucun signe que vous êtes sur le point de la plupart des autres (de niveau supérieur) langues ne pas vous laisser faire ça.
  • de base, C est ce que je faisais référence (ce problème n'est pas spécifique à C++, qui est un saut énorme dans la complexité). Mais ce même problème peut s'appliquer à la BASE. "Toute personne qui fait usage d'entre eux devraient se familiariser à l'avance" - facile pour une personne bien informée à dire. Avez-vous appris au sujet de ce problème particulier avant que vous avez fait votre première boucle imbriquée avec un tableau 2D? Je sais que je n'ai pas! Je ne pense pas que j'ai utilisé ces grands tableaux, mais ce n'était pas parce que je savais que de rester loin d'eux pour des raisons de performances!
  • Peut être différent pour les gpu noyaux de processeur.
  • Je suis à la réouverture de cette question car je crois que c'est un mieux "canonique double" que celle liée, principalement en raison de quelques belles réponses postées ici.
  • les résultats d'un Benchmark pour N=10000: la première méthode est 3.68 fois plus lent, 1.092 s vs 0.296 s. (Résultats d'une exécution, il y a beaucoup de variabilité entre les pistes). La différence de vitesse dépendra probablement de la taille relative entre votre cache du CPU et de la taille du tableau choisi.
  • GCC 8 et à venir Clang 7 (avec -mllvm -enable-loopinterchange drapeau) ont amélioré leur boucle de l'échangeur routines d'optimisation et de générer exactement le même montage pour les deux cas, gcc.godbolt.org/z/EB-PRg

InformationsquelleAutor Mark | 2012-03-30