J'ai deux pour les boucles qui recherchent essentiellement deux tableaux différents (chacun ayant une taille d'environ 2-4K au maximum) et définissez une valeur dans un troisième réseau en fonction de ces valeurs. Pour une ratification étrange, il existe un facteur deux différences entre les performances de ce code de code en fonction de l'ordre que j'ai mis les deux pour les boucles.
Ceci est la première configuration. Il exécute dans ~ 150 millisecondes sur mon PC: maintenant si je ne change plus que l'ordre des boucles comme celui-ci Le temps d'exécution total de la méthode tombe à environ environ 400 millisecondes. Comment un échange simple 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 une performance de pointeur?
6 Réponses :
C'est une disposition de données. Pensez à la mémoire comme une matrice de dimension unique. C'est ainsi que les choses sont conçues sur le disque (en ce qui concerne l'ordinateur.) Donc, lors de la création de tableaux multidimensionnaires, lorsque vous modifiez la commande de boucle, vous modifiez la manière dont le tableau est traversé. Au lieu de lire dans l'ordre, vous sautez de la position à la position.
Un réseau multi-dimensions vous ressemble à celui-ci:
et comme ceci à l'ordinateur. Le moyen optimal de traverser a les index suivant la flèche ci-dessous:
Ainsi, lorsque vous changez que vous êtes en boucle, la matrice est traversée comme ceci:
Ainsi, vous obtenez plus de cache Misses et un algorithme performant plus pauvre.
... c'est comme une matrice de chaises dans un cinéma ... visiter chaque chaise en parcourant la rangée par ligne est plus rapide que la colonne par colonne ...
Sans cache toutefois, l'ordre de traverser à travers la mémoire d'accès aléatoire (RAM) n'a pas d'importance (en supposant que tout le tableau est sur la RAM) - "Le mot aléatoire fait donc référence au fait que tout élément de données peut être renvoyé dans un Temps constant, quel que soit son emplacement physique et qu'il soit lié ou non à la pièce précédente de données. [1] " EN.WIKIPEDIA.ORG/WIKI/RANDOM-Access_Memory
Il est très probable lié au cache Hits / Misses. La différence réside dans l'accès séquentiel vs dispersé qui se situe en taille supérieure à la taille d'une ligne de cache.
Pour les boucles plaines C ++, cela aiderait également à faire en arrière les boucles pour gagner un peu de performance sur la boucle. Je ne sais pas comment il convient à .NET.
Pourquoi a-t-il de l'aide pour faire de la boucle en arrière?
Si vous avez un coup d'œil au code de montage, le test est plus facile. Lors de la boucle jusqu'à 0, le test est facile, car vous décrémentez et testez le drapeau Z de la CPU. En comparant à une autre limite, vous devez ajouter un CMP supplémentaire (pour X86 processeurs à titre d'exemple)
localité, localité, localité des données. De Wikipedia (qui dit mieux que j'aurais):
Structures de données linéaires: la localité se produit souvent car le code contient des boucles qui ont tendance à faire référence à des tableaux de référence 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 accessibles linéairement. Par exemple, la simple traversée des éléments d'une matrice unidimensionnelle, de l'adresse de base au plus haut élément exploiterait la localité séquentielle de la matrice en mémoire. [2] La localité équidistante plus générale se produit lorsque la traversée linéaire est supérieure à une zone plus longue de structures de données adjacentes ayant une structure et une taille identiques, et en plus de cela, les structures entières ne sont pas dans l'accès, mais uniquement les mêmes éléments correspondants des structures. C'est le cas où une matrice est représentée sous forme de matrice séquentielle de lignes et que l'exigence est d'accéder à une seule colonne de la matrice.
Je me souviens de lire à ce sujet dans Code complet . Dans la plupart des langues, les tableaux sont configurés avec le dernier index configuré de manière séquentielle, vous accédez donc à des octets directement dans une rangée lors de l'itération du dernier index, au lieu de sauter lors de l'itération lors de l'itération du premier.
Le dernier index est celui où les données seraient commandées de manière séquentielle, pas la première.
Votre intuition a raison, 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 cache Hits.
moyen le plus rapide de boucler via un tableau 2D?
Mais, SHHHH, nous ne sommes pas censés se soucier de la performance non? :)
Ce code est écrit pour un concours de performances en C #, il est donc absolument crucial. Je ne peux pas croire que je n'ai pas pensé au stockage de la mémoire.
@Qua, oui, j'étais juste facetieuse. La ligne de fête actuelle parmi de nombreuses personnes semble être que la performance ne compte plus. Mais c'est juste idiot.
Je pense également que les tailles relatives des matrices A et B feraient une différence.
Si une longueur est grande et B.Longueur est petite, la deuxième option doit être plus rapide. Inversement, si une longueur est petite et B.Longueur est grande, la première option serait plus rapide. Le problème évite le coût de la configuration / dératrement de la boucle interne.
BTW, pourquoi avez-vous
int alen = a.length;
mais aussi appelez-le directement. Semble que vous devriez choisir l'un ou l'autre.
Tout en profilant, le code tente de comprendre ce qui se passait, j'ai joué avec la mise en cache des longueurs de la matrice, ce que vous voyez sont des morceaux dispersés de cette tentative. Il n'y avait pas de gain d'optimisation, alors je me suis finalement débarrassé de cela.
Pourquoi si la longueur est grande et B.Longueur est petite, la deuxième option devrait être plus rapide?
Voir ici: Stackoverflow .com / questions / 997212 / ...
Quelles sont les longueurs de
a etb ?La réponse est précisément celle dans le lien que @Mike Daniels fournis. C'est un exemple de problème / optimisation de cache très connu.
Pour beaucoup de meilleures performances avec des tableaux multidimensionnels, vous devriez envisager d'utiliser des pointeurs.