DivideConcept.net

le blog de divide.

Archive pour septembre 2005

Quelques point importants pour les programmeurs débutants soucieux d’optimiser au maximum leur code, et aux curieux souhaitant avoir quelques notions de ce qu’est l’optimisation d’un code (attention il faut avoir quelques bases de programmation pour comprendre les pseudo-codes de cet article)…

Attention les astuces données ici sont très generales (et donc d’utilisation frequentes) et relevent plus d’optimisation liées aux fonctionnement interne des processeurs que de l’algorithmie (qui doit etre laissé a la seule intelligence du concepteur du programme…).
Il convient également de ne pas les utiliser a n’importe quel sauce, l’optimisation étant generalement antonyme de lisibilité.
A reserver aux endroits critiques donc.

Si la difference de vitesse gagnée avec ces optimisations a tendance a disparaitre sur les CPU moderne, elle reste plus que jamais valable avec l’apparition des GPU, qui restent des processeurs "primitifs" (mais dont la force reside dans le parallelisme).

Les tests ? A la poubelle !

Les tests prennent beaucoup de temps d’execution comparés aux operations classiques; d’autant plus quand on a une architecture parallele (plusieurs proc, comme sur une carte graphique), chaque proc attendant du coup de se synchroniser avec l’autre, car la longueur du programme risque de varier d’un thread à l’autre à cause de ces tests.

Bref, il faut les eviter comme la peste dans ce genre de situation !
Mais parfois, il est quand meme necessaire pour le bon deroulement d’un calcul d’en faire un… alors comment faire ?

Il faut ruser !

Par exemple au lieu d’ecrire

if (var1>var2)
{
max=var1;
} else {
max=var2;
}

on ecrira, beaucoup plus economique en temps de traitement:

test=(var1>var2); // renvoi 1 ou 0
max=var1*test+var2*(1-test);

et voila !
si var1>var2, alors test=1, et max=var1
si var1<var2, alors test=0, et max=var2

on obtient donc le meme resultat que dans le premier algo, mais en se passant de test !
Avec ce genre d’astuce on divise facilement par 3 le temps d’execution d’un Pixel shader 3.0…
Les Pixels Shaders 2.0 n’acceptent pas les tests, alors on est forcé d’utiliser ce genre d’astuce de toute façon ;)

Les divisions ? Piège à con !

Une division est plus longue à calculer qu’une multiplication.. donc il faut toujours essayer de factoriser au maximum ces divisions.

Par exemple, ne pas ecrire:

var1=var2/var3+var4/var3+var5/var3;

mais

inverse_var3=1/var3;
var1=var2*inverse_var3+var4*inverse_var3+var5*inverse_var3;

Les fonctions sont nos amies

Ce n’est pas pour rien qu’il existe dans beaucoup de langages des fonctions du type min, max, normalize… dont l’usage est courant; il ne faut pas hesiter à s’en servir plutot que de reecrire de telles fonction, car on ne les optimisera jamais aussi bien ! Ces fonctions incluses avec les langages de programmations ont été optimisées au maximum, souvent en passant par l’Assembleur (ndr: le langage de plus bas niveau en informatique), il est donc vain de chercher à faire plus rapide !

Les optimisations implicites des compilateurs: s’en méfier !

Lorsqu’on cherche à optimiser un programme, il faut toujours se mefier des optimisations que le compilateur fait dans notre dos…
Pas qu’elles soient mauvaises, mais elles faussent souvent les chronometrages des bouts de code qu’on veut tester si on y prend pas garde…

Exemple:

var4=var1+var2;
var5=var6+var7;
Print var4;

Combien d’operations mathématiques dans ce bout de code ?
2, normalement (2 additions)

Mais le compilateur ne va pas tenir compte de la ligne

var5=var6+var7;

car on exploite pas var5 dans le programme (seul var4 est affiché), alors à quoi bon la calculer ?

Du coup on pense que 2 additions sont calculées super vite (bien sur que c’est calculé super vite 2 additions, mais c’est une image…), mais en fait il n’en calcule qu’une !.. et on se fait baiser facilement a ce jeu la.

En conclusion

Bien sur ce n’est pas l’Encyclopedia Optimisatis, mais ce sont les points que j’ai remarqué le plus fréquement depuis que j’ai commencé à programmer, et je les applique constamment (d’autant plus avec l’apparition des pixels shaders).
Il faut savoir reperer les "goulots d’etranglement" d’un programme, souvent un petit bout de code qui est repeté des milliers de fois, et dont l’optimisation permet de gagner facilement en vitesse !