Optimisation de code - profiling

1. Introduction

L'optimisation de code est un très vaste sujet, et plusieurs aspects d'un programme informatique peuvent être optimisés. On peut par exemple réduire l'empreinte mémoire, augmenter la vitesse d'execution, agir sur la bande passante... Je m'intéresse ici plus particulièrement à l'optimisation de la vitesse d'execution du programme, en utilisant des outils de profiling pour mesurer le temps passé dans les différentes routines du code donné en exemple, et ainsi détecter les parties qui prennent un temps anormalement long pour s'exécuter.

2. Profiling

2.1 Définition

Avant de se lancer dans de longues recherches pour optimiser un programme, il est préférable d'identifier les parties du code qu'il est nécessaire d'optimiser. Pour ce faire, on peut utiliser des outils de profiling, qui vont nous indiquer le temps passé dans chaque partie du programme. On peut ainsi détecter si un processus prend un temps exagérément long pour s'executer, et donc se concentrer sur ce processus pour l'améliorer.

2.2 Outils

Les outils utilisés dans cet exemple sont la plupart du temps fournis dans les paquets de base des distributions Linux ou Unix. Il s'agit du compilateur gcc [1] et de gprof [2]. Pour obtenir des informations sur le déroulement d'un programme, une méthode simple consiste à utiliser l'option -pg avec gcc, puis à lancer gprof pour analyser les temps passés dans chaque routine du programme. J'ai rédigé ci-dessous un petit exemple simple d'une session de 'profiling', afin de montrer l'enchaînement des commandes.

Remarque: Dans cet article, la session de profiling montre l'exemple d'un programme écrit en C, mais une étude similaire est possible dans la majorité des langages de programmation. On peut utiliser par exemple le module Devel::Profiler [3] si on programme en Perl, ou bien un profiler basé sur JVMTI [4] si on utilise Java, ... Il suffit de trouver les outils développés pour son langage de prédilection!

2.3 Exemple

Il s'agit dans cet exemple de calculer la somme du premier million d'entiers naturels. Voici le code initial (notez bien la subtilité de l'algorithme ;) :

/* 
 * somme_entiers.c : 
 * calcul de la somme S des n premiers entiers naturels non nuls.
 * S = 1 + 2 + ... + (n - 1) + n 
 *   = n * (n + 1) / 2
 */ 

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define N       1000000

unsigned int calcul_somme(int borne_sup)
{
        unsigned int somme = 0 , pas , j = 1, i;

        while (j <= borne_sup) {
                pas = 10;
                while (j + pas > borne_sup) {
                        pas--;
                }
                if (pas == 0) break;
                for (i = 1; i <= pas; i++) {
                        somme += i + j;
                        usleep(1 / somme);
                }
                j += pas;
        }
        return somme + 1;
}

void affiche(long resultat)
{
        printf("La somme des %d premiers entiers est: %d\n",
            N, resultat);
}

int main()
{
        unsigned int resultat;

        resultat = calcul_somme(N);
        affiche(resultat);

        return EXIT_SUCCESS;
}

Compilons le programme, puis executons-le en chronométrant le temps mis pour le calcul de la somme des premiers nombres entiers:

$ gcc somme_entiers.c -o somme_entiers

$ time ./somme_entiers

La somme des 1000000 premiers entiers est: 1784293664

real    0m0.122s
user    0m0.110s
sys     0m0.010s

Le temps mis pour le calcul est de 0,122 secondes. Compilons maintenant le source avec l'option -pg, puis relançons le programme. Après l'execution, nous voyons apparaître un nouveau fichier: gmon.out, qui va servir à gprof pour effectuer son profiling.

$ gcc -pg somme_entiers.c -o somme_entiers

$ ./somme_entier

$ gprof ./somme_entier | less

Voici un extrait de la sortie de gprof:

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
100.00      0.05     0.05        1 50000.00 50000.00  calcul_somme
  0.00      0.05     0.00        1     0.00     0.00  affiche
  0.00      0.05     0.00        1     0.00 50000.00  main

Ce tableau nous indique le temps passé dans chaque routine du programme (colonne time pour avoir le pourcentage, et self pour avoir le temps réel), ainsi que le nombre d'appels à ces routines (colonne calls).

A l'évidence, nous passons beaucoup de temps dans la fonction calcul_somme (c'est bien entendu trivial, mais c'est avant tout pour montrer l'enchaînement des commandes). Transformons un peu le code source et voyons si nous obtenons un meilleur temps d'execution:

/* 
 * somme_entiers.c : 
 * calcul de la somme S des n premiers entiers naturels non nuls.
 * S = 1 + 2 + ... + (n - 1) + n 
 *   = n * (n + 1) / 2
 */ 

#include <stdio.h>
#include <stdlib.h>

#define N 1000000

unsigned int calcul_somme(int borne_sup)
{
        unsigned int somme = 0, i;

        for (i = borne_sup; i--; ) 
                somme += i;
        return somme;
}

void affiche(long resultat)
{
        printf("La somme des %d premiers entiers est: %d\n",
            N, resultat);
}

int main()
{
        unsigned int resultat;

        resultat = calcul_somme(N);
        affiche(resultat);

        return EXIT_SUCCESS;
}

La commande time nous indique le temps d'execution suivant:

$ time ./somme_entiers

La somme des 1000000 premiers entiers est: 1783293664

real    0m0.027s
user    0m0.030s
sys     0m0.000s

Le temps mis pour le calcul est maintenant de 0,027 secondes, ce qui est un peu plus de quatre fois plus rapide qu'avec la précédente version du programme!

3. Conclusion

Utiliser un profiler nous a donc permis d'identifier rapidement l'endroit du programme qui pouvait être amélioré. Ce type de recherche est d'autant plus utile que le programme est long, et permet d'éviter de perdre du temps à optimiser une partie du code qui n'apportera pas un gain significatif en performance.

4. Ressources