TACTIQUES D’OPTIMISATION DE LA VITESSE D'EXECUTION DU CODE
L’optimisation du code est la pratique qui consiste à modifier un code correct pour le rendre plus efficace. Il peut s’agir de la taille ou de la vitesse d’un programme. Mais dans ce tutoriel, nous ne nous occuperons que de la vitesse d’exécution.
On peut considérer ce problème d’optimisation de la vitesse à deux niveaux : stratégique ou tactique.
Au niveau stratégique, il s’agit de modifications obtenues par la refonte de la conception de tout le programme et des données. Autant dire de repartir presque à zéro. Il y a cependant une solution extrêmement efficace qui consiste à acheter (ou à faire acheter par l’utilisateur qui se plaint de la lenteur) un nouvel ordinateur plus rapide et plus puissant (héhéhé).
Je vous laisserai décider de la stratégie à adopter et je ne traiterai que des tactiques. C’est-à-dire de modifications à petite échelle qui ne concerneront que quelques lignes de code.
On a calculé, à propos des programmes Fortran, que 4% d’un programme représentait en moyenne 50% de son temps d’exécution. C’est sans doute vrai pour tous les langages. Nous allons voir comment améliorer cet état de fait.
D’abord parlons d’un malentendu courant que voici :
«La réduction du nombre de lignes de code conditionne la taille et la vitesse de l’exécutable.»
C’est faux !
Une preuve?
- Initialisons un tableau de 10 éléments :
for i := 1 to 10 do MaTable[ i ] :=0;
A votre avis, la méthode ci-dessous sera-t elle plus rapide ou plus lente?
MaTable[1] := 0;
MaTable[2] := 0;
MaTable[3] := 0;
MaTable[4] := 0;
MaTable[5] := 0;
MaTable[6] := 0;
MaTable[7] := 0;
MaTable[8] := 0;
MaTable[9] := 0;
MaTable[10] := 0;
Un test avec Delphi7 donne l’avantage à la deuxième méthode avec un ratio de performance de 1.7 : 1 (1.7 fois plus rapide !)
J’en profite pour effectuer une petite mise en garde.
Les techniques que je vais présenter ne constituent pas des recettes à appliquer aveuglément. Peu de techniques s’appliqueront d’une façon assez générale pour être directement copiées dans votre code. Ce sera à vous de les tester et de vérifier que votre compilateur n’y est pas allergique. En effet, certaines techniques, paraissant pourtant de bon sens, pourront dégrader les performances après la compilation. J’en montrerai un exemple et je rappellerai ce point très important : « testez, testez et re-testez ! »
Voici les six commandements à garder en mémoire pour obtenir de bonnes performances. Allez ! Mettons les doigts dans le cambouis !
« LOGIQUE DE DELPHI TU ADOPTERAS »
Je ne doute pas que vous ayez tous une certaine dose de logique. Mais bon… Il ne faut pas craindre l’overdose.
Par exemple, les expressions logiques suivantes sont équivalentes :
(not A) and (not B)
not (A or B)
En choisissant la 2ème, on gagne une opération ‘not’. Le temps gagné sera sans doute infime, mais dans une boucle très longue, ça se sentira.
Sortir d’un test en temps et en heure :
Voici un exemple de code optimisable :
for i := 0 to High( TableTest ) do if (TableTest[ i ] < 0) then NegativeFound := true;
C’est une boucle de recherche, un cas très courant. Le principe d’optimisation consiste à ne pas continuer à tester lorsque le résultat est connu. Appliquons ce principe :
for i := 0 to High( TableTest ) do begin
if TableTest[ i ] < 0 then begin
NegativeFound := true;
Break; //On sort dès que le résultat est connu.
end;
end;
Ici, le gain de performance sera très variable en fonction du contexte. Mais le plus souvent, le gain sera très important. Si on place une valeur négative au milieu du tableau, on peut s’attendre à un temps de traitement deux fois plus rapide. Et c’est bien ce que confirment les tests.
Un autre exemple :
N := Random(101);
…
if (N>=0) and (N<5) then Categorie := 1;
if (N>=5) and (N<20) then Categorie := 2;
if (N>=20) and (N<101) then Categorie := 3;
Et ce même code partiellement optimisé :
if (N>=20) then Categorie := 3 //On sort dès que le résultat est connu.
else if (N>=5) then Categorie := 2//On sort dès que le résultat est connu.
else Categorie := 1;
Ratio de performance = 1.3 : 1 Mais on peut faire mieux…
Ranger les tests par ordre croissant :
if (N<5) then Categorie := 1
else if N<20 then Categorie := 2
else Categorie := 3;
Maintenant, le ratio de performance = 1.9 : 1
Vous allez me dire : « - Où est la logique dans tout cela ? »
- Bein, c’est la logique du compilateur de Delphi7, tiens !
Je vous avez bien dit : « testez, testez et re-testez ! »
Cet exemple souligne la nécessité de ne pas suivre aveuglément des conseils d’optimisation. Ce qui est valable pour C# ne le sera pas forcément pour Java ou Delphi. Certaines optimisations valables pour un langage dégraderont même très fortement les performances dans un autre langage. De plus, cela peut même varier d’une version à l’autre d’un même compilateur. Vous devrez donc toujours mesurer les performances car les règles du jeu changent lorsque vous changez de langage, de compilateur ou de version d’un même compilateur, de processeur, de mémoire vive, de région (bon, d’accord, peut-être pas de région), etc…
Je cite Olivier DAHAN :
« Prenons l’instruction Case pour exemple. Jusqu’à Borland Pascal 7 (BP7) l’ordre le meilleur des constantes de cas en termes d’efficacité du code devait être celui de l’ordre décroissant de la fréquence d’utilisation : le cas le plus fréquent devant être placé en premier, le moins fréquent en dernier. Cela était lié au code machine généré par le Pascal (une suite de comparaisons et de sauts de cas en cas, du premier au dernier). L’Objet Pascal de Delphi génère un code très différent, et ici le moyen d’optimiser l’efficacité d’un Case est de placer les constantes de cas dans l’ordre numérique croissant (qui est celui de l’ordre de la déclaration dans le type si le sélecteur de cas est de type énuméré). »
J’espère donc avoir réveiller votre méfiance.
Sinon, je rajoute une couche :
Case of meilleur que if then else :
Au lieu d’écrire :
case N of
20..100 : Categorie := 3;
5..19 : Categorie := 2;
else Categorie := 1;
end
On préférera la formulation 1.5 fois plus rapide :
case N of
0..4 : Categorie := 1;
5..19 : Categorie := 2;
else Categorie := 3;
end;
Maintenant, le ratio de performance = 1.95 : 1
Presque deux fois plus rapide que l’exemple de départ ! (Ca tombe bien pour une fois, car Case of est toujours plus lisible que des if then else imbriqués).
-En C#, Case of et if then else sont comparables.
-Par contre, en Java if then else est 6 fois plus rapide qu’un case of.
-Et en Visual Basic, c’est Case of qui est 4 fois plus rapide que if then else (Steve McConnell dixit).
A bon entendeur, salut !
Remplacer des expressions logiques complexes par un tableau :
A titre d’exemple abstrait, supposons que vous ayez à assigner un numéro de catégorie (0, 1, 2, 3) à un objet en fonction de son appartenance à un ou plusieurs ensembles A, B, C :
Exemple extrait du livre de Steve McConnell «CODE COMPLETE» et adapté du C++ à Delphi.
En général, on écrira un truc du genre :
if ((N in EnsembleA) and not (N in EnsembleC)) or ((N in EnsembleA) and
(N in EnsembleB) and (N in EnsembleC)) then Categorie := 1
else if ((N in EnsembleB) and not (N in EnsembleA)) or ((N in EnsembleA) and
(N in EnsembleC) and not (N in EnsembleB)) then Categorie := 2
else if (N in EnsembleC) and not (N in EnsembleA) and not (N in EnsembleB)
then Categorie := 3
else Categorie := 0;
Avec une recherche dans un tableau, nous n’allons certes pas augmenter la lisibilité du code, mais ce ne sera pas beaucoup plus sibyllin… De toute façon, on peut toujours documenter le code avec des commentaires et un tableau sera plus facile à modifier si nécessaire. Cela donnera :
type
TTab = array[0..1, 0..1, 0..1] of byte;
const
TableCategorie : TTab = // notB,notC notB,C B,notC B,C
(((0, 3), (2, 2)), // notA
((1, 2), (1, 1))); // A
Categorie := TableCategorie[Ord(N in EnsembleA), Ord(N in EnsembleB), Ord(N in EnsembleC)];
Ratio de performance = 9 : 1
« LES BOUCLES TU VERIFIERAS »
Placer les tests à l’extérieur des boucles :
Il est facile de repérer les tests qui ne sont pas modifiés à l’intérieur des boucles :
for i := 0 to High( TableTest ) do begin
if Choix = 0 then TableTest[ i ] := TableTest[ i ] + 1
else TableTest[ i ] := TableTest[ i ] - 1;
end;
Et la même chose optimisée :
if Choix = 0 then
for i := 0 to High( TableTest ) do TableTest[ i ] := TableTest[ i ] + 1
else for i := 0 to High( TableTest ) do TableTest[ i ] := TableTest[ i ] - 1;
Ratio de performance = 1.35 : 1
Déroulez les boucles :
Cette technique se rapproche du premier exemple de ce tutoriel où on déroulait complètement une boucle de 10 itérations. En pratique, ce n’est pas réalisable pour un grand nombre d’éléments ou quand celui-ci nous est inconnu. On peut cependant adapter cette technique. Voici une boucle classique :
i:=0;
while i < High(TableTest) do begin
TableTest[ i ] := 0;
Inc(i);
end;
Et un exemple de la même boucle partiellement déroulée :
i:=0;
while i < High(TableTest)-3 do begin
TableTest[ i ] := 0;
TableTest[ i+1 ] := 0;
TableTest[ i+2 ] := 0;
TableTest[ i+3 ] := 0;
inc(i,4);
end;
{On ajuste les derniers cas:}
if i = High(TableTest)-1 then TableTest[ High(TableTest)-1 ] := 0;
if i = High(TableTest)-2 then TableTest[ High(TableTest)-2 ] := 0;
if i = High(TableTest)-3 then TableTest[ High(TableTest)-3 ] := 0;
Ratio de performance = 1.4 : 1
Mais c’est une technique que je ne recommande pas. D’abord, je la trouve affreuse. Ensuite, il faut vraiment tester le gain de performance dans chaque cas car il peut changer en fonction des calculs effectués. Le compilateur de Delphi fait en général beaucoup mieux qu’un tel bricolage. A tester et n’utiliser que lorsque le gain en vitesse de traitement est crucial.
Les valeurs sentinelles :
Exemple d’une boucle de recherche contenant un test composé :
NegativeFound := False;
i := 0;
while (not NegativeFound) and (i < High(TableTest)) do begin
if TableTest[ i ] < 0 then NegativeFound := true;
inc(i);
end;
Dans ce code, on sort bien de la boucle en temps et en heure, cependant chaque itération de la boucle teste (not NegativeFound) et (i < High(TableTest)). Le test TableTest[ i ] < 0 sert à déterminer si la valeur négative a été trouvée. La boucle exécute donc 3 tests par itération.
Mais on peut n’effectuer qu’un test par itération. Il suffit d’affecter la valeur de recherche à l’élément qui suit immédiatement la fin de la plage de recherche (N’oubliez pas d’allouer de l’espace pour cet élément lorsque vous déclarez le tableau !). Ici, on affectera une valeur négative au dernier élément du tableau. Si on ne trouve pas de valeur négative avant de rencontrer celle qu’on a placée à la fin, on saura que la valeur recherchée ne se trouve pas dans le tableau.
Quelques lignes de code valent mieux qu’une longue explication :
TableTest[ High(TableTest) ] := -1; // Valeur sentinelle.
NegativeFound := false;
I := 0;
while not TableTest[ i ] < 0 do inc(i); //On sort.
{Et on vérifie que la valeur a été trouvée}.
if i < High(TableTest) then NegativeFound := true;
Ratio de performance = 1.7 : 1
Placez la boucle la plus active à l’intérieur :
Lorsque des boucles sont imbriquées, réfléchissez à la boucle que vous allez placer à l’extérieur et à celle que vous voulez à l’intérieur. L’exemple suivant est optimisable :
for Col := 0 to 999 do
for Ligne := 0 to 1 do Total := Total + MaTable[ Col, Ligne ];
La boucle extérieure est exécutée 1000 fois. La boucle intérieure 1000*2 = 2000 fois. Soit un total de 3000 itérations.
En inversant les boucles :
for Ligne := 0 to 1 do
for Col := 0 to 999 do Total := Total + MaTable[ Col, Ligne ];
Ratio de performance = 1.9 : 1
Dans le code optimisé, la boucle extérieure est exécutée 2 fois. La boucle intérieure 2*1000 = 2000. Soit un total de 2002 itérations.
« ATTENTION AUX DONNEES TU FERAS »
Voici quelques lignes qu’on peut souvent trouver dans un code qui affiche une animation à l’écran par exemple :
Var X, Y, Angle, Hypot : Smallint;
for Angle := 0 to 360 do begin
X := Round( cos(DegToRad(Angle)) * Hypot );
Y := Round( sin(DegToRad(Angle)) * Hypot );
end;
Se méfier des fonctions système :
D’abord, l’unité Math nous permet d’utiliser la fonction SinCos() qui est deux fois plus rapide que l’appel à Sin() suivi de l’appel à Cso() :
Var X, Y, Angle, Hypot : Smallint
Sinus, Cosin : Extended;
for Angle := 0 to 360 do begin
SinCos(DegToRad(Angle) ,Sinus, Cosin);
X := Round( Cosin * Hypot );
Y := Round( Sinus * Hypot );
end;
Ratio de performance = 1.3 : 1
DegToRad() est très explicite et favorise la lisibilité du code, mais il est aussi très gourmand en temps de traitement. On le vire et on fait l’opération à la main :
for Angle := 0 to 360 do begin
SinCos(Angle*0.0174532925199433 ,Sinus, Cosin);
X := Round( Cosin * Hypot );
Y := Round( Sinus * Hypot );
end;
Ratio de performance = 1.5 : 1 (Par rapport au premier exemple)
Mise en cache des données :
La véloce fonction SinCos() n’est pas aussi rapide qu’un accès à un tableau. La technique de mise en cache des données consiste à enregistrer systématiquement les valeurs que vous utilisez souvent en mémoire. Ici, nous allons stocker les valeurs trigonométriques dans un tableau :
Var //var globales.
MonCos : array[0..360] of Extended; // Tableau en cache.
MonSin : array[0..360] of Extended; // Tableau en cache.
procedure TForm1.FormCreate(Sender: TObject);
var Angle : Integer;
Sinus, Cosin : Extended;
begin
for Angle := 0 to 360 do begin
SinCos(Angle*0.0174532925199433 ,Sinus, Cosin);
MonSin[ Angle ] := Sinus; //Création des tableaux en cache.
MonCos[ Angle ] := Cosin;
end;
...
for Angle := 0 to 360 do begin
X := Round( MonCos[ Angle ] * Hypot );
Y := Round( MonSin[ Angle ] * Hypot );
end;
Ratio de performance = 7 : 1 (Par rapport au premier exemple)
La CPU est optimisée pour le 32 bits :
Vous aviez sans doute remarqué qu’on travaillait avec des SmallInt dans la boucle de calcul. C’est justifié car largement suffisant pour calculer des coordonnées écran. Cependant, la CPU est beaucoup plus à l’aise en travaillant avec des Integers. La modification est minime :
Var X, Y, Angle, Hypot : Integer;
Sinus, Cosin : Extended;
Ratio de performance = 9 : 1 (Par rapport au premier exemple)
Précision superflue des fonctions système :
Tiens, c’est vrai qu’on travaille sur l’écran !
Si une valeur trigonométrique en Extended (15aine de chiffres après la virgule) se justifie pour faire « alunir » un homme, ici avec mon écran de ‘m…’, je n’ai pas besoin d’une telle précision. On va diminuer la précision des tableaux de valeurs trigonométriques en cache.
Et comme nous venons de voir que notre CPU aimait les 32 bits. Nous allons donc, par la même occasion, transformer les extendeds en Integers.
Dans la foulée, on supprimera le Round, fonction système très coûteuse aussi.
Var //var globales.
MonCosInt : array[0..360] of Integer; // Tableau en cache.
MonSinInt : array[0..360] of Integer; // Tableau en cache.
procedure TForm1.FormCreate(Sender: TObject);
var Angle : Integer;
Sinus, Cosin : Extended;
begin
for Angle := 0 to 360 do begin
SinCos(Angle*0.0174532925199433 ,Sinus, Cosin);
MonSinInt[ Angle ] := Round( Sinus * 1000 );
MonCosInt[ Angle ] := Round( Cosin * 1000 );
end;
...
for Angle := 0 to 360 do begin
X := MonCosInt[ Angle ] * Hypot div 1000;
Y := MonSinInt [ Angle ] * Hypot div 1000;
end;
Ratio de performance = 300 : 1 (Par rapport au premier exemple)
Parfois, avec cette technique, on aura une petite erreur d'une unité sur une coordonnée à cause de l’arrondi vers le bas de Div. Mais dans une animation sur l’écran cela passera inaperçu et de toute façon tout a un prix !
Rester vigilant à tout :
A votre avis, qu’est-ce qui ne colle pas dans le code suivant ?
Hypothenuse1 := Sqrt( Sqr(CoteA1) + Sqr(CoteB1) );
Hypothenuse2 := Sqrt( Sqr(CoteA2) + Sqr(CoteB2) );
if Hypothenuse1 < Hypothenuse2 then {Faire ceci};
C’est simplement que si Hypothenuse1 < Hypothenuse2, alors
CoteA1 + CoteB1 < CoteA2 + CoteB2
On peut s’épargner les coûteux Sqrt() et Sqr() avec simplement :
if CoteA1 + CoteB1 < CoteA2 + CoteB2 then {Faire ceci};
Ratio de performance = 10 : 1
« SCANLINE() TU UTILISERAS »
Si Canvas.Pixels[] peut être bien pratique pour connaître la couleur d’un pixel isolé, dans le cas où on travaille sur toute la surface d’un Bitmap, il faut utiliser Scanline[] qui est beaucoup plus performant. En effet, les goulets d’étranglement pour ce qui concerne les temps d’exécution se trouvent souvent dans les traitements de Bitmap.
Je vous renvoie à l’excellente démonstration de Florenth qui semble avoir fait plusieurs fois le tour du problème ;)
http://www.delphifr.com/codes/BON-USAGE-SCANLINE_43222.aspx
« DES IDEES RECUES TU TE MEFIERAS »
Un exemple : le décalage :
On voit et on entend souvent (j’étais dans le lot) que les décalages binaires sont plus rapides pour remplacer une multiplication ou une division par 2, 4, 8, etc :
X := X shl 1
Y := Y shr 2
Pourtant les temps de calcul sont équivalents avec D7. Alors, préférez la lisibilité :
X := X * 2
Y := Y div 4
Ratio de performance = 1 : 1
J’ai demandé une explication à f0xi, pensant que le compilateur de Borland était vraiment excellent. Voici sa réponse :
« C'est surtout les CPU qui deviennent bons.
A l'époque des CPU monocore, faire un shr 1 ou shl 1 était plus rapide qu'une multiplication ou division. Maintenant avec les CPU dual, quad, octo-core, ça devient ridicule ce genre de petite optimisation.
[ ]
L'optimisation "locale" n'est plus vraiment une question à se poser. Aujourd'hui on parle plus d'optimisation "globale" de l'ensemble du programme et de ses éléments et également de plus travailler la méthodologie ; car si le compilo est capable d'optimiser certaines instructions, il n'est pas encore capable d'optimiser tout seul une routine. »
« L’OPTIMALISATION TU EVITERAS »
Optimisation, optimalisation, l’un des deux termes ne vous semble-t il pas démesuré ? ;)
Un logiciel est un fragile équilibre entre sa lisibilité, sa facilité de maintien, sa vitesse d’exécution, sa taille, sa justesse, etc.
Touchez à l’un de ces éléments et il est probable que l’équilibre sera rompu. Ce qui est sûr, c’est que l’optimisation de la vitesse rend souvent le code beaucoup moins lisible et moins facile à maintenir. Il faut donc toujours se demander ce qui est le plus important. Avec les machines modernes c’est finalement rarement la vitesse qui est un problème. De toute façon, ce sera à vous d’arbitrer ce dilemme.
Conclusion :
L’abus nuit en tout. Sachez utiliser ces techniques à bon escient. En cas d’optimisation de votre code, n’hésitez pas à commenter la technique que vous employez. En effet, si les techniques décrites ici étaient toujours ‘cleans’, elles seraient la norme en programmation, non ?
Il existe bien sûr des centaines d’autres techniques plus ou moins performantes qui vont du fait d’éviter les tableaux à plusieurs dimensions jusqu’à utiliser l’assembleur ( ainsi que l’a fait remarqué WHITEHIPPO, l’optimisation ultime restera quand même l'optimisation en assembleur, et je vous renvoie à ce site : http://www.fastcodeproject.org/ pour obtenir les meilleures routines ). Mais le but de ce tutoriel était de vous mettre sur de bons rails, non pas d’établir une liste exhaustive des techniques. J’espère être parvenu à vous donner quelques conseils généraux qui vous aideront.
Et quand vous serez parvenu à multiplier par 300 la vitesse d’exécution d’un code, vous serez content de ce que vous aurez fait à la seule force de nos petits neurones ! ^_^
C’est une des satisfactions qui font partie des joies de la programmation.
Je remercie ceux qui m’ont aidé ou inspiré ce tutoriel:
Steve McConnell (TOUT sur le CODE, en français chez Microsoft)
Olivier Dahan et Paul Toth (Delphi7 Studio chez Eyrolles
fOxi (Administrateur de CS et légèrement obsédé par les optimisations, graphiste oblige ;)
Florenth (Membre de CS, dont le dada est l’optimisation. On se demande d’ailleurs bien pourquoi ce n’est pas lui qui a écrit ce tuto ;)
Caribensila