Optimisation de code
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
Langages à objets
C++ - C# - D
Delphi - Eiffel - Groovy
Java - Lisaac - Python - Ruby
Simula - Smalltalk
Visual Basic - WLangage
Langages impératifs
APL - ASP - Assembleur
BASIC (En programmation, BASIC est un acronyme pour Beginner's All-purpose Symbolic Instruction Code. qui désigne une famille de langages de programmations de haut niveau.) - C - Cobol (COBOL est un langage de programmation de troisième génération créé en 1959 (officiellement le 18 Septembre 1959). Son nom est l'acronyme de COmmon Business Oriented Language qui révèle sa vocation...) - Natural (Natural est un langage de programmation semi-compilé, édité par la société allemande Software AG.)
Forth - Fortran - Limbo
Logo - Pascal - Perl - PHP (PHP (sigle de PHP: Hypertext Preprocessor), est un langage de scripts libre principalement utilisé pour produire des pages Web dynamiques via un...)
Langages fonctionnels
Haskell - ML/OCaml
Lisp/Common Lisp
Scheme - XSLT
Langages déclaratifs
Clips - Prolog
Langages concurrents
Ada 95 - Erlang
Voir aussi
Conception - Codage (De façon générale un codage permet de passer d'une représentation des données vers une autre.)
Tests - Optimisations

En programmation informatique (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire...), l'optimisation est la pratique qui consiste généralement à réduire le temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) d'exécution d'une fonction, l'espace occupé par les données et le programme, ou la consommation d'énergie (Dans le sens commun l'énergie désigne tout ce qui permet d'effectuer un travail, fabriquer de la chaleur, de la lumière, de produire un mouvement.).

La règle numéro un (Numéro Un est une référence à un modèle de personnages fictifs de la série télévisée Battlestar Galactica, interprété par...) de l'optimisation est qu'elle ne doit intervenir qu'une fois que le programme fonctionne et répond aux spécifications fonctionnelles. L'expérience montre qu'appliquer des optimisations de bas niveau du code avant que ces deux conditions ne soient réalisées revient le plus souvent à une perte de temps et s'avère néfaste à la clarté du code et au bon fonctionnement du programme :

L'optimisation prématurée est la source de tous les maux. ", Donald Knuth (Donald Ervin Knuth ([knu?θ], en chinois : ???[1]) (10 janvier 1938 à Milwaukee, Wisconsin - ) est un informaticien américain de renom et professeur émérite en informatique à l'Université de Stanford[2] (en tant que...) citant Dijkstra

Cependant cette citation, tronquée, est très souvent mal interprétée. La version complète étant:

On devrait oublier les petites optimisations locales, disons, 97% du temps : l'optimisation prématurée est la source de tous les maux. (We should forget about (L’about est un terme de charpenterie désignant l’extrémité façonnée d’une pièce de bois.) small efficiencies, say about 97% of the time: premature optimization is the root of all evil.) ", Donald Knuth

La citation originale indique très clairement que cette règle ne doit s'appliquer qu'aux optimisations locales, de bas niveau (réécriture en assembleur, déroulage de boucle etc.) et pas aux optimisations de haut niveau concernant le choix des algorithmes ou l'architecture (L’architecture peut se définir comme l’art de bâtir des édifices.) d'un projet (Un projet est un engagement irréversible de résultat incertain, non reproductible a priori à l’identique, nécessitant le concours et l’intégration d’une grande diversité de contribution, et...). Au contraire plus le projet grandit et plus ces optimisations de haut niveau seront difficiles et couteuses (en termes de temps, difficulté et budget), voire impossible, à effectuer.

La plupart des compilateurs récents pratiquent de façon automatique (L'automatique fait partie des sciences de l'ingénieur. Cette discipline traite de la modélisation, de l'analyse, de la commande et, de la régulation des systèmes dynamiques. Elle a...) un certain nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'optimisations qu'il serait fastidieux d'effectuer manuellement et qui rendraient le code source (Le code source (ou les sources voire le source) est un ensemble d'instructions écrites dans un langage de programmation informatique de haut niveau, compréhensible par un être humain...) moins lisible.

L'optimisation manuelle locale peut s'avérer nécessaire dans des cas très spécifiques, mais les mesures montrent que sur des machines RISC qui possèdent un nombre élevé de registres et où l'efficacité demande le regroupement des instructions identiques pour bénéficier de l'effet pipeline, l'optimiseur d'un compilateur C fournit souvent un code plus efficace que celui qui serait écrit en assembleur par un programmeur (En informatique, un développeur (ou programmeur) est un informaticien qui réalise du logiciel en créant des algorithmes et en les mettant en œuvre dans un langage de programmation.) expérimenté (ce qui n'était jamais le cas sur les machines CISC). Et de surcroit ce code est bien plus facile à maintenir, car les instructions en C restent dans un ordre lié à la seule intelligibilité du code et non aux spécificités de la machine : dans les optimiseurs actuels, en effet, les ordres machines associés à une instruction (Une instruction est une forme d'information communiquée qui est à la fois une commande et une explication pour décrire l'action, le comportement,...) ne se trouvent plus nécessairement en position contiguë, pour des raisons d'efficacité d'exécution. Cela rend le code assembleur généré particulièrement indéchiffrable.

Pratique de l'optimisation

Première approche

Avant de commencer l'optimisation, il faut savoir mesurer la vitesse (On distingue :) du code. Pour cela il faut choisir un paramètre (Un paramètre est au sens large un élément d'information à prendre en compte pour prendre une décision ou pour effectuer un calcul.), de préférence simple, mesurable. Ceci peut-être par exemple le temps de traitement sur un jeu de donnée (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) précis, ou le nombre d'images affichées par seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde d'arc est une...), ou encore le nombre de requêtes traitées par minute ( Forme première d'un document : Droit : une minute est l'original d'un acte. Cartographie géologique ; la minute de terrain est la...).

Une fois le paramètre de mesure déterminé, il faut mesurer le temps passé (Le passé est d'abord un concept lié au temps : il est constitué de l'ensemble des configurations successives du monde et s'oppose au futur sur une...) dans chacune des parties du programme. Il n'est pas rare que 80% à 90% du temps soit consacré à l'exécution de 10% du code (les boucles critiques). Les chiffres varient en fonction de la taille et de la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par...) des projets. Il faut localiser ces 10% de code pour être le plus rentable dans ses optimisations. Cette étape de localisation peut être réalisée à l'aide d'outils spécialisés d'instrumentation (Le mot instrumentation est employé dans plusieurs domaines :) du code nommés profilers. Ils sont chargés de compter le nombre d'exécutions de chaque fonction et de cycles du microprocesseur correspondants au cours de l'exécution.

Ensuite on itère sur la section la plus consommatrice de ressource autant de fois que nécessaire cette boucle :

  • optimisation d'une partie du code
  • mesure du gain de performances

Seconde approche

On peut optimiser à plusieurs niveaux un programme:

  • au niveau algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de résolution, par le calcul, d'un...), en choisissant un algorithme de complexité inférieure (au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du...) mathématique) et des structures de données adaptées,
  • au niveau du langage de développement, en ordonnant au mieux les instructions et en utilisant les bibliothèques disponibles,
  • en utilisant localement un langage de bas niveau (Un langage de bas niveau est un langage qui oblige le programmeur à se soucier de concepts proches du fonctionnement de la machine, comme la mémoire. Ceci rend pénible l'élaboration de...), qui peut être le langage C ou, pour les besoins les plus critiques, le langage assembleur.

On ne passe au niveau supérieur d'optimisation qu'une fois qu'on a épuisé les possibilités d'un niveau. L'utilisation d'un langage de bas niveau sur l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise...) d'un projet pour des raisons de rapidité est l'une des erreurs les plus communes et les plus coûteuses que puisse faire un projet industriel.

L'optimisation de code (En programmation informatique, l'optimisation est la pratique qui consiste généralement à réduire le temps d'exécution d'une fonction, l'espace occupé par les données et le programme, ou la consommation d'énergie.) est considéré par beaucoup de développeurs amateurs comme un art un peu magique et, pour cette raison, comme l'une des parties les plus excitantes de la programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la...). Ceci les conduit à croire qu'un bon programmeur est une personne qui optimise d'emblée le programme. Cependant l'expérience montre qu'elle ne peut palier une mauvaise conception initiale. C'est dans la conception que l'expérience du développeur joue (La joue est la partie du visage qui recouvre la cavité buccale, fermée par les mâchoires. On appelle aussi joue le muscle qui sert principalement à ouvrir et...) le plus. Par ailleurs, dans un nombre majoritaire et grandissant de cas, le " bon programmeur " est moins celui qui écrit du code astucieux (l'optimiseur s'en chargera le plus souvent mieux que lui) que celui qui écrit du code lisible et aisé à maintenir.

Une bonne connaissance des techniques de structures de données ainsi que des algorithmes (même sans aller jusqu'aux considérations théoriques poussées de la complexité algorithmique) se montre bien plus féconde que celle d'un langage d'assemblage. Lorsqu'on a déterminé l'algorithme le plus adéquat, les optimisations les plus efficaces peuvent être obtenues en utilisant le chemin suivant :

  • écriture du code critique dans un langage de haut niveau (Un langage de haut niveau en informatique est un langage de programmation qui permet au programmeur de s'abstraire de détails inhérents au fonctionnement de la machine, ceux-ci étant pris en compte lors de la compilation....) (comme Scheme ou Common Lisp),
  • application de transformations mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les...) successives qui préservent la spécification du programme tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) en réduisant la consommation des ressources,
  • traduction du code transformé dans un langage de bas niveau (langage C).

Dans la pratique, les performances des machines actuelles font que des applications comportant beaucoup d'entrées-sorties lentes peuvent faire l'économie de ces trois étapes et se rédiger directement dans un langage comme Haskell. L'application bien connue nget, qui moissonne systématiquement les images publiées dans les forums Usenet, avait dans sa première implémentation (Le mot implantation peut avoir plusieurs significations :) été écrite en Haskell. La version en C n'en a été qu'une traduction qui ne se révèle pas plus performante pour ce type d'application. Une application limitée principalement par le CPU et la vitesse de la mémoire (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) par contre pourra gagner énormément à être écrite dans un langage tel que le C ou le C++.

Optimisation automatique

Les compilateurs sont souvent capable de faire des optimisations locales, auxquelles aucun développeur ne penserait en première approche.

Pour le langage C, cela peut considérer :

  • les variables locales et les registres
  • les fonctions non implémentées en assembleur en tant que fonction
  • les switch, qui sont optimum.

Toutefois on peut grandement aider le compilateur en déclarant les variables avec les mots-clefs const et/ou restrict quand c'est possible. Autrement le compilateur ne peut savoir si une zone mémoire est accessible par d'autres références, et désactivera des optimisations (phénomène dit d'aliasing mémoire).

Exemples

Utilisation de variables locales pour éviter l'aliasing de mémoire

Le code C++ suivant sera en général peu optimisé par le compilateur car il est souvent incapable de savoir si le code de la boucle modifie ou non le compteur d'itérations : un pointeur ou une référence pourrait le modifier.

 
 void MyClass::DoSomething() const 
 { 
 for( int i=0; i<m_nbrElements; ++i ) 
 { 
 void *ptr = GetSomePtr(); 
 .... 
 } 
 } 
 

Dans cette version, on indique clairement qu'on utilise un nombre d'itérations fixé à l'avance et qui ne sera jamais modifié, autorisant le compilateur à effectuer des optimisations plus agressives:

 
 void MyClass::DoSomething() 
 { 
 const int nbrElements = m_nbrElements; 
 for( int i=0; i<nbrElements; ++i ) 
 { 
 .... 
 } 
 } 
 

Une spécificité du binaire : le décalage

Une des toutes premières optimisations a été celle de la division (La division est une loi de composition qui à deux nombres associe le produit du premier par l'inverse du second. Si un nombre est non nul, la fonction "division par ce nombre" est la réciproque de la fonction "multiplication par ce...) et de la multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .) par une puissance (Le mot puissance est employé dans plusieurs domaines avec une signification particulière :) de 2.

En effet, l'informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique...) actuelle repose sur le binaire, puisqu'elle utilise comme élément de base le transistor (et historiquement, auparavant le relais) qui n'autorise que deux valeurs différentes.

On a donc logiquement implémenté en langage machine (Le langage machine est la suite de bits qui est interprétée par le processeur de l'ordinateur lors de l'exécution d'un programme. C'est le langage natif du processeur. Il est aussi appelé code machine....) les opérations de décalage à gauche et décalage à droite.

En effet, en binaire, le décalage d'un nombre d'un cran vers la gauche le multiplie par 2.

Ainsi, 2 (102) décalé de 1 bit donne 4 (1002).
5 (1012) décalé de 2 bits donne 20 (101002) : 5 * 22 = 20.

Ceci marche (La marche (le pléonasme marche à pied est également souvent utilisé) est un mode de locomotion naturel. Il consiste en un déplacement en appui...) aussi pour la division, en décalant les bits vers la droite.

100 (11001002) décalé de 3 bits vers la droite donne 100 / 23 = 12.5 donc 12 (11002) car nous travaillons sur des nombres entiers.

La division (en dehors de ce cas et des cas pathologiques) est une instruction coûteuse en temps machine, et n'est d'ailleurs toujours pas disponible sur la grande majorité des processeurs de type RISC.

Le mot clef (Au sens propre, la clef ou clé (les deux orthographes sont correctes) est un dispositif amovible permettant d'actionner un mécanisme.) inline du C

Le code C suivant:

 
 inline int f(int a, int b) { 
 return a * b; 
 } 
 int g (int a) { 
 switch (a) { 
 case 10: 
 return f(a, a); 
 case 11: 
 case 12: 
 return f(a - 2, a); 
 case 1200: 
 return f(a - 2, a); 
 default: 
 return f(a, a); 
 } 
 } 
 

Une compilation avec gcc -O4 -S donne:

 
 .file    "opt.c" 
 .text 
 .p2align 4,,15 
 .globl   g 
 .type    g, @function 
 g: 
 pushl   %ebp 
 movl    %esp, %ebp 
 movl    8(%ebp), %edx 
 cmpl    $12, %edx 
 jg      .L14 
 leal    -2(%edx), %eax 
 cmpl    $11, %edx 
 jge     .L15 
 movl    $100, %eax 
 cmpl    $10, %edx 
 .L17: 
 je      .L2 
 movl    %edx, %eax 
 .L15: 
 imull   %edx, %eax 
 .L2: 
 popl    %ebp 
 ret 
 .p2align 4,,7 
 .L14: 
 movl    $1437600, %eax 
 cmpl    $1200, %edx 
 jmp     .L17 
 .size   g, .-g 
 .section        .note.GNU-stack,"",@progbits 
 .ident  "GCC: (GNU) 3.3.2 (Mandrake Linux (Au sens strict, Linux est le nom du noyau de système d'exploitation libre, multitâche, multiplate-forme et multi-utilisateur de type UNIX créé par Linus Torvalds, souvent désigné comme le noyau Linux. Par extension,...) 10.0 3.3.2-6mdk)" 
 

Ce qui pourrait se traduire, pour une compréhension plus aisée, par le code C suivant:

 
 int g(int a) { 
 int eax, b; 
 if (a > 12)          /* cas a == 1200 */ 
 goto (L’instruction goto (de l’anglais go to, en français aller à) est une instruction présente dans de nombreux langages de programmation. Elle est utilisée pour...) L14; 
 eax = a - 2; 
 if (a >= 11)         /* cas a == 11 ou a == 12 */ 
 goto L15; 
 eax=100;             /* = 10 * 10 */ 
 b=10; 
 L17: 
 if (a == b)          /* cas a == 10 */ 
 goto L2; 
 /* cas "default" */ 
 eax=a; 
 L15: 
 eax=eax*a; 
 L2: 
 return eax; 
 L14: 
 eax = 1437600;       /* = 1200*(1200-2) */ 
 b = 1200; 
 goto L17; 
 } 
 

On peut remarquer par exemple que la fonction 'f' n'a pas été générée, mais que son code a directement été incorporé dans la fonction 'g' (le mot clef 'inline' permet de forcer ce type d'optimisation en C )

Page générée en 0.335 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique