Quel ordre de boucles imbriquées pour itérer sur un tableau 2D est le plus efficace ?

Question

Lequel des ordres suivants de boucles imbriquées pour itérer sur un tableau 2D est le plus efficace en termes de temps (performance du cache) ? Pourquoi ?

int a[100][100];

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
       a[i][j] = 10;    
   }
}

o

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
      a[j][i] = 10;    
   }
}

Answer 1

La première méthode est légèrement meilleure, car les cellules assignées sont placées les unes à côté des autres.

Première méthode :

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment

Deuxième méthode :

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment

Answer 2

1. Pour le tableau [100][100] - les deux sont identiques, si le cache L1 est plus grand, alors 100*100*sizeof(int) == 10000*sizeof(int) == [généralement] 40000. Remarque Sandy Bridge - 100*100 entiers devraient être suffisamment d'éléments pour voir une différence, puisque le cache L1 n'est que de 32k.

2. Les compilateurs vont probablement optimiser ce code tout de même

3. En supposant qu'il n'y ait pas d'optimisation du compilateur et que la matrice ne tienne pas dans le cache L1, le premier code est meilleur grâce aux performances du cache [généralement]. Chaque fois qu'un élément n'est pas trouvé dans le cache - vous obtenez un message d'erreur manque de cache - et doivent aller dans la RAM ou le cache L2 [qui sont beaucoup plus lents]. Le transfert d'éléments de la RAM au cache [remplissage du cache] se fait par blocs [généralement 8/16 octets] - ainsi, dans le premier code, vous obtenez au maximum taux d'échec de 1/4 [Dans le second code, les éléments qui étaient déjà dans le cache [insérés dans le remplissage du cache pour les éléments adjacents] - ont été retirés, et vous obtenez un manque de cache redondant.

   • Ceci est étroitement lié à la principe de localité qui est l'hypothèse générale utilisée lors de la mise en œuvre du système de cache. Le premier code suit ce principe alors que le second ne le fait pas - ainsi les performances du cache du premier seront meilleures que celles du second.

Conclusion : Pour toutes les implémentations de cache que je connais, la première ne sera pas pire que la seconde. Ils peuvent être identiques - s'il n'y a pas de cache du tout ou si tout le tableau rentre complètement dans le cache - ou en raison de l'optimisation du compilateur.

Answer 3

Ce type de micro-optimisation dépend de la plate-forme. Il vous faudra donc profiler le code pour pouvoir tirer une conclusion raisonnable.

Answer 4

Dans votre deuxième extrait, la modification de l'élément j dans chaque itération produit un modèle avec une faible localité spatiale. Rappelez-vous que dans les coulisses, une référence de tableau calcule :

( ((y) * (row->width)) + (x) ) 

Considérons un cache L1 simplifié qui a suffisamment d'espace pour seulement 50 rangées de notre tableau. Pour les 50 premières itérations, vous paierez le coût inévitable de 50 manques de cache, mais que se passera-t-il ensuite ? Pour chaque itération de 50 à 99, vous manquerez encore de mémoire cache et devrez aller chercher dans la L2 (et/ou la RAM, etc.). Ensuite, x passe à 1 et y recommence, conduisant à un autre manquement au cache parce que la première ligne de votre tableau a été évincée du cache, et ainsi de suite.

Le premier extrait ne présente pas ce problème. Il accède au tableau dans ordre de rang-majeur Vous n'avez à payer qu'une seule fois pour les erreurs de cache (si une ligne de votre tableau n'est pas présente dans le cache au moment où la boucle commence) par ligne.

Ceci étant dit, cette question dépend beaucoup de l'architecture, il faut donc prendre en compte les spécificités (taille du cache L1, taille des lignes de cache, etc.) pour tirer une conclusion. ) pour tirer une conclusion. Vous devriez également mesurer dans les deux sens et suivre les événements matériels pour disposer de données concrètes permettant de tirer des conclusions.

Answer 5

Si l'on considère que le C++ est le rang majeur, je pense que la première méthode sera un peu plus rapide. En mémoire, un tableau 2D est représenté dans un tableau à une seule dimension et les performances dépendent de l'accès à ce tableau, que ce soit par rangée ou par colonne.