Discussion :

[margagn]

Bonjour à tous !

J'ai une petite question. J'ai cherché dans le bouquin de Jeffrey Richter, mais je n'ai pas trouvé.

J'ai deux méthodes statistiques qui font toutes les deux la même chose, soit compter le nombre de bits à 1 dans un nombre. Il y a une version lente et l'autre optimisé. La version optimisée contient un tableau d'information précalculé. Ce tableau fait 256 octets en mémoire et je me demande tout simplement si .NET alloue cette mémoire à chaque appel de la méthode ou bien l'alloue une fois et joue avec...

J'ai tenté de la déclarer CONST ou READONLY, mais sans succès... J'ai tenté de découvrir la réponse à l'aide d'un profiler, mais je n'ai pas trouvé. En passant, si vous en avez un bon, laisser moi le savoir!

Merci !

Martin

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int NbBitsOn(int n)
{
    const int NbBits = sizeof(int) * 8;
    int nbBitsOn = 0;
 
    for (int i = 0; i < NbBits; i++)
    {
        nbBitsOn += n & 0x1;
        n >>= 1;
    }
 
    return nbBitsOn;
}

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
public static int NbBitsOnOpt(int n)
{
    byte[] PreComputedNbBitsOn = new byte[] {0, 1, 1, 2, 1, 2, 
        2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 
        3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 
        3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 
        6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 
        3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 
        4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 
        4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 
        4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 
        5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 
        4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 
        3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 
        6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 
        5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 
        7, 7, 8 };
    const int NbBits = sizeof(int);
    int nbBitsOn = 0;
 
    for (int i = 0; i < NbBits; i++)
    {
        nbBitsOn += PreComputedNbBitsOn[n & 0xFF];
        n >>= 8;
    }
 
    return nbBitsOn;
}

[Maniak]

je me demande tout simplement si .NET alloue cette mémoire à chaque appel de la méthode ou bien l'alloue une fois et joue avec...

À chaque appel.

Si tu veux qu'il ne le fasse qu'un fois, déclare ton tableau en static (static readonly tant qu'à faire) en dehors de la procédure.

Test simple pour voir les différences :

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
const int iterationCount = 10000000;
const int value = 255;
 
Stopwatch stopwatch = new Stopwatch();
 
stopwatch.Start();
for ( int i = 0 ; i < iterationCount ; ++i )
{
	NbBitsOn( value );
}
stopwatch.Stop();
Console.WriteLine( stopwatch.ElapsedMilliseconds );
stopwatch.Reset();
 
stopwatch.Start();
for ( int i = 0 ; i < iterationCount ; ++i )
{
	NbBitsOnOpt( value );
}
stopwatch.Stop();
Console.WriteLine( stopwatch.ElapsedMilliseconds );

Lance ça avec ta version actuelle, tu devrais voir qu'en debug, la version non-optimisée est bien plus rapide que l'autre, et qu'en release la version non-optimisée est lumineusement plus rapide que l'autre.

Mets ton tableau en static readonly, relance, et là tu devrais voir comme une légère inversion de la tendance.

(ou alors ma machine exécute ça très bizarrement :)

[margagn]

Salut Maniak,

Tu n'as pas de problème avec ta machine... Cependant, lorsque je déclare mon tableau global (static readonly) à la classe la version optimisé est vraiment rapide! Si j'utilise la StopWatch, sur ma machine, la version optimisée en mode DEBUG est 5 fois plus rapide que la non-optimisée.

Avec un tableau Static en Readonly
En Mode Debug
Non-Optimisé : 186ms
Optimisé : 35ms

En Mode Release
Non-Optimisé : 91ms
Optimisé : 19ms

Avec un tableau local à la méthode
En Mode Debug
Non-Optimisé : 186ms
Optimisé : 210ms

En Mode Release
Non-Optimisé : 90ms
Optimisé : 185ms

Définitivement, il y a une réallocation de la mémoire à tous les appels. Est-ce qu'il y a moyen de laisser mon tableau dans ma méthode tout en étant static? Ainsi peut-être éviter une réallocation... Le compilateur ne me laisse pas faire... :S

Merci !

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
            stopwatch.Start();
            for (int i = 0; i < 1000000; i++)
                NbBitsOn(i);
 
            stopwatch.Stop();
            Console.WriteLine(String.Format("Non-Optimisé : {0}ms", stopwatch.ElapsedMilliseconds));
            stopwatch.Reset();
 
            stopwatch.Start();
            for (int i = 0; i < 1000000; i++)
                NbBitsOnOpt(i);
            stopwatch.Stop();

[Maniak]

Définitivement, il y a une réallocation de la mémoire à tous les appels. Est-ce qu'il y a moyen de laisser mon tableau dans ma méthode tout en étant static? Ainsi peut-être éviter une réallocation... Le compilateur ne me laisse pas faire... :S

Nope. En static il sera au niveau de la classe. Il ne faut pas énerver le compilo :)

En même temps, si le but est d'optimiser la chose, qu'il soit au niveau de la classe ne devrait pas être trop gênant.