Greg's Devblog Par un développeur, pour les développeurs

Pixel plot, optimisation 2

Après un premier billet sur le pixel plot en alpha un poil technique, je reviens pour un billet un peu plus simple mais toujours très efficace. Cette optimisation peut, de plus, être combinée à la précédente pour améliorer d'autant plus la vitesse d'affichage.

Version naïve

Voici une boucle d'affichage, version "naïve" :

for (int y=0; y<height; y++){
	for (int x=0; x<width; x++){
		if (alpha[x+y*width] == MAX_ALPHA){
			dst[dest_x + x + (dest_y + y) * dest_width] = color[x + y*width];
		} else if (alpha[x+y*width] > 0) {
			idem mais avec le code alpha
		}
	}
}	

J'ai vraiment mis la version de base, sans utiliser de pointeurs ni rien. Idéalement il faudrait calculer les pointeurs de la source et de la destination juste avant la ligne 2, et ensuite faire du pointer++, mais ce n'est pas le sujet de ce billet.

On voit ici plusieurs qu'afin de ne pas utiliser le code alpha pour rien (car il reste lent pour rien quand on n'en a pas besoin), on a en fait 3 cas de figures :

1. Pixel plein, on affiche bêtement
2. Pixel avec alpha, on affiche avec le code lent
3. Alpha = 0, on ne fait rien

Si on a une image avec beaucoup de vide, on va passer beaucoup de temps à boucler et faire des if pour rien. Si on a une image qui ne contient que des pixels pleins, pareil, la perte de temps est monstrueuse. Il faudrait donc pouvoir améliorer ce comportement.

RLE power

En fait, ce dont on aurait besoin pour améliorer la vitesse, c'est de ne pas vérifier systématiquement le niveau d'alpha des pixels à afficher. Si on savait à l'avance, autant que possible, ce qu'on doit faire, alors on peut gagner pas mal de temps.

Je trouve qu'il est important d'avoir de bonnes notions des algos qui existent dans un peu tous les domaines, car in fine on ne sait jamais où et quand des versions analogues pourraient servir. Ici on va reprendre le principe de la compression RLE, et la mettre à profit pour l'affichage ^^

La compression RLE (Run Length Encoding) est une des compression les plus basiques qui soit, très facile à comprendre : en gros, l'idée est que si dans une image on a souvent les mêmes pixels à la suite, alors plutôt que d'écrire chaque pixel dans le fichier, on pourrait écrire un pixel, puis le nombre de fois qu'il apparait. Ca marche particulièrement bien pour des images avec peu de couleurs (palettes 2, 4, ou 16 couleurs par exemple), moins bien pour le reste puisqu'on a beaucoup plus de variations, mais le débat n'est pas là ^^

Ici, en plus de notre tableau avec les couleurs et de celui avec l'alpha (qui peuvent être en fait un seul et même tableau), on va donc se rajouter un tableau de type RLE. Ce qu'il va contenir, c'est le nombre de pixels à la suite qui ont le même type d'alpha. Par type, j'entends les 3 catégories qu'on a énoncé précédemment : pixel opaque, pixel semi-transparent, ou pixel invisible.

Grâce à ça, on fait un premier test pour savoir le type de pixel qu'on va afficher, mais au lieu d'en afficher un seul, on va introduire une nouvelle boucle dans le if qui va permettre d'afficher très rapidement tous les pixels du même type.

1. Pour les pixels opaque, on peut même envisager de faire un memcpy si on a suffisamment de pixels opaques à la suite. Le code devient alors super simple et rapide.
2. Pour les pixels semi-transparents, pas de miracle, mais on économisera pour chaque pixel le if...
3. Pour les pixels invisible/transparents, là c'est génial, car on peut directement tous les sauter d'un coup. Et là, quand on a des images avec pas mal de vide (des icones par exemple), le gain est assez monstrueux.

Je ne poste pas de code (sauf si vous me le demandez) pour illustrer ça, car il y a pas mal de façon de faire et que pour que ce soit beau et rapide il faudrait passer par des pointeurs dans tous les sens (contrairement à la version naïve).

Discussion

Cette optimisation est-elle toujours efficace, ou alors peut-elle être mise à défaut ? De façon assez logique, on voit que si dans une image on a une alternance très rapide du type de niveau d'alpha (par exemple un damier de pixels), alors on perd pas mal de temps : au lieu d'avoir juste 1 if dans la boucle, on va avoir un if plus une boucle dedans (qui n'aura aucun intérêt pour 1 pixel), et du coup on y perd un peu. Ca reste relativement rare, mais ça pourrait arriver si on a énormément de toutes petites images à afficher. Dès que les images sont de taille correcte (plus que 8x8, en gros), alors le gain l'emporte largement.

Le gain est aussi d'autant plus important que le nombre de pixels semi-transparents est faible. Ceci est du au fait que le gain est plus massif pour les pixels opaque et transparents que pour les semi-transparents. Mais même avec beaucoup de pixels semi-transparents, on y gagne quand même.

Quant à comment implémenter le calcul du RLE, il y a une façon relativement simple et efficace de le faire : quand on précalcule les niveaux d'alpha, on va partir pour chaque ligne de la droite plutôt que de la gauche. On met la valeur du RLE à 1. Et là, l'algo est tout con :

• Si le pixel a le même type d'alpha, on incrémente la valeur du RLE et on la stocke. Si on ne prend que 8 octets pour stocker le RLE d'un pixel, alors il faut vérifier qu'on ne dépasse pas 255 ^^ (sinon on bloque à 255)
• Si le pixel a une valeur différente, on met à 1

Pas grand chose de plus à dire. Ah si, il faut préciser qu'on perd quand même encore quelques octets par image (selon la taille de l'image), donc c'est un choix à faire entre utilisation CPU et utilisation de RAM.

On peut en fait optimiser la place que ça prend en RAM (c'est le choix que j'avais fait sur PocketPC), mais ce n'est pas gratuit : au lieu de stocker la valeur de RLE pour chaque pixel, on peut se contenter de les stocker uniquement pour le premier pixel d'un type d'alpha donné, comme dans la compression RLE d'origine. Le gain de place peut être important, mais les conséquences sur le code sont assez importantes : si on a une image partiellement hors de l'écran, on ne va pas pouvoir clipper directement en lisant le bon pixel, et on va devoir en fait faire comme si on partait du début de l'image, dérouler le RLE, mais sans faire l'affichage. Sur de grosses images partiellement hors de l'écran on va perdre pas mal de temps comme ça, et la routine d'affichage devient inutilement complexe (pour gérer la portion hors de l'écran), alors qu'avec la version décrite ci-dessus le code reste très simple et compact.

L'idée derrière cette optimisation, comme beaucoup d'autre, est au final de précalculer un maximum de choses au chargement, de stocker des informations sur ces précalcule, pour les réutiliser intelligemment par la suite.