Pourquoi faire simple quand on peut faire compliqué ? Pour faire un article. Nous allons va voir ici au travers d’un exemple pourquoi le choix de la représentation d’une donnée, ici un pixel, peut influer sur les performances générales.

On se propose ici de parcourir différentes représentation d’une donnée destinée à contenir les composantes d’une couleur au format RGBA (tout ceci est évidemment applicable à d’autres formats). Il existe plusieurs façons de coder une couleur, on choisira celle utilisant 4 entiers compris entre 0 et 255 pour chaque composante : rouge, vert, bleu, et transparence. Le langage choisit est le C++.

Après avoir présenté le contexte d’utilisation, on passera en revue différentes représentations. Chacune d’entre elle sera commentée selon la clarté du code produit et la facilité de lecture/écriture qu’elle sous-tend. Et enfin au travers d’un exemple, on verra l’impact que cela peut avoir sur le temps d’exécution.

Contexte

On imagine que dans le cadre d’une application graphique, on dispose d’une classe image pour représenter… des images. Cette classe propose une méthode to_grayscale() permettant de convertir l’image en niveau de gris. Dans cette méthode, pour chaque pixel de l’image, on calcule sa valeur moyenne sur les 3 composantes rouge, verte, bleue. La couleur de chaque pixel est mise à jour avec la valeur obtenue.

class image
{
  public:

  // Constructor with image size as parameter
  image(size_t size);

  // Convert image to greyscale
  void to_greyscale();

  // Destructor
  ~image();

private:
  // Pixels array
  color* pixels;

  // Image size
  size_t size;
};

L’instanciation est l’appel de cette méthode sera réalisé dans main.cpp. On y reviendra plus tard.

Les représentations

On va parcourir 5 représentations possible d’un pixel :

• une structure “naïve”,
• un tableau d’entiers,
• un champ de 32 bits,
• une liste chaînée,
• une table de hachage.

La structure

Pour représenter chaque composante, la façon de faire qui vient en premier à l’esprit est certainement de créer une structure regroupant les composantes de la couleurs en utilisant un attribut par composante..

Définition du type

struct color
{
  // Constructor
  color() = default;

  // Convert image to greyscale
  void to_greyscale();

  // Color channels
  unsigned int red;
  unsigned int green;
  unsigned int blue;
  unsigned int alpha;
};

Pas grand chose dire sur la lisibilité du code. On voit clairement apparaître les données à manipuler.

Calcul du gris

Étant donnée la facilité d’accès à chaque composante, il n’y a pas de difficulté particulière pour calculer la valeur moyenne des composantes.

void color::to_greyscale()
{
  // Compute the mean color
  unsigned int grey = (red + green + blue) / 3;

  // Update all channels
  red = grey;
  green = grey;
  blue = grey;
}

Avec un tableau en plus

Dans cette situation, on remplace les 4 champs de la structure précédente par un tableau de 4 entiers.

Définition du type

struct color
{
  // Constructor
  color() = default;

  // Convert image to greyscale
  void to_greyscale();

  // Channels data
  unsigned char channels[NB_CHANNELS];
};

La compréhension est dans ce cas légérement moins immédiate que dans le cas précédent. On comprend bien que chaque couleur sera représenté à l’aide de 4 composantes, mais l’accés à chacune d’entre ne découle pas immédiatement de définition du type. En l’absence de davantage de commentaire ou de documentation, on ne sait par exemple pas dans quel ordre se trouve les composantes dans le tableau.

Calcul du gris

Une fois que l’ordre des couleurs dans le tableau est connu, l’accès à chacune d’entre elles ne pose pas de problème. L’utilisation des boucles, qui rend le calcul légérement plus opaque que dans le cas précédent, implique peut⁻être un très léger effort de compréhension.

void color::to_greyscale()
{
  unsigned int grey = 0;

  // Compute the mean color
  for(int i=0; i<NB_CHANNELS; i++)
    grey += (unsigned int)channels[i];

  grey /= NB_CHANNELS;

  // Update all channels
  for(int i=0; i<3; i++)
    channels[i] = grey;
}

Le champs de bit

Chaque composante pouvant être contenue sur 8 bits, il est possible d’utiliser un seul entier de 32 bits pour contenir les 4 composantes.

Définition du type

struct color
{
  // Constructor
  color() = default;

  // Convert image to greyscale
  void to_greyscale();

  // Channel value
  unsigned int channels;
};

Dans le cas du champs de bits on divise tout par 3 par rapport au cas précédent : l’occupation mémoire et la facilité d’accés à chaque champs. Là encore il faudrait ajouter au moins un commentaire pour préciser comment les composantes sont ordonnées. Ce code pourrait convenir dans le cas de systèmes avec de fortes contraintes sur l’occupation mémoire.

Calcul du gris

void color::to_greyscale()
{
  // Compute the mean color
  unsigned int grey =
    (((channels >> 24) & 0xFF) +
     ((channels >> 16) & 0xFF) +
     ((channels >> 8 ) & 0xFF)) / 3;

  // Zero all channels but alpha value
  channels &= 0x000000FF;

  // Update all channels
  channels |= (grey << 24); // red
  channels |= (grey << 16); // green
  channels |= (grey << 8);  //  blue
}

L’accés à chaque composante indépendemment des autres se fait par décalage/masquage de bits. Le principal avantage de ce type est la possibilité d’utiliser la notation héxadécimale pour assigner une couleur à un pixel. Si on souhaite un pixel jaune, on peut écrire :

color pixel;
pixel.channels = 0xFFFF0000;

Liste chaînée

Ensuite on peut imaginer stocker les différentes composantes au sein d’une liste chaînée. Le rouge référence le bleu, qui référence le vert, qui référence la valeur alpha de transparence.

Définition du type

// Linked list element definition
struct channel
{
  // Channel value
  unsigned char value;

  // Link to next channel
  struct channel* next_channel;
};


struct color
{
  // Constructor
  color();

  // Convert image to greyscale
  void to_greyscale();

  // Destructor
  ~color();

  // Channels data
  channel red;  
};

Il n’apparaît pas au premier coup d’oeil que l’on s’apprête à manipuler une couleur à 4 composantes. Contrairement aux cas vu précédemment, une phase d’initialisation est nécessaire. Elle permet d’allouer les 3 derniers éléments (vert, bleu, alpha).

color::color()
{
  // Initialize red channel
  red.value = 0;

  // Initialize green channel
  red.next_channel = new channel();
  red.next_channel->value = 0;

  // Initialize blue channel
  red.next_channel->next_channel = new channel();
  red.next_channel->next_channel->value = 0;

  // Initialize alpha channel
  red.next_channel->next_channel->next_channel = new channel();
  red.next_channel->next_channel->next_channel->value = 0;
}

Au delà d’une compréhension qui cette fois-ci n’est pas immédiate, ce code expose à des risques d’une mauvaise gestion de la mémoire, et rend plus difficile le déboggage.

Calcul du gris

void color::to_greyscale()
{
  // Compute the mean color
  unsigned int grey = red.value;
  grey += red.next_channel->value;
  grey += red.next_channel->next_channel->value;
  grey /= 3;

  // Update all channels
  red.value = grey;
  red.next_channel->value = grey;
  red.next_channel->next_channel->value = grey;
}

La mise à jour d’un pixel se fait via le déréférencement successif des valeurs référencées par chaque composante.

Table de hachage

Définition du type

struct color
{
  // Constructor
  color();

  // Convert image to greyscale
  void to_greyscale();

  // Channels data
  std::map<char, unsigned int> channels;
};

Question lisibilité on se trouve à peu de chose prés au même niveau que dans le cas du tableau d’entiers. Bienqu’il soit possible d’utiliser une implémentation indépendante, l’utilisation de la librairie standard C++ rendra plus difficile l’intégration de ce code dans le cas d’un programme embarqué par exemple.

Calcul du gris

void color::to_greyscale()
{
  // Compute the mean color
  unsigned int grey =
    (channels['r'] + channels['g'] + channels['b']) / 3;

  // Update all channels
  channels['r'] = grey;
  channels['g'] = grey;
  channels['b'] = grey;
}

En ce qui concerne les calculs, on regagne en facilité (pas en compléxité) d’accés en lecture/écriture de chaque composante.

Les performances

Le calcul des performance a été réalisé de la façon suivante : pour chaque type, une image de 1024x1024 pixels a été créée. La méthode to_greyscale() a été appelée 50 fois. Chaque appel de la méthode a été chronométré (en utilisant les fonctions dans <chrono>). Le temps indiqué est la moyenne des temps d’exécution sur les 50 appels.

Compilateur et machine

Le compilateur utilisé est GCC.

~$: gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0

Les options de compilation utilisées sont -O2 -pedantic -Wall. Le code a tourné sur un processeur AMD E-450, 1.6 GHz.

Résultats

Le code est disponible ici sur le dépot git.