Tableaux rectangulaires .NET: comment accéder en boucle?
https://stackoverflow.com/questions/405810
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
En gros, vous avez deux moyens de le faire:
for (int x = 0; x < UPPER_X; x++)
for (int y = 0; y < UPPER_Y; y++)
{
arr1[x, y] = get_value();
arr2[y, x] = get_value();
}
La seule différence est la variable à modifier dans la boucle interne: première ou seconde. J'ai entendu dire que les résultats différaient d'une langue à l'autre.
Quel est le bon ordre pour .NET?
La solution
La raison pour laquelle l'un est plus rapide que l'autre est liée au cache du processeur et à la manière dont les données sont disposées en mémoire.
Il existe deux manières normales de stocker les données bidimensionnelles dans un espace adresse unidimensionnel. Soit vous pouvez stocker toutes les données de la première ligne, puis de la deuxième ligne, etc. (alias ordre majeur de ligne ), ou vous pouvez le faire en colonnes (aka < a href = "http://en.wikipedia.org/wiki/Row-major_order#Column-major_order" rel = "nofollow noreferrer"> ordre majeur de la colonne ). Vous trouverez ci-dessous les emplacements mémoire d’un tableau 3x3 pour ces deux options.
Lignes:
1 2 3
4 5 6
7 8 9
Colonnes:
1 4 7
2 5 8
3 6 9
Lorsque vous accédez à un emplacement de mémoire, une ligne de cache complète (pouvant aller de 8 à 512 octets, selon Wikipedia) est chargée dans le cache. Donc, si vous accédez au prochain emplacement mémoire, il sera déjà dans le cache. Ainsi, il peut être beaucoup plus rapide d’accéder séquentiellement à la mémoire que de se déplacer dans l’espace adresse. Ainsi, avec de grands tableaux bidimensionnels, il peut y avoir une différence de vitesse importante entre le choix de lignes ou de colonnes comme variable de boucle interne.
Autres conseils
Vous devez évaluer votre situation particulière pour en être sûr.
Vous penseriez qu'il n'y aurait aucune différence pour les tableaux rectangulaires (c'est-à-dire la mémoire allouée de manière contiguë), MAIS en fonction de ceci Article MSDN : il y a une différence:
Vous pouvez obtenir des résultats encore meilleurs en convertir un tableau multidimensionnel dans un tableau unidimensionnel. Si ça ne vous dérange pas la syntaxe, cela peut être banal; il suffit d'utiliser un index en tant que décalage. Par exemple, le suivant déclare un tableau unidimensionnel à être utilisé comme un tableau à deux dimensions:
double[] myArray = new double[ROW_DIM * COLUMN_DIM];
Pour indexer les éléments de cette tableau, utilisez le décalage suivant:
myArray[row * COLUMN_DIM + column];
Ce sera sans doute plus rapide que un équivalent dentelé ou rectangulaire tableau.
J'ai donc fait le point de repère et les résultats sont que l'accès à arr1 est trois fois plus rapide.
Très intéressant, je n’ai jamais cessé de penser que la différence peut être aussi énorme en accédant simplement aux index de tableaux "de manière non séquentielle". J'ai essayé moi-même et j'ai également constaté que le code suivant avait la deuxième boucle prenant entre 2 et 3 fois plus longtemps:
// Hmmm, how to insert blank lines in the code formatter???
static void Main(string[] args)
{
Stopwatch timer = new Stopwatch();
int arraySize = 10000;
// First array, access X by Y
int[,] xbyy = new int[arraySize, arraySize];
timer.Start();
for (int x = 0; x < arraySize; x++)
for (int y = 0; y < arraySize; y++)
{
xbyy[x, y] = 15;
}
timer.Stop();
TimeSpan duration = timer.Elapsed;
string realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
duration.Minutes, duration.Seconds, duration.Milliseconds);
Console.WriteLine("X by Y took " + realTimeFormat);
// Seecond array, access Y by X
int[,] ybyx = new int[arraySize, arraySize];
timer.Start();
for (int x = 0; x < arraySize; x++)
for (int y = 0; y < arraySize; y++)
{
ybyx[y, x] = 15;
}
timer.Stop();
duration = timer.Elapsed;
realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
duration.Minutes, duration.Seconds, duration.Milliseconds);
Console.WriteLine("Y by X took " + realTimeFormat);
Console.ReadLine();
}
Pour rester bref, voici les extraits de code IL émis pour la boucle X par Y et la boucle Y par X.
Code initial avant la mise en boucle,
.method private hidebysig static void Main(string[] args) cil managed
{
.entrypoint
// Code size 290 (0x122)
.maxstack 4
.locals init ([0] class [System]System.Diagnostics.Stopwatch timer,
[1] int32 arraySize,
[2] int32[0...,0...] xbyy,
[3] int32 x,
[4] int32 y,
[5] valuetype [mscorlib]System.TimeSpan duration,
[6] string realTimeFormat,
[7] int32[0...,0...] ybyx,
[8] int32 V_8,
[9] int32 V_9)
IL_0000: newobj instance void [System]System.Diagnostics.Stopwatch::.ctor()
IL_0005: stloc.0
IL_0006: ldc.i4 0x2710
IL_000b: stloc.1
boucle X par Y
IL_000c: ldloc.1
IL_000d: ldloc.1
IL_000e: newobj instance void int32[0...,0...]::.ctor(int32,
int32)
IL_0013: stloc.2
IL_0014: ldloc.0
IL_0015: callvirt instance void [System]System.Diagnostics.Stopwatch::Start()
IL_001a: ldc.i4.0
IL_001b: stloc.3
IL_001c: br.s IL_003d
IL_001e: ldc.i4.0
IL_001f: stloc.s y
IL_0021: br.s IL_0034
IL_0023: ldloc.2
IL_0024: ldloc.3
IL_0025: ldloc.s y
IL_0027: ldc.i4.s 15
IL_0029: call instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_002e: ldloc.s y
IL_0030: ldc.i4.1
IL_0031: add
IL_0032: stloc.s y
IL_0034: ldloc.s y
IL_0036: ldloc.1
IL_0037: blt.s IL_0023
IL_0039: ldloc.3
IL_003a: ldc.i4.1
IL_003b: add
IL_003c: stloc.3
IL_003d: ldloc.3
IL_003e: ldloc.1
IL_003f: blt.s IL_001e
IL_0041: ldloc.0
boucle Y par X
IL_0090: ldloc.1
IL_0091: ldloc.1
IL_0092: newobj instance void int32[0...,0...]::.ctor(int32,
int32)
IL_0097: stloc.s ybyx
IL_0099: ldloc.0
IL_009a: callvirt instance void [System]System.Diagnostics.Stopwatch::Start()
IL_009f: ldc.i4.0
IL_00a0: stloc.s V_8
IL_00a2: br.s IL_00c7
IL_00a4: ldc.i4.0
IL_00a5: stloc.s V_9
IL_00a7: br.s IL_00bc
IL_00a9: ldloc.s ybyx
IL_00ab: ldloc.s V_9
IL_00ad: ldloc.s V_8
IL_00af: ldc.i4.s 15
IL_00b1: call instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_00b6: ldloc.s V_9
IL_00b8: ldc.i4.1
IL_00b9: add
IL_00ba: stloc.s V_9
IL_00bc: ldloc.s V_9
IL_00be: ldloc.1
IL_00bf: blt.s IL_00a9
IL_00c1: ldloc.s V_8
IL_00c3: ldc.i4.1
IL_00c4: add
IL_00c5: stloc.s V_8
IL_00c7: ldloc.s V_8
IL_00c9: ldloc.1
IL_00ca: blt.s IL_00a4
IL_00cc: ldloc.0
Le flux logique IL est quelque peu similaire. La principale différence que je peux observer est que la première boucle parvient à utiliser stloc et ldloc pour les positions 2 et 3 pour le premier tableau et la variable d'index X. Au moment de passer à la deuxième boucle, il avait utilisé le maxstack et avait donc utilisé les instructions stloc.s et ldloc.s. J’estime que c’est la différence entre le référencement des variables sur la pile et celui sur le tas et la contribution au ralentissement des performances.
Maintenant, si vous intervertissez l'ordre dans lequel les boucles sont testées, afin que la boucle Y par X soit exécutée en premier pour accéder aux références de pile, vous verrez que les durées de synchronisation sont inversées.
UPDATE: J'avais tort de faire référence à des adresses de pile ou de tas. Il semble simplement que les quatre premières variables d’une méthode soient plus efficaces pour faire référence aux opcodes dédiés stloc.0, 1, 3, 4 et ldloc.0, 1, 3, 4.
http://weblogs.asp.net/mnolton /archive/2004/01/09/48992.aspx
