Discussion :

[hugobosscool26]

Salut à tous, je voulais savoir quels étaient la manière la plus rapide de parcourir un tableau avec une boucle for après avoir lu les tests de rapidité fait en C# (framework 3.0) sur le magazine developpez de ce mois ! J'ai donc fais ceci en c# :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
            int[] tab                   = new int[229948364];
            Random rand                 = new Random();
            Stopwatch stopWatchEn       = new Stopwatch();
            Stopwatch stopWatchTab      = new Stopwatch();
            Stopwatch stopWatchTabLen   = new Stopwatch();
            int lgTab           = 0;
 
            //Une première initialisation du tableau pour le charger en mémoire
            for (int j = 0; j < tab.Length; j++)
            {
                tab[j] = 0;
            }
 
            //Différentes boucles for pour tester
            for (int h = 0; h < 25; h++)
            {
                stopWatchTab.Start();
                lgTab = tab.Length;
                for (int j = 0; j < lgTab; j++)//Premier type de boucle : utilisation d'une variable chargé avec la taille du tableau
                {
                    tab[j] = 5;
                }
                stopWatchTab.Stop();
 
                stopWatchTabLen.Start();
                for (int i = 0; i < tab.Length; i++)//Second type : utilisation à chaque tour de la taille "calculée" du tableau
			    {
                    tab[i] = 5;
			    }
                stopWatchTabLen.Stop();
 
                stopWatchEn.Start();
                for (int j = 0; j < 229948364; j++)//Troisième type : utilisation directe d'un entier correspondant à la taille du tableau
                {
                    tab[j] = 5;
                }
                stopWatchEn.Stop();
            }
            stopWatchEn.Stop();
            stopWatchTab.Stop();
            stopWatchTabLen.Stop();
 
            //Résultats
            Console.WriteLine("Voici le résultat des tests :");
            Console.WriteLine("Entier : "    + stopWatchEn.Elapsed.Milliseconds);
            Console.WriteLine("Tab : "       + stopWatchTab.Elapsed.Milliseconds);
            Console.WriteLine("TabLength : " + stopWatchTabLen.Elapsed.Milliseconds);
        }

Voici le résultat de 6 tests réalisés :

Entier : 637
Tab : 131
TabLength : 230

Entier : 779
Tab : 361
TabLength : 715

Entier : 550
Tab : 66
TabLength : 991

Entier : 343
Tab : 989
TabLength : 3

Entier : 319
Tab : 39
TabLength : 20

Entier : 332
Tab : 32
TabLength : 11

Voici le résultat des 6 tests additionnés :

Entier : 2960
Tab : 1618
TabLeng : 1970

Pourquoi tant de différence entre les deux premiers ? (qui pour moi sont quasi pareils...)
Pourquoi le tablength est il aussi rapide ? (le framework recalcule t'il à chaque tour la taille ou est elle stockée ?)

Les sources sont disponibles ici pour tester : http://hugobosscool26.free.fr/TestBoucleFor.rar


Merci de vos réponses

PS : si vous avez des liens sur l'optimisation d'algorithme je suis preneur.
PS2 : y en a t'il qui ont VS2K8 (& framework 3.5) pour voir le code source de tab.Length ?

[SirJulio]

Pour le code source, comme toujours, Reflector est la (pour les malchanceux n'ayant pas VS2008 ou une express =p).

Pour la difference entre entier fixe et local, j'avouerai que je ne sais pas trop, par contre pour le tab.Length, la taille d'un tableau est une instruction IL (ldlen, l'appel à length d'un array etant un appel interne à la CLR (cf reflector)), et doit, donc, etre optimisé (bon ca n'avance pas beaucoup de dire ca, mais je pense que c'est la seule explication logique =p).

Par contre chose etonnante, le fait de compile avec optimize, rend les differences de performances bien moins marquées (le passage sur int fixe est amelioré, et le passage par Length est plus lent).

Bref, le mystere s'epaissit ! =)

Dans un usage pratique, le Length s'avere etre la meilleure solution, donc utilise le. =)

[hugobosscool26]

Ben oui tout ca est bizarre pour moi si d'autres pouvaient apporter leur culture !

[SaumonAgile]

Le JIT recherche (et optimise) les patterns dans le code correspondant à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (int j = 0; j < tab.Length; j++)

C'est la raison pour laquelle ces codes s'éxécutent plus rapidement. Je n'ai plus l'optimisation exacte, et ce ne serait pas vraiment utile ici. L'idée est de savoir que ce pattern est traité spécifiquement par le JIT.

[SaumonAgile]

Ah si j'ai retrouvé, l'optimisation est de supprimer des tests de bornes du tableau car on utilise directement Length. C'est la raison pour laquelle cette optimisation n'est pas appliquée quand la taille est stockée dans une variable annexe.

EDIT : Et pour ceux qui pourraient être intéressés, j'ai trouvé ceci :
http://weblogs.asp.net/justin_rogers.../26/97230.aspx

Plus général :
http://dotnet.sys-con.com/read/46342.htm

[hugobosscool26]

Merci SaumonAgile, je regarderais cela avec attention dès que j'ai le temps

[ced600]

Enfin moi ce qu'il m'étonne c'est que pour tablength on va de 3 à 991 ms.
Soit une moyenne qui devrait se trouver à 494 mais on observe 328.

Je pense que tes résultats ne peuvent être pris en compte que si tu fais une étude statistique sur une 100 de tests.

Par ce que là tu dois avoir un epsilon erreur trop grand pour que les données soit utilisable.

[Chubyone]

Tant qu'à faire : en principe un "down to 0" est plus rapide qu'un "up to x", tu pourrais tester s'il te plait?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
for( int i = tab.Lenght; i > 0; --i )
{ 
...
}

Merci

[hugobosscool26]

Fais toi plaisir Chubyone fais-le

[Chubyone]

Fais toi plaisir Chubyone fais-le

Ok j'avoue, Là... C'était total loose flemme... Mais j'avais du pain sur la planche, c'était juste au càs où tu passais par là, j'aurais eu réponse

Mais c'était aussi une simple remarque pour toi, qui pouvait t'amener à tester et donc choisir ensuite la meilleure technique

Bon aller ok, je prendrais tes exemples et je testerais ça demain, j'ai du temps maintenant...