Optimisations en langage C

Quand

Ou

Comment

Code

Quand optimiser ?

"premature optimization is the root of all evil"

Dr. Donald Knuth

REGLE A RESPECTER OBLIGATOIREMENT :

Optimiser un programme n'a lieu qu'en dernier recours, une fois que le programme s'exécute et donne le résultat escompte.

Ensuite SEULEMENT, et SEULEMENT SI la vitesse est un problème, optimiser, mais SEULEMENT le code qui en a réellement besoin.

Corollaire 1: Optimiser le code qui ne marche pas est inutile.

Corollaire 2: Optimiser le code qui ne pose pas de problème de vitesse est inutile.

Axiome de base des cette règle : Un code optimise est beaucoup, beaucoup plus dur a maintenir. Et en general la premiere source de bogues.

Quel type d'optimisation appliquer?

En premier lieu, il faut apporter le plus grand soin aux algorithmes choisi, utiliser des implentations de référence ou se plonger dans les livres de D. Knuth. Au besoin, il faut pouvoir prouver mathématiauement son choix. Vérifier son analyse du probleme et l'adéquation de sa solution.

Ensuite il faut tester les optimisation du compilateur.

Le codage optimisé pour inconvénient principal qu'il défigure le code source, rendant beaucoup plus difficile sa lecture et sa maintenance.

La "règle" est que l'on peut peux gagner un facteur 1000 avec un bon algorithme et au maximum un facteur 10 avec du codage optimisé.

Chemins d'optimisations

Détecter la lenteur

D'abord et avant tout, il faut trouver les bouts de code et les goulot d'étranglement du code, pour savoir ce qu'il faut optimiser

Plusieurs solutions:

• Utiliser des outils de profiling : gcc -pg, gprof, valgrind-cachegrind, etc.
• Utiliser des bancs de mesures en appelant les fonctions suspecte un grand nombre de fois en mesurant le temps global avec des outils systèmes (time)
• Utiliser des Timers ultra-précis pour compter les temps d'exécution. (GetTickCount() n'est précis qu'a 10 ms près, mieux vaut utiliser gettimeofday() sous linux, et QueryPerformanceCounter pour Win32)

Opérations Lentes

• Ouvrir un fichier
• Écrire un fichier (particulièrement dans un ordre non-linéaire),
• Lire beaucoup de données (particulièrement dans un ordre non-linéaire),
• Créer un nouveau processus,
• Rechercher,
• Trier,
• Opérations globales sur des tableaux
• Copier des gros paquets de données
• Écrire directement a l'écran.
• Opérations multiples et répétées sur des variables globales ou statiques

Opérations Rapides

• Assigner une variable
• ajouter des entiers
• de-référencer un pointeur

"inlining"

Avec gcc : -finline-functions

Si nécessaire, des fonctions C peuvent être re-codées comme des macros pour obtenir le même effet que l'"inline" sur les compilateurs,

Attention toutefois :

• Le faire sans raison pour toutes le fonctions va générer une programme inutilement gros en mémoire et plus le programme est gros, moins il aura de chances de tenir en mémoire cache, transformant l'optimisation en "ralentisseur de code".
• Les Macros en C "évaluent" leur arguments a chaque fois que l'argument est mentionne dans la macro... Si l'argument est une expression complexe ou un appel de fonction, le processeur va chauffer et le risque d'effet de bord de multiples appels de fonction va rendre le programme moins sur.
• Comme les macros peuvent être complexe, les optimiseurs ont du mal a générer du bon code... Donc limiter la complexité d'une macro assurera une meilleure optimisation (ne pas oublier qu'il existe bien souvent une limite sur le nombre de caractères d'une macro)
• Les "profiler" ne voient pas les macros, du coup optimiser une macro est difficile.

Pour toujours plus d'optimisation, il reste le code dépendant très fortement du processeur (mmx, 3dnow, etc), ou en assembleur ou avec des hacks.

Quelques optimisations:

règles générales

• Éviter les variables globales autant que possible.
• Utiliser le mot clef "static" pour toutes les fonctions ou variables internes a un fichier
• La Recursivité ne doit s'appliquer qu'au fonctions avec peu de paramètres et de variables
• Utiliser les fonctions les plus spécifique possibles (puts plutôt que printf, alloca plutôt que malloc)
• Utiliser l'allocation dynamique pour les cas ou vous n'avez aucune idée de la taille memoire de votre variable. Si une variable est bornée pour 90% de son utilisation utiliser une allocation statique pour ces 90% et un test pour passer en allocation dynamique pour les 10% restants.
• Utiliser les optimisations du compilateur.

Les Bases

Utiliser des tableaux pour les choix multiples :

switch ( queue )

 {

   case 0 : letter = 'W';

        break;

   case 1 : letter = 'S';

       break;

   case 2 : letter = 'U';

      break;

}

ou

if ( queue == 0 )

     letter = 'W';

else if ( queue == 1 )

      letter = 'S';

else

     letter = 'U';

Devient :

static char *classes="WSU";

letter = classes[queue];

Utiliser des variables locales pour accélérer les accès aux variables pointées

void func1( int *data )

{

     int i;

   for(i=0; i<10; i++)

        {

        somefunc2( *data, i);

        }

}

Même si data ne change pas, le compilateur ne peux pas le deviner en conséquence, la variable pointe par *data ne sera pas mise en cache :

void func1( int *data )

{

   int i;

   int localdata;

   localdata = *data;

    for(i=0; i<10; i++)

        {

             somefunc2( localdata, i);

         }

}

Les compteurs de boucles

Utiliser des "register unsigned int" comme compteurs (for et while). Plus rapide, plus sur et auto-documente le code.

Par exemple, un

#define compteur register unsigned int

dans le fichier d'include global

Peur d'être bloque pour réutiliser la variable dans d'autres calculs ?

Ne faites pas l'économie de variables servant a plusieurs actions différentes, cela complique le code et n'optimise rien du tout, car ces optimisations seront de toute façon faites par le compilateur.

Boucles

Minimiser les boucles, groupez les si possibles, et surtout si vous les imbriquez, vérifier bien si vous ne pouvez pas l'éviter.

for(i=0; i<100; i++)

{

stuff();

}

for(i=0; i<100; i++)

{

morestuff();

}

devient :

for(i=0; i<100; i++)

{

stuff();

morestuff();

}

Quelques fois, si le code dans les boucles est minuscule, il sera mis en cache du processeur et donc deux boucles pourrait être plus rapides.

"Loop Unrolling" et "Dynamic Loop Unrolling"

Le déploiement de boucles accélèrent leur exécution, mais augmentent la taille du binaire genere.

(souvent, optimiser implique utiliser plus de mémoire)

for(i=0; i<3; i++)

{

something(i);

}

est moins rapide que

something(0);

something(1);

something(2);

Incrémentation de boucle

En utilisant ++i plutôt que i++ dans une boucle

while (i++)

{}

le code genere sera plus petit et plus rapide (surtout en C++):

En effet i++ donne :

stocke la valeur i dans une variable temporaire

Évalue l'expression contenant i en utilisant la variable temporaire

Incrémente i

Tandis que ++i donnera:

Incrémente i

Évalue l'expression contenant i

Structures, Passage par référence

Tant que possible, passer les structures par référence aux fonctions mafunc(&structvar) pour éviter une recopie complète de la structure a chaque appel, et pour éviter toute modification utiliser "const" pour empêcher toute modification par la fonction.

void mafunc ( const mastruct *structvar)

{...}

Utiliser Break

Exécuter l'intégralité des itérations d'une boucle n'est pas toujours indispensable, dans ce cas break permet de s'en sortir facilement et de gagner du temps d'exécution sans rajouter de test supplémentaire.

while (i<10000)

{

   if( estbonne (valeur[i]) )

   {

     trouve = TRUE;

   }

    i++

}

devient :

while (i<10000)

{

  if ( estbonne (valeur[i]) )

      break;

 i++

}

Code

Algorithmes et structures

Implémentation classique	Implémentation optimisée
array	hashtables
sequential search	binary search / hash lookup
quicksort	merge sort, radix sort
Bresenham	lines DDA fixed point

Opérateurs Binaires (Attention dépend de l'architecture machine)

Opérations classiques	Optimisations binaires pour cpu "high endian"
x = y % 32;	x = y & 31;
x = y * 8;z = y * 33;	x = y << 3; z = (y << 5) + y;
x = y / w + z / w;	x = (y + z) / w;
if (a == b && c == d && e == f )    {...}	if ( ((a-b)|(c-d)|(e-f)) == 0 )    {...}
if ((x & 1) || (x & 4) )    {...}	if ( x & 5 ) {...}
if ( x>=0 && x<8 && y>=0 && y<8 )    {...}	if (((unsigned int) (x | y)) < 8 )     {...}
if ( (x == 1) || (x == 2) || (x == 4) || (x == 8) || ...)	if ( x & (x-1) == 0 && x != 0 )
#define abs(x) \ (((x)>0)?(x):-(x))	static long abs (long x) { long y; y = x>>31; return (x^y)-y;
c = a; a = b; b =a;	a ^= b; b ^= a; a ^= b;
x = y / 4;	x = y >> 2;