Optimisation de code

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En programmation informatique, l'optimisation de code est la pratique consistant à améliorer l'efficacité du code informatique d'un programme ou d'une librairie logicielle. Ces améliorations permettent généralement au programme résultant de s'exécuter plus rapidement, de prendre moins de place en mémoire, de limiter sa consommation de ressources (par exemple les fichiers), ou de consommer moins d'énergie électrique.

Principes d'optimisation[modifier | modifier le code]

La règle numéro un 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, 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[1]. »

— Donald Knuth

La citation originale indique que généralement durant l'écriture d'un code, on peut laisser de côté les optimisations locales, de bas niveau (réécriture en assembleur, déroulage de boucle, etc.). Il est possible d'interpréter cette citation en déduisant de celle-ci que les optimisations de haut niveau concernant le choix des algorithmes ou l'architecture d'un projet doivent venir avant celle de bas niveau. Ainsi, ce n'est que vers la fin de l'écriture du programme, une fois que l'analyse montre qu'un détail de bas niveau est critique qu'il peut éventuellement être nécessaire de le modifier :

« What Hoare and Knuth are really saying is that software engineers should worry about other issues (such as good algorithm design and good implementations of those algorithms) before they worry about micro-optimizations such as how many CPU cycles a particular statement consumes. »

— Randall Hyde, ACM Ubiquity Vol. 10, Issue 3

Au contraire plus le projet grandit et plus ces optimisations de haut niveau seront difficiles, coûteuses (en termes de temps, difficulté et budget) voire impossibles à effectuer.

La plupart des compilateurs récents pratiquent de façon automatique un certain nombre d'optimisations qu'il serait fastidieux d'effectuer manuellement et qui rendraient le code source 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 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 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[modifier | modifier le code]

Pour suivre l’efficacité d’une optimisation, le développeur s’appuie sur des tests de performance, c’est-à-dire sur des mesures objectives du temps de traitement et de la taille de la mémoire allouée.

La réduction de la taille des données résidentes en mémoire est complexe puisque la libération d’une zone de mémoire permet rarement de rendre la mémoire disponible pour le système d’exploitation[2].

Localisation du code à optimiser[modifier | modifier le code]

Pour évaluer le temps et la mémoire nécessaire pour chaque partie du programme, les développeurs réalisent le profilage du code. Il n'est pas rare qu’une grande partie du temps soit consacré à l'exécution d’un petit morceau du code, ce morceau de code est appelé « goulot d’étranglement ».

Le logiciel de profilage est chargé de compter le nombre d’exécutions de chaque fonction et de cycles du microprocesseur correspondants au cours de l'exécution.

Différentes approches d’optimisation[modifier | modifier le code]

Plusieurs approches existent pour optimiser un code :

Optimisation algorithmique[modifier | modifier le code]

L’optimisation algorithmique consiste à appliquer au code des transformations mathématiques successives qui préservent la spécification du programme tout en réduisant la consommation des ressources.

Optimisations grâce aux outils du langage[modifier | modifier le code]

L’utilisation de fonctions différentes voire de bibliothèques complètes différentes peut permettre une optimisation du programme.

Optimisation en changeant de langage utilisé[modifier | modifier le code]

Dans la pratique, les applications comportant beaucoup d'entrées-sorties lentes peuvent être optimisées en étant réécrites dans un langage comme Haskell ou Python.

Une application nécessitant beaucoup de calculs et d’affectations en mémoire peut être optimisée en étant réécrite dans un langage tel que le C ou le C++.

Optimisation automatique[modifier | modifier le code]

Les compilateurs sont souvent capables 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'alias de mémoire).

Exemples[modifier | modifier le code]

Utilisation de variables locales pour éviter les alias de mémoire[modifier | modifier le code]

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[modifier | modifier le code]

Une des toutes premières optimisations a été celle de la division et de la multiplication par une puissance de 2.

En effet, l'informatique 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 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 () décalé de 1 bit donne 4 ().
5 () décalé de 2 bits donne 20 () : .

Ceci marche aussi pour la division, en décalant les bits vers la droite.

100 () décalé de 3 bits vers la droite donne donc 12 () car nous travaillons sur des nombres entiers.

L'arithmétique entière d'un processeur est en fait l'arithmétique dans l'anneau des par exemple. Et donc, tous les nombres premiers avec ont un inverse, et il est possible d'effectuer une division par l'un de ces nombres en une seule instruction. Par exemple, dans l'anneau des entiers sur 32 bits, diviser par 3 revient à multiplier par 2863311531. Diviser par 14 revient à multiplier par 3067833783 puis diviser par 2. C'est donc possible avec deux instructions. Les compilateurs savent faire ces optimisations mais pour cela le diviseur doit être connu à la compilation.

La division dans le cas général 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 inline du C[modifier | modifier le code]

Le mot clef inline attaché à une fonction indique au compilateur qu'il devrait essayer d'étendre cette fonction. Considérons par exemple 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, en assembleur i386 :

         .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 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 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)

Notes et références[modifier | modifier le code]

  1. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
  2. (en) « Memory Optimization », sur redis.io (consulté le 25 mars 2020)

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]