Optimisations en langage C
| Quand | Ou | Comment | Code |
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; |
"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.
Suggestions ?