Algorithme du lièvre et de la tortue
En cours il y a quelques temps un prof nous a demandé si on savait comment détecter des cycles en utilisant un espace mémoire en O(1). Pour illustrer pourquoi on peut avoir envie de ça, imaginons que l'on cherche à trouver 2 valeurs qui vont avoir le même hashé (avec la méthode de votre choix).
On peut alors s'amuser à prendre 1 valeur au hasard, trouver son hashé, et ensuite utiliser cette nouvelle valeur comme valeur de départ, prendre son haché, etc... Là, on est sûr de trouver, au bout d'un temps potentiellement très long, une boucle (ou un cycle), comme sur l'image suivante (prise de wikipedia) :
La façon naïve de faire va être de stocker chacune des valeurs, et de comparer la nouvelle valeur avec toutes les valeurs précédentes. Si on veut éviter d'exploser en temps, on peut utiliser des énormes tables de hash. Sauf que voilà, il faut stocker toutes les valeurs, et on est donc en O(n) pour l'espace mémoire, n étant le nombre de valeurs avant qu'on ne cycle.
Je repose donc la question : comment peut-on effectuer le même traitement en O(1) pour l'espace mémoire ?
Pas forcément intuitive, l'algorithme est au final particulièrement simple et élégant. Il a été défini par Floyd, et on le connait sous le nom d'algorithme du lièvre et de la tortue.
On peut écrire les opérations que l'on fait pour avancer sur la chaine sous la forme ai+1 = f(ai), f étant la fonction qu'on utilise (fonction de hash dans l'exemple que j'ai donné). Mais au lieu d'itérer une seule fois sur la chaine, on va en fait lancer 2 itérations en parallèle :
- La tortue avance lentement, donc à chaque itération elle fait ai+1 = f(ai)
- Le lièvre est très rapide, il va donc avancer 2 par 2, avec bi+1 = f(f(b1))
De façon évidente, le lièvre va arriver dans le cycle avant la tortue, et va se retrouver à tourner dedans en attendant que la tortue n'arrive... Une fois que la tortue est dans le cycle, on a la garantie qu'elle va arriver à la même valeur que le lièvre au bout d'un temps donné, puisque qu'en fait le lièvre rattrape la tortue d'1 étape à chaque itération. Quel que soit l'écart entre les 2, une fois que la tortue arrive dans le cycle le lièvre sera sur le même noeud en au plus L itérations (L étant la taille du cycle).
Et du coup, on n'a besoin d'aucune mémoire supplémentaire pour savoir où est le cycle !
Le pseudo-code, pris de wikipedia, est le suivant :
mu := 0;
répéter
mu := mu+1;
x := f(x);
y := f(f(y));
tant que x <> y
On peut difficilement faire plus simple...
Le seul défaut de cette méthode est la complexité : on reste en O(n), mais on va tout de même appeler 3*n fois la fonction f. Mais cette constante reste relativement faible par rapport au gain en mémoire (on passe de O(n) à O(1)...).
Plus d'informations sur wikipedia
Mandelbrot en parallèle
Aujourd'hui à la fac, c'était programmation parallèle d'un Mandelbrot. C'est du fractal, et ça se prête très bien à de la programmation parallèle, puisqu'en fait on itère N fois sur chaque pixel, indépendamment des voisins, pour savoir si on doit l'afficher ou pas (et avec quelle couleur).
La conception du code s'est faite en plusieurs phases :
1. Version séquentielle
Exécution du code en version séquentielle, histoire de voir le temps que ça prend et d'avoir un résultat qui puisse servir d'étalon... Résultat : entre 7 et 8 secondes pour générer l'image avec les paramètres par défaut.
2. Version parallèle, statique.
Réalisation d'une version pouvant tourner en parallèle avec N processus. La méthode est relativement simple et naïve : au démarrage de chaque processus, on récupère le numéro du processus (de 0 à N-1), ainsi que le nombre total de processus lancés. A partir de là, on découpe l'image en N bandes (on garde toute la largeur, on découpe en hauteur), chaque processus calcule sa portion, puis tout le monde envoie la portion calculée au processus 0, qui enregistre l'image finale (et affiche le temps total).
Et là, surprise, même avec 8 ou 10 processus, le gain est assez faible : on tourne en 2.5 à 3.5 secondes, soit à peine 2 à 3 fois plus vite (alors qu'on a pourtant 4 à 5 fois plus de puissance, normalement !).
La raison est en fait rapidement trouvée : les lignes du milieu mettent beaucoup plus de temps à calculer que les lignes aux extrémités (en fait tout ce qui est noir sur l'image a mis longtemps à être calculé). Du coup, les processus qui se tapent les bords en haut et en bas finissent super vite (en 0.05 secondes !), alors que les processus qui ont le milieu à calculer mettent plus de 2 secondes... C'est du beau gachi de puissance, il convient donc de concevoir un truc un peu plus dynamique qui puisse répartir au mieux la charge...
3. Version parallèle, mais dynamique !
La dernière version à être réalisée va donc avoir une approche beaucoup moins statique : le processus 0 ne va rien calculer, mais va en fait servir de chef d'orchestre, et va dire aux autres quoi calculer. A chaque fois qu'un processus a fini de calculer une portion de l'image, il l'envoie au processus 0, qui va ensuite lui redonner un ensemble de ligne à calculer.
Cette fois-ci, on va donc envoyer aux processus des blocs de 1 à 8 lignes à calculer (limites arbitraires et qu'on peut changer pour optimiser les choses), et donc au pire si un processus met beaucoup de temps pour calculer les 8 lignes du milieu, pendant ce temps les autres processus calculeront peut-être 32 lignes ou plus, puisque la charge est répartie dynamiquement !
Et là, le résultat est sans appel, c'est beaucoup mieux : on arrive sous la barre de la seconde, dès qu'on a 8 processus ou plus ! Et pourtant, le processus 0 ne calcule rien, il ne fait que récupérer le résultat des autres :p On a donc à présent un système qui tient bien la charge, qui peut supporter un grand nombre de processus, et qui s'adapte aux besoins. On peut même avoir un parc hétérogène de machines, ce n'est plus gênant.
4. Pour aller plus loin...
On peut à présent réfléchir à des optimisations pour ce système.
En fait, la faille est que cette fois-ci on passe pas mal de temps dans les communications à cause des transferts de taille relativement faibles. De plus, si tous les processus finissent de calculer à peu près en même temps, alors ils vont tous devoir attendre que le processus 0 ait reçu les messages pour continuer, donc on a tout de même une partie du temps qui est perdu en communication et surtout en attente de communication. Plusieurs stratégies peuvent permettre de limiter ce temps, en voici quelques une en vrac :
- Faire des paquets plus gros : si on fait des paquets plus gros, on fera au total moins de communications, donc en théorie on devrait aller plus vite. Sauf qu'on s'expose au risque d'avoir à attendre à la fin un processus trop lent qui aurait eu un gros bloc à finir... On pourrait donc imaginer faire calculer des blocs de grande taille au début, et réduire la taille et fur et à mesure de l'avancement. Comme ça, à la fin, tout le monde aura de petites taches, et devrait finir sensiblement en même temps...
- Permettre au processus 0 de travailler ! Pourquoi devrait-il perdre son temps à attendre les autres ? En fait, il pourrait s'allouer une ligne à calculer, mais regarder tous les X pixels s'il n'a pas une communication en attente. Comme ça, il participe aussi au calcul, et on devrait gagner un peu (mais plus on aura de processus, moins ça sera intéressant, car plus il devra communiquer de toute façon)
- Dans la version actuelle, les communications sont synchrones : quand on demande à avoir des lignes à calculer, on est bloqué en attendant que le processus maître réponde... Une meilleure stratégie pourrait être d'envoyer la demande de façon asynchrone (ie, non bloquante) quand on arrive au milieu du calcul, de façon à avoir la réponse sous le coude à la fin du calcul. Comme ça, dès que c'est fini, on a de fortes chances d'avoir le message près en réception. Dans le même genre, on pourrait imaginer se voir confier 2 taches à la fois par le processus maître, et donc quand on fini la première on en redemande une, etc... Je pense qu'au final ça revient sensiblement au même, à voir.
- Mieux répartir la charge dès le départ. Cette stratégie est celle préconisée par Mathias, tout le mérite lui en revient ^^ En gros, on peut imaginer calculer au début une version simplifiée (calculée plus rapidement, ou alors plus petite) afin de localiser plus rapidement les zones noires, et donc dès le départ faire des paquets de taille variable selon la charge de travail estimée (avec les options par défaut, le temps pour traiter un pixel varie d'un facteur 10 000 entre les pixels les plus rapides à calculer et les plus longs). Au lieu d'envoyer des paquets de taille relativement fixe (et donc représentant une charge de travail très variable), on peut alors envoyer des paquets dont les charges effectives sont proches.
- Tenter de répartir un peu mieux les temps de communications entre les différents processus : là le facteur ralentissant est que tout le monde communique avec le processus 0. On pourrait imaginer sous-découper les processus et l'image en 2 groupes (voire plus), leur faire se débrouiller avec ça, et puis à la fin rassembler les lignes calculées. On limite alors les communications car 2 processus (voire plus) vont centraliser les appels. Dans cette optique, on pourrait avoir une partie des processus qui remplissent l'image par le haut, et l'autre partie par le bas : quand les 2 groupes se sont rejoints, on s'arrête !
Et alors ?
Bah rien ^^ J'ai trouvé ça sympa comme sujet, donc je me suis dit que j'en ferai un billet :p Bon, c'est sûr que c'est plus facile de faire ce genre de chose à la fac où on peut monopoliser 16 PCs en même temps (dual core, donc potentiellement 32 processus à pleine vitesse), alors que chez soi on a bien moins de matériel... Je devrais peut-être économiser pour installer une ferme de PCs chez moi en fait :p
LibGD : affichage de cercles et d’arcs…
Aujourd'hui je devais changer la routines d'affichage de notre fonction "SoftRectangle", qui affiche des rectangles à bord arrondis, pour passer d'un affichage d'une couleur donnée à un affichage en utilisant un XOR (histoire que les contours marchent quelle que soit la couleur de fond).
Comme on utilisait de façon extensive les routines d'affichage de la libGD, ce n'était pas super compatible. Je me suis dit, un peu naïvement, que j'allais récupérer les sources, extraire les routines utilisées, et changer le pixel plot par du XOR... Et bien finalement quand j'ai vu tout ça j'ai préféré le refaire ^^
En fait, déjà, toutes les routines de dessin sont 100% génériques. Comprendre par là qu'un des paramètres d'une image est son type (truecolor, palette, etc...), et que bien entendu la façon d'écrire un pixel en dépend complètement. Du coup, quand on trace une ligne, pour chaque pixel à afficher on va utiliser la routine générique qui va regarder le type et appeler la bonne macro correspondante... Je ne sais pas si le compilo arrive à faire son boulot à fond pour optimiser tout ça, mais j'espère, sinon le résultat ne doit pas être terrible niveau perfs :s
Bref, je disais ça surtout pour la routine qui permet de tracer les arcs de cercle. Là j'ai eu un peu peur, car au final la routine ne fait que parcourir les angles possibles, degré par degré, et trace des lignes entre les différents points pour former le cercle... Forcément, pour mon XOR ce n'était pas terrible car chaque pixel était allumé/éteint une bonne dizaine de fois, donc c'était un poil trop aléatoire... La bonne optimisation que j'ai vue est l'utilisation d'une LUT en lien et place des cosinus/sinus, mais par contre pour ne pas dépasser, chaque accès dans la LUT nécessite un petit calcul de modulo 360 qui ne doit pas être gratuit :/
Bon, j'ai voulu faire mieux, à savoir un truc qui marchera dans mon cas et qui tournera, pour le coup, vraiment bien. Je me suis donc tourné vers Monseigneur Bresenham et son algorithme de tracé d'arc de cercle. Je ne vais pas rentrer trop dans les détails, mais en gros on ne va afficher les pixels qu'une fois, et en plus histoire d'aller super vite, pour chaque calcul de position, on l'utilise 8 fois (de façon assez logique on a 1 fois par cadran, donc ça fait déjà 4 fois, et en fait dans chaque cadran on peut imaginer partir d'un sens ou de l'autre (symétrie "en diagonale"), ce qui multiplie par 2 
).
procédure tracerOctant (entier rayon, entier x_centre, entier y_centre) déclarer entier x, y, m ; x ←0 ; y ← rayon ; // on se place en haut du cercle m ←5-4*rayon ; // initialisation Tant que x <= y // tant qu'on est dans le second octant tracerPixel( x+x_centre , y+y_centre ) ; tracerPixel( y+x_centre , x+y_centre ) ; tracerPixel( -x+x_centre , y+y_centre ) ; tracerPixel( -y+x_centre , x+y_centre ) ; tracerPixel( x+x_centre , -y+y_centre ) ; tracerPixel( y+x_centre , -x+y_centre ) ; tracerPixel( -x+x_centre , -y+y_centre ) ; tracerPixel( -y+x_centre , -x+y_centre ) ; si m > 0 alors //choix du point F y ← y - 1 ; m ← m-8*y ; fin si ; x ← x+1 ; m ← m + 8*x+4 ; fin tant que ; fin de procédure ;
Là ça fait des cercles complets alors que je voulais juste faire des cadrans vite fait, mais en fait il m'a suffit de rajouter en paramètre la largeur et la hauteur de la boite à créer, et de rajouter des +w et des +h là où il faut (en gros en imagine qu'on dessine de base le cadran en haut à gauche, du coup les cadrans avec un x positif on doit leur ajouter +w, et les cadrans avec un y positif on leur ajoute +h...
Avec ça on obtient de façon rapide et efficace le tracé des 4 quart de cercle à moindre frais
Cet algo ne présente qu'une limite, qui fait que je vais probablement voir pour le remplacer par un autre : Si on affiche 2 cercles concentriques dans le but de faire un tracé 2 fois plus épais... on a des trous ! Il n'a pas été fait pour ça, et donc il faudra alors se tourner vers un autre algo, tel quel algorithme de tracé de cercle d'Andres.
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 :
- Pixel plein, on affiche bêtement
- Pixel avec alpha, on affiche avec le code lent
- 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.
- 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.
- Pour les pixels semi-transparents, pas de miracle, mais on économisera pour chaque pixel le if...
- 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.
Algorithmes majeures
Un groupe de programmeurs a décidé, pour le fun, de faire une compilation des algos les plus importants selon eux. C'est assez subjectif pour certains, et très vrai pour d'autres. J'ai trouvé la liste assez intéressante, et comme je ne connais pas tout, je prendrai le temps de me documenter dessus
Et si jamais je trouve la motivation, chacun de ces algos pour donner naissance à un petit billet 
Je vous file donc le lien vers la source : http://www.risc.jku.at/people/ckoutsch/stuff/e_algorithms.html
J'ai aussi démarré un topic sur dev-fr.org pour faire une liste bien à nous ! http://www.dev-fr.org/index.php/topic,4729.msg46847/topicseen.html
Et sinon vous cliquer sur le lien ci-dessous pour lire un beau copié/collé de tout ça (attention, anglophobes s'abstenir !)
Pixel plot alpha optimisé
Bon, je n'ai pas eu le temps de faire un billet hier, j'espère me rattraper aujourd'hui avec une astuce que j'avais trouvée assez géniale pour écrire en 15bit des pixels avec niveaux d'alpha de façon super rapide. Je l'avais utilisé il y a quelques années sur PocketPC et les performances étaient hallucinantes.
Duff’s Device
En lisant vite fait un topic sur playeradvance.org je suis tombé sur une remarque de Nesgba (que je salue au passage ^^) : "tu peux utiliser le fameux duff-device en version asm pour accélérer le traitement. "
Bon, alors le fameux duff-device, je ne connaissais pas... Un petit tour sur Wikipedia plus tard, je vois qu'en fait, si, je connaissais, mais pas son nom. Il faut rendre à César ce qui est à César... C'est donc Tom Duff qui a pondu ça en 1983
Même si la plupart doivent connaitre, je me dis que c'est une belle astuce, et que donc ça peut être intéressant de la présenter ici...
Dithering : méthode de Sierra
Un livre électronique a un gros défaut : son écran monochrome, qui ne présente que peu de niveaux de gris. Hier je bossais donc sur améliorer le rendu (en terme de vitesse et de qualité), sachant que le résultat final n'est codé que sur 3bits (8 niveaux de gris).
Je vais donc vous présenter la méthode de dithering qu'on a utiliser pour avoir un meilleur rendu : celle de Sierra. Petit schéma pour illustrer le but du jeu :
Image d'origine |
Méthode de Sierra |