Frédéric Mélantois
Manipulation d'images en C#, vers la performance
Nous chercherons à augmenter la performance de nos traitements via quelques petites « recettes »
Par Frédéric Mélantois publié le 01/02/2007 à 10:11, lu 8087 fois, 5 pages
commentaire(s) 2 commentaire(s) tag(s)Tags: C#, Framework .NET
 2 | Usage des tableaux et performance
Usage des tableaux et performance
Le petit problème que je vous avais posé lors du précédent article était le suivant : comment améliorer de 25% le temps d'exécution du code ci-dessous :

int width = bitmap.Width;

int height = bitmap.Height;

Bitmap bitmap1Bit = new Bitmap(width, height, PixelFormat.Format1bppIndexed);

 

//le pattern a appliquer sur des niveaux de gris de 64

byte[][] pattern = new byte[][]{ new byte[]{0,32,8,40,34,2,10,42},

                                new byte[]{48,16,56,24,50,18,58,26},

                                new byte[]{12,44,4,36,14,46,6,38},

                                new byte[]{60,28,52,20,62,30,54,22},

                                new byte[]{3,35,11,43,1,33,9,41},

                                new byte[]{51,19,59,27,49,17,57,25},

                                new byte[]{15,47,7,39,13,45,5,37},

                                new byte[]{63,31,55,23,61,29,53,21}};

 

//tables de precalculs des multiplications pour le calcul du niveau de gris

int[] multiBleu = new int[256];

int[] multiVert = new int[256];

int[] multiRouge = new int[256];

for (int i = 0; i < 256; i++)

{

    multiBleu[i] = 76 * i;

    multiVert[i] = 151 * i;

    multiRouge[i] = 28 * i;

}

 

unsafe

{

    BitmapData bmpDataOld = bitmap.LockBits(new Rectangle(0,

    0, width, height), ImageLockMode.ReadWrite, PixelFormat.Format32bppArgb);

    BitmapData bmpDataNew = bitmap1Bit.LockBits(new Rectangle(0, 0,

    width, height), ImageLockMode.ReadWrite, PixelFormat.Format1bppIndexed);

 

    byte* oldPixel = (byte*)(void*)bmpDataOld.Scan0;

    byte* newPixel = (byte*)(void*)bmpDataNew.Scan0;

 

    //l'offset de l'image 1 bit

    int offset = bmpDataNew.Stride - (width / 8);

 

    byte pixel;//Niveau de gris

    int newPix = 0;//ensemble de 8 pixels

 

    for (int y = 0; y < height; y++)

    {

        for (int x = 1; x <= width; x++)

        {

            //A partir des composantes du pixel

            //de l'image 32 bits, on determine

            //le niveau de gris

 

            pixel = (byte)((multiBleu[oldPixel[0]] + multiVert[oldPixel[1]]

                + multiRouge[oldPixel[2]]) >> 8);

 

            //on compare le pixel (reduit  64 niveaux)

            //au pattern (en fonction de sa position

            //par rapport  l'image)

            if ((pixel >> 2) > pattern[x & 7][y & 7])

                //on allume le pixel (Bit=1)

                //dans le byte

                newPix = newPix | (1 << (7 - (x % 8)));

 

            if (x % 8 == 0)

            {

                //quand on a rempli 8 bits

                //on ecrit le byte dans l'image

                newPixel[0] = (byte)newPix;

 

                //on avance le pointeur

                newPixel++;

 

                //on teint tous les pixels

                //pour le nouveau cycle de 8 bits

                newPix = 0;

            }

            oldPixel += 4;

        }

        newPixel += offset;

    }

    bitmap.UnlockBits(bmpDataOld);

    bitmap1Bit.UnlockBits(bmpDataNew);

}

Quand on observe ce code, on constate la présence d'un tableau de tableaux. En cela, nous avons respecté les recommandations faîtes par l'équipe de la CLR (Common Language Runtime) puisque nous n'avons pas fait appel aux tableaux multidimensionnels qui sont sensiblement plus lents d'accès que les tableaux imbriqués.
Comment montrer d'ailleurs cette affirmation ? Soit la méthode suivante :

static byte[][] TabloImbriques()

{

    byte[][] tab = new byte [16][];

    tab[0][0] = 1;

    return tab;

}

dont le code IL correspondant est le suivant :

.method private hidebysig static uint8[][]

        TabloImbriques() cil managed

{

  // Code size       21 (0x15)

  .maxstack  3

  .locals init ([0] uint8[][] tab,

           [1] uint8[][] CS$1$0000)

  IL_0000:  nop

  IL_0001:  ldc.i4.s   16

  IL_0003:  newarr    uint8[]

  IL_0008:  stloc.0

  IL_0009:  ldloc.0

  IL_000a:  ldc.i4.0

  IL_000b:  ldelem.ref

  IL_000c:  ldc.i4.0

  IL_000d:  ldc.i4.1

  IL_000e:  stelem.i1

  IL_000f:  ldloc.0

  IL_0010:  stloc.1

  IL_0011:  br.s       IL_0013

  IL_0013:  ldloc.1

  IL_0014:  ret

} // end of method Program::TabloImbriques

Soit la méthode suivante utilisant un tableau multidimensionnel :

static byte[,] TabloMultiDimensions()

{

    byte[,] tab = new byte[16,16];

    tab[0, 0] = 1;

    return tab;

}

dont le code IL correspondant est le suivant :

.method private hidebysig static uint8[0...,0...]

        TabloMultiDimensions() cil managed

{

  // Code size       26 (0x1a)

  .maxstack  4

  .locals init ([0] uint8[0...,0...] tab,

           [1] uint8[0...,0...] CS$1$0000)

  IL_0000:  nop

  IL_0001:  ldc.i4.s   16

  IL_0003:  ldc.i4.s   16

  IL_0005:  newobj    instance void uint8[0...,0...]::.ctor(int32,

                                                            int32)

  IL_000a:  stloc.0

  IL_000b:  ldloc.0

  IL_000c:  ldc.i4.0

  IL_000d:  ldc.i4.0

  IL_000e:  ldc.i4.1

  IL_000f:  call       instance void uint8[0...,0...]::Set(int32,

                                                           int32,

                                                           uint8)

  IL_0014:  ldloc.0

  IL_0015:  stloc.1

  IL_0016:  br.s       IL_0018

  IL_0018:  ldloc.1

  IL_0019:  ret

} // end of method Program::TabloMultiDimensions

Il n'est alors pas nécessaire de beaucoup maîtriser l'IL (Intermediate Language) pour comprendre que pour manipuler les tableaux multidimensionnels, il est nécessaire de faire appel un constructeur (Ctor) pour initialiser un objet (instruction newobj). Pour initialiser les entrées de ce tableau, on fera appel à la méthode « Set » de cet objet. Alors que pour les tableaux imbriqués de type valeur, des instuctions IL spécifiques permettent de rapidement créer un objet tableau sans nécessité de faire appel à un constructeur. On peut donc en conclure que la création de tableaux multidimensionnels est donc beaucoup plus coûteux que la création de tableaux imbriqués. Tous les tests de performance que vous pourrez effectuer confirmeront cette règle.
Nous avons donc bien fait d'utiliser les tableaux imbriqués dans notre code. Pourtant, nous avons fait un mauvais usage des tableaux. Si vous observez bien tous les tableaux, ceux-ci ont une même taille : 8 entrées. Connaissant cette longueur répétitive, il apparaît plus judicieux de ne créer qu'un seul tableau de taille 64 au lieu des tableaux imbriqués. Nous gagnerons de façon évidente en performance. En effet, l'appel d'une entrée de ce tableau dans la boucle de parcours des pixels représente beaucoup moins d'instructions que d'appeler une référence à un tableau dans notre tableau initial pour obtenir la valeur d'une entrée précise de celui-ci . Cette optimisation n'est pas à négliger. Vous pouvez la reproduire dans le code VB.NET fourni dans le précédent article. Voici les modifications à apporter en C# :

//le pattern a appliquer sur des niveaux de gris de 64

byte[] pattern = new byte[64]{0,32,8,40,34,2,10,42,

                            48,16,56,24,50,18,58,26,

                            12,44,4,36,14,46,6,38,

                            60,28,52,20,62,30,54,22,

                            3,35,11,43,1,33,9,41,

                            51,19,59,27,49,17,57,25,

                            15,47,7,39,13,45,5,37,

                            63,31,55,23,61,29,53,21};

Une fois ces modifications effectuées, il est nécessaire d'apporter la correction suivante à la condition :

if ((pixel >> 2) > pattern[(x & 7) * 8 + (y & 7)])

                        //Au lieu de :

                        //if ((pixel >> 2) > pattern[x & 7][y & 7])

Vous aurez certainement remarqué que nous multiplions par 8. Si vous avez bien retenu ce que je vous avez dit lors de mon précédent article, vous aurez la reflexion suivante : « il vient d'ajouter une opération de multiplication, ce qui réprésente un coût non négligeable ». Vous aurez en partie raison. Si vous faîtes une bonne observation, vous constaterez que nous multiplions ici par 8, ce qui devrait représenter un décalage de bits vers la gauche de 3 à l'exécution de ce code. Le compilateur c# est –il capable de réaliser une telle optimisation, et donc de produire un code IL en conséquence ? Pour obtenir la réponse à cette question, créons les méthodes suivantes :

static int Multiplie(int x)

{

    return x * 8;

}

 

static int Decale(int x)

{

    return x << 3;

}

Observons maintenant le code IL généré grâce à l'utilitaire ILDASM fourni avec le Framework SDK. Cet utilitaire « désassemble » le byte code contenu dans l'assembly et fournit le code IL, ce dernier nous paraissant évidemment bien plus « intelligible » qu'une succession d'octets dont les valeurs déterminent les instructions à exécuter. Vous pouvez constater grâce à cet utilitaire que la multiplication n'a pas été convertie en une opération de décalage puisque le code IL contient l'instruction « mul ». Puisque le compilateur c# ne réalise pas d'optimisation de cette ordre sur le code IL, serait-il possible que le JIT fasse cette optimisation à l'exécution ? La réponse est évidemment oui :

00000026 8B C7            mov        eax,edi

00000028 C1 E0 03        shl        eax,3

0000002b 8B F0            mov        esi,eax

la lecture du code natif montre que l'optimisation est effectuée puisque l'instruction « Shr » le confirme. Vous pouvez très simplement le vérifier en exécutant la commande CorDbg fournie avec le Framework SDK. Une exécution pas à pas des instructions permet d'observer le code natif produit lors de l'exécution. Je vous laisse essayer les différentes commandes de l'utilitaire fort utile« CorDbg ».
Nous pouvons retenir que les décalages bit à bit coûtent beaucoup moins que de réaliser des multiplications ou des divisions. Lorsqu'on a un nombre de multiplications important (dont le résultat doit être un nombre entier) par un nombre avec deux chiffres après la virgule, on a tout intérêt à multiplier ce dernier par 128 pour en faire un nombre entier sans virgule flottante. Il suffit alors de réaliser nos opérations de calculs puis de diviser à nouveau par 128 (division qui sera traduit par le compilateur JIT par un décalage de bits). Il ne faut surtout pas négliger ce genre d'optimisation, elles font gagner énormément de temps. A titre d'illustration, c'est l'optimisation qui a été effectuée pour les tables de précalculs concernant les multiplications intervenant dans le calcul du niveau de gris (voir code plus haut). Concernant ce code, nous effectuons une multiplication par 256 (décalage de bits vers la gauche de 8), puis une fois tous les calculs effectués, nous divisons par 256 (décalage de bits vers la droite de 8).
 
» Démarrer une discussion
 
Discussion démarée par Frédéric Mélantois le 07/05/2007 à 11:28, 1 commentaire(s).
Discussion démarée par Frédéric Mélantois le 07/05/2007 à 11:21, 1 commentaire(s).