Pourquoi cela améliore-t-il les performances?

Question

J'ai deux pour les boucles qui recherchent essentiellement dans deux tableaux différents (chacun ayant une taille autour de 2-4k à la crête) et définissez une valeur dans un troisième tableau en fonction de ces valeurs. Pour une raison étrange, il existe un facteur deux différence entre les performances de ce morceau de code en fonction de l'ordre dans lequel j'ai mis les deux pour les boucles.

Ceci est la première configuration. Il exécute en ~ 150 millisecondes sur mon PC:

public static int[] SchoolMultiplication(int[] a, int[] b, int numberBase) 
{ 
    List<double> times = new List<double>(); 
    TimeTest timeTest = new TimeTest(); 

    int aLen = a.Length; 
    int bLen = b.Length; 

    int[,] resultMatrix = new int[a.Length + b.Length, aLen]; 
    int[] result = new int[a.Length + b.Length]; 

    timeTest.Start(); 

    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
    { 
     for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 

     { 
      resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
     } 
    } 

Maintenant, si je change rien, mais l'ordre des boucles comme celui-ci

for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 
{ 
    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
{ 
     resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
    } 
} 

La durée totale de la méthode chute à environ ~ 400 millisecondes . Comment un simple échange d'ordre de boucle améliore-t-il les performances de près de 300%? Je suppose que c'est une sorte de mise en cache ou de performance de pointeur?

Answer 1

C'est un arrangement de données. Pensez à la mémoire comme un tableau de dimension unique. C'est ainsi que les choses sont arrangées sur le disque (en ce qui concerne l'ordinateur). Ainsi, lors de la création de tableaux multidimensionnels, lorsque vous changez d'ordre de boucle, vous changez la façon dont le tableau est traversé. Au lieu de lire dans l'ordre, vous sautez d'une position à l'autre.

---

Un tableau à plusieurs dimensions ressemble à ceci pour vous:

Et comme celui-ci à l'ordinateur. La meilleure façon de déplacement a les indices suivants la flèche ci-dessous:

Ainsi, lorsque vous vous changez tableau boucle le tableau est traversée comme ceci:

Ainsi vous obtenez plus de défauts de cache et un algorithme de moins performants .

Answer 2

Il est très probable que ce soit lié au cache hits/misses. La différence réside dans l'accès séquentiel par rapport à l'accès dispersé dont la taille est supérieure à la taille d'une ligne de cache.

Pour les boucles C++ simples, il serait également utile de faire reculer les boucles pour obtenir un peu de performance sur la boucle. Je ne sais pas comment cela convient à .NET.

Answer 3

Localité, localité, localité de données. De Wikipedia (qui le dit mieux que je n'aurais):

Structures de données linéaires: La localité se produit souvent parce que le code contient des boucles qui tendent à référencer des tableaux ou d'autres structures de données par des indices. La localité séquentielle, un cas particulier de localité spatiale, se produit lorsque des éléments de données pertinents sont disposés et consultés linéairement. Par exemple, la traversée simple d'éléments dans un tableau à une dimension, de l'adresse de base à l'élément le plus élevé, exploiterait la localité séquentielle du tableau en mémoire. [2] La localité équidistante plus générale se produit lorsque la traversée linéaire est sur une zone plus longue de structures de données adjacentes ayant une structure et une taille identiques, et en plus, toutes les structures sont en accès, mais seulement les mêmes éléments correspondants des structures. C'est le cas lorsqu'une matrice est représentée comme une matrice séquentielle de lignes et que l'exigence est d'accéder à une seule colonne de la matrice. Je me souviens d'avoir lu à ce sujet dans Code Complete

Answer 4

Dans la plupart des langages, les tableaux sont configurés avec le dernier index mis en place de manière séquentielle. Ainsi, vous accédez aux octets directement dans une ligne lors de l'itération sur le dernier index, au lieu de passer en revue le premier.

Answer 5

Votre intuition est bonne, c'est un problème de mise en cache. @Mike Daniels post à la question ci-dessous décrit essentiellement le même problème. Le deuxième bit de code obtiendra beaucoup plus de hits de cache.

Fastest way to loop through a 2d array?

Mais, chut, nous ne sommes pas censés se soucier de droit d'exécution? :)

Answer 6

Je pense aussi que les tailles relatives des tableaux a et b feraient une différence.

Si a.length est grand et b.length est petit, la deuxième option devrait être plus rapide. Inversement, si a.length est petit et b.length est grand, la première option serait plus rapide. Le problème est d'éviter le coût d'installation/démontage de la boucle interne.

BTW, pourquoi avez-vous

int Alen = a.length;

Mais appelez aussi a.Length directement? On dirait que vous devriez choisir l'un ou l'autre.