Pourquoi y a-t-il une différence significative dans ce C ++ pour le temps d’exécution de la boucle?

C’est un problème de cache mémoire.

masortingx[i][j] a de meilleurs résultats en cache que la masortingx[j][i] , puisque la masortingx[i][j] a plus de chances d’accéder à la mémoire.

Par exemple, lorsque nous accédons à la masortingx[i][0] , le cache peut charger un segment continu de mémoire contenant la masortingx[i][0] , accédant ainsi à la masortingx[i][1] , masortingx[i][2] , …, bénéficiera de la vitesse de mise en cache, puisque la masortingx[i][1] , la masortingx[i][2] , … sont proches de la masortingx[i][0] .

Cependant, lorsque nous accédons à la masortingx[j][0] , elle est loin de la masortingx[j - 1][0] et peut ne pas être mise en cache et ne peut pas bénéficier de la vitesse de mise en cache. En particulier, une masortingce est normalement stockée en tant que grand segment continu de mémoire, et le cacher peut prédire le comportement de l’access à la mémoire et toujours mettre la mémoire en cache.

C’est pourquoi la masortingx[i][j] est plus rapide. Ceci est typique dans l’optimisation des performances basée sur le cache du processeur.

La différence de performances est due à la stratégie de mise en cache de l’ordinateur.

La masortingx[i][j] tableau à 2 dimensions masortingx[i][j] est représentée comme une longue liste de valeurs dans la mémoire.

Par exemple, le tableau A[3][4] ressemble à:

 1 1 1 1 2 2 2 2 3 3 3 3 

Dans cet exemple, chaque entrée de A [0] [x] est définie sur 1, chaque entrée de A [1] [x] définie sur 2, …

Si votre première boucle est appliquée à cette masortingce, l’ordre d’access est le suivant:

 1 2 3 4 5 6 7 8 9 10 11 12 

Alors que l’ordre d’access aux secondes boucles ressemble à ceci:

 1 4 7 10 2 5 8 11 3 6 9 12 

Lorsque le programme accède à un élément du tableau, il charge également les éléments suivants.

Par exemple, si vous accédez à A[0][1] , A[0][2] et A[0][3] sont également chargés.

La première boucle doit donc effectuer moins d’opérations de chargement, car certains éléments sont déjà dans le cache lorsque cela est nécessaire. La seconde boucle charge les entrées dans le cache qui ne sont pas nécessaires à ce moment, ce qui entraîne davantage d’opérations de chargement.

D’autres personnes ont bien expliqué pourquoi une forme de votre code utilise plus efficacement le cache mémoire que l’autre. J’aimerais append quelques informations de base que vous ne connaissez peut-être pas: vous ne réalisez probablement pas à quel point les access à la mémoire principale sont coûteux aujourd’hui.

Les chiffres affichés dans cette question semblent me convenir et je vais les reproduire ici car ils sont si importants:

 Core i7 Xeon 5500 Series Data Source Latency (approximate) L1 CACHE hit, ~4 cycles L2 CACHE hit, ~10 cycles L3 CACHE hit, line unshared ~40 cycles L3 CACHE hit, shared line in another core ~65 cycles L3 CACHE hit, modified in another core ~75 cycles remote remote L3 CACHE ~100-300 cycles Local Dram ~60 ns Remote Dram ~100 ns 

Notez le changement d’unités pour les deux dernières entrées. Selon le modèle que vous avez, ce processeur fonctionne à 2,9–3,2 GHz; pour simplifier le calcul, appelons-le simplement 3 GHz. Donc, un cycle est de 0,33333 nanosecondes. Ainsi, les access DRAM sont également 100-300 cycles.

Le fait est que le processeur aurait pu exécuter des centaines d’instructions pendant le temps nécessaire pour lire une ligne de cache dans la mémoire principale. Ceci s’appelle le mur de mémoire . De ce fait, l’utilisation efficace de la mémoire cache est plus importante que tout autre facteur de performance globale sur les processeurs modernes.

La réponse dépend un peu de la façon dont la masortingx est définie. Dans un tableau entièrement alloué dynamicment, vous auriez:

 T **masortingx; masortingx = new T*[n]; for(i = 0; i < n; i++) { t[i] = new T[m]; } 

Ainsi, chaque masortingx[j] nécessitera une nouvelle recherche de mémoire pour le pointeur. Si vous faites la boucle j dehors, la boucle interne peut réutiliser le pointeur pour la masortingx[j] tous pour toute la boucle interne.

Si la masortingce est un simple tableau 2D:

 T masortingx[n][m]; 

alors la masortingx[j] sera simplement une multiplication par 1024 * sizeof(T) - ce qui peut être fait en ajoutant 1024 * sizeof(T) l'index de la boucle dans le code optimisé.

En plus de cela, nous avons des facteurs de localité de cache. Les caches ont des "lignes" de données qui sont généralement de 32 à 128 octets par ligne. Donc, si votre code lit l'adresse X , le cache se chargera de valeurs de 32 à 128 octets autour de X Donc, si le paramètre NEXT dont vous avez besoin est uniquement de sizeof(T) avant par rapport à l'emplacement actuel, il est fort probable que le cache [et les processeurs modernes détectent également que vous parcourez tous les emplacements mémoire et pré-charge le Les données].

Dans le cas de la boucle interne j , vous lisez un nouvel emplacement de sizeof(T)*1024 distance pour chaque boucle [ou possiblya une plus grande distance si elle est allouée dynamicment]. Cela signifie que les données en cours de chargement ne seront pas utiles pour la prochaine boucle, car elles ne sont pas dans les 32 à 128 octets suivants.

Et enfin, il est tout à fait possible que la première boucle soit plus optimisée, grâce aux instructions SSE ou similaires, qui permettent d’effectuer le calcul encore plus rapidement. Mais ceci est probablement marginal pour une masortingce aussi grande, car les performances sont fortement liées à la mémoire à cette taille.

Le matériel de mémoire n’est pas optimisé pour fournir des adresses individuelles: il a plutôt tendance à fonctionner sur de plus gros blocs de mémoire continue appelés lignes de cache . Chaque fois que vous lisez une entrée de votre masortingce, l’intégralité de la ligne de cache dans laquelle elle se trouve est également chargée dans le cache.

Le classement en boucle plus rapide est configuré pour lire la mémoire dans l’ordre; Chaque fois que vous chargez une ligne de cache, vous utilisez toutes les entrées de cette ligne de cache. Chaque passage à travers la boucle externe, vous lisez chaque entrée de la masortingce une seule fois.

L’ordre de boucle plus lent n’utilise toutefois qu’une seule entrée de chaque ligne de cache avant de continuer. Ainsi, chaque ligne de cache doit être chargée plusieurs fois, une fois pour chaque entrée de masortingce dans la ligne. Par exemple, si un double est de 8 octets et une ligne de cache de 64 octets, chaque passage dans la boucle externe doit lire chaque entrée de la masortingce huit fois au lieu d’une seule fois.

Cela dit, si vous aviez activé les optimisations, vous ne verriez probablement aucune différence: les optimiseurs comprennent ce phénomène et les bons sont capables de reconnaître qu’ils peuvent échanger quelle boucle est la boucle interne et quelle boucle est la boucle externe de ce extrait de code.

(de plus, un bon optimiseur n’aurait effectué qu’un seul passage dans la boucle la plus externe, car il reconnaît que les 999 premières fois sont sans rapport avec la valeur finale de la sum )

La masortingce est stockée en mémoire en tant que vecteur. En accédant à la première manière, on accède à la mémoire de manière séquentielle. Pour y accéder de la seconde manière, il faut parcourir les emplacements de mémoire. Voir http://en.wikipedia.org/wiki/Row-major_order

Si vous accédez à j -i, la dimension j est mise en cache afin que le code de la machine ne soit pas obligé de le modifier à chaque fois, la deuxième dimension n’est pas mise en cache, vous supprimez donc le cache à chaque fois.

Basé sur le concept de localité de référence, il est très probable qu’un morceau de code accède à des emplacements de mémoire adjacents. Donc, plus de valeurs sont chargées dans le cache que ce qui est demandé. Cela signifie plus de résultats de cache. Votre premier exemple est bien satisfaisant pendant que vous codez dans le second exemple.