J'ai eu un problème à mon examen pour le sujet principal du langage de programmation. Je pensais depuis longtemps mais je n'ai toujours pas compris le problème
problème: Vous trouverez ci-dessous un programme C, qui est exécuté dans l'environnement MSVC ++ 6.0 sur un PC avec configuration ~ CPU Intel 1.8GHz, RAM 512MB P>
#define M 10000
#define N 5000
int a[M][N];
void main() {
int i, j;
time_t start, stop;
// Part A
start = time(0);
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
a[i][j] = 0;
stop = time(0);
printf("%d\n", stop - start);
// Part B
start = time(0);
for (j = 0; j < N; j++)
for (i = 0; i < M; i++)
a[i][j] = 0;
stop = time(0);
printf("%d\n", stop - start);
}
5 Réponses :
ordre majeur de la ligne par rapport à la colonne - ordre majeur.
Rappelez-vous d'abord que tous les tableaux multidimensionnels sont représentés en mémoire comme un bloc de mémoire conditionné. Ainsi, la matrice multidimensionnelle A (m, n) peut être représentée en mémoire comme
A00 A01 A02 ... A0N A10 A11 A11 ... A1N A20 ... AMN
La première boucle, vous passez à travers ce bloc de mémoire séquentiellement. Ainsi, vous passez à travers la matrice traversant les éléments de l'ordre suivant dans la seconde boucle, vous ignorez dans la mémoire et parcourez la matrice traversant les éléments dans les éléments suivants Commandez ou, peut-être plus clairement, tout ce qui saute autour de vous parce que vous ne gagnez pas vraiment parce que vous ne gagnez pas Avantages de la mise en cache. Lorsque vous passez à travers le tableau séquentiellement, les éléments voisins sont chargés dans le cache. Lorsque vous sautez à travers le tableau, vous ne recevez pas ces avantages et continuez à obtenir le cache manque de nuire aux performances.
Pourriez-vous expliquer plus? Je cherchais ceux-ci dans le principe du livre du langage de programmation mais je ne l'ai pas encore trouvé :(
+1. Un lien rapide Wikipedia pour la question Postituer: en.wikipedia.org/wiki/row-major_order " a>
@Minh: Recherchez la phrase "localité de référence", peut-être?
en raison des optimisations architecturales matérielles. La partie A est d'exécuter des opérations sur des adresses de mémoire séquentielles, ce qui permet au matériel d'accélérer sensiblement comment les calculs sont traités. La partie B saute essentiellement en mémoire tout le temps, qui défait beaucoup d'optimisations matérielles.
Concept de clé de ce cas spécifique est cache de processeur .
Cela concerne la manière dont la mémoire de la matrice est aménagée et la manière dont il est chargé dans le cache et accessible: dans la version A, lors de l'accès à une cellule du tableau, les voisins sont chargés avec le cache, et le Le code accède ensuite immédiatement à ces voisins. Dans la version B, une cellule est accessible (et ses voisins chargés dans le cache), mais l'accès suivant est éloigné, sur la ligne suivante, et la ligne de cache entière a donc été chargée mais une seule valeur utilisée et une autre ligne de cache doit être rempli pour chaque accès. D'où la différence de vitesse.
MSDN a eu un bel article en parlant récemment à ce sujet par rapport aux bitmaps. L'article est MSDN.MicRosoft.com/en-us/ magazine / cc850829.aspx "cible =" _ vide "> msdn.microsoft.com/en-us/magazine/cc850829.a SPX > ici.
Le tableau que vous déclarez est mis en place de la ligne en mémoire. Fondamentalement, vous avez un grand bloc de m × n entiers et c un peu de scandale pour vous faire croire qu'il est rectangulaire. Mais en réalité, c'est plat.
Ainsi, lorsque vous ithérez-vous à travers la ligne de ligne (avec une variable de boucle extérieure), vous allez vraiment de linéairement à travers la mémoire. Quelque chose que le cache de la CPU gère très bien.
Cependant, lorsque vous ithétiez-la avec n dans la boucle extérieure, vous faites toujours plus ou moins de sauts aléatoires en mémoire (au moins pour le matériel que cela ressemble à cela). Vous accédez à la première cellule, puis déplacez-les des entiers plus loin et faites la même chose, etc., car vos pages en mémoire sont généralement d'environ 4 kib, une autre page est accessible pour chaque l'itération Boucle intérieure. De cette façon, presque toute stratégie de mise en cache échoue et que vous voyez un ralentissement majeur.
Le problème est ici, comment votre tableau est couché en mémoire.
Dans la mémoire de l'ordinateur, les tableaux sont normalement alloués, tels que, que d'abord toutes les colonnes de la première ligne se produisent, puis de la deuxième rangée et ainsi de suite.
La mémoire de votre ordinateur est mieux considérée comme une longue rayure d'octets - il s'agit d'une matrice unidimensionnelle de mémoire - et non de deux matrices multidimensionnelles doivent être attribuées de la manière décrite.
vient maintenant un autre problème: les processeurs modernes ont des caches. Ils ont plusieurs caches et ils ont appelé des "lignes de cache" pour le cache du premier niveau. Qu'est-ce que ça veut dire. L'accès à la mémoire est rapide, mais pas assez rapide. Les processeurs modernes sont beaucoup plus rapides. Donc, ils ont leurs caches sur puce qui accélèrent les choses. De plus, ils n'accumulent plus les emplacements de mémoire unique, mais ils remplissent une ligne de cache complète d'une excellente fetch. Cela est également pour la performance. Mais ce comportement donne toutes les avantages d'opérations qui traitent des données de manière linéairement. Lorsque vous accédez à toutes les premières colonnes d'affilée, alors la ligne suivante et ainsi de suite - vous travaillez linéairement en fait. Lorsque vous traitez pour la première fois toutes les premières colonnes de toutes les lignes, vous «sautez» dans la mémoire. Ainsi, vous forcez toujours une nouvelle ligne de cache à remplir, quelques octets peuvent être traités, alors la ligne de cache est éventuellement invalidée par votre prochain saut ....
Vous avez votre idée, Juergen. Merci
en.wikipedia.org/wiki/cas_latency