Optimisation de 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.

Plusieurs approches existent pour optimiser un code :

• au niveau algorithmique, en choisissant un algorithme de complexité mathématique inférieure 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, qui peut être le langage C ou, pour les besoins les plus critiques, le langage assembleur.

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.

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

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

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 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 (${\displaystyle 10_{2}}$) décalé de 1 bit donne 4 (${\displaystyle 100_{2}}$).

5 (${\displaystyle 101_{2}}$) décalé de 2 bits donne 20 (${\displaystyle 10100_{2}}$) : ${\displaystyle 5*2^{2}=20}$.

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

100 (${\displaystyle 1100100_{2}}$) décalé de 3 bits vers la droite donne ${\displaystyle 100/2^{3}=12.5}$ donc 12 (${\displaystyle 1100_{2}}$) 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 ${\displaystyle \mathbb {Z} /2^{32}\mathbb {Z} }$ par exemple. Et donc, tous les nombres premiers avec ${\displaystyle 2^{32}}$ 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 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)

• The Fallacy of Premature Optimization by Randall Hyde expliquant la citation de Donald Knuth et sa mauvaise interprétation
• Premature Optimization by Charles Cook sur cette même citation de Donald Knuth.