Trouver un livre, un site internet, ou toute autre source de documentation sur la programmation en langage C est très aisé. Trouver des informations sur l'optimisation de codes en langage C est une toute autre affaire. C'est donc là la raison de la présence de cet article sur Onversity. La seconde raison est qu'en abordant les optimisations de codes, on va aborder des aspects techniques de la compilation qui vont vous permettre de mieux comprendre ce qui se passe réellement et quelles sont les limites des compilateurs et pourquoi, à certains moments.

Cet article a une particularité. Tout le monde est invité à y participer et peut en écrire un paragraphe auquel son nom sera accolé. De fait cet article sera toujours en cours d'évolution, mais j'espère qu'on arrivera à mettre les principaux éléments dedans rapidement pour qu'il puisse devenir un outil pratique et utile.

Bonne lecture :)

Vous entendez beaucoup parler d'optimisation de codes sur internet, par le biais des actualités sur les drivers, des locigiels de codage et décodage vidéo, de moteurs de base de données. Mais c'est l'arbre qui cache la forêt. De nombreuses applications que vous pouvez être amené à utiliser quotidiennement ne le sont pas. Parfois ce sont les outils qui sont de mauvaise qualité mais qui surtout ont un problème de code. Il pourrait être tentant de dire que les développeurs de ces applications ne sont pas compétents mais ça serait faire une terrible erreur. Il y a un mal plus profond qui touche à l'état d'esprit des développeurs sur le sujet de l'optimisation. Je vais laisser parler Steve Oualline qui donne très bien sa propre position et celle d'une grande partie des développeurs.

Soyons clairs : dans 99% des cas il est inutile - voire nuisible - de tenter d'optimiser un programme et les efforts consacrés à réduire le temps de réponse de quelques dixième de seconde sont rarement justifiés.

Certes, il existe bon nombre de programmes exceptionnellement lents qui mériteraient l'implémentation de nouveaux algorithmes.

Ce qu'exprime ce développeur et auteur de livres est une pensée connue de tous les développeurs. Essayons de la décortiquer un peu. La première affirmation consiste finalement à dire que l'optimisation ne sert à rien, pire elle est nuisible. Nuisible pour qui ? Pour les utilisateurs ? Certainements pas. Pour les développeurs ? S'ils sont sous contrat alors effectivement se lancer dans des optimisations cela peut amener à des retards de production et donc à des sanctions. Mais le terme est laché : production. Toute l'origine de cette histoire provient d'une volonté de ne pas perdre de temps pour produire. Ce qu'exprime cet auteur est typiquement un point de vue d'éditeurs dont le seul objectif est de produire un logiciel, qu'il soit lent n'est pas sa préoccupation. Cela est tellement vrai que quand un logiciel est particulièrement lent alors qu'il ne le devrait pas on reporte la faute sur le matériel soit disant obsolète ou peu adapté de l'utilisateur. Belle état d'esprit que voila !

En second l'auteur exprime à nouveau un avis partagé par bon nombre de développeurs. Tous ? certainement pas. Cet avis consiste à affirmer que seules les optimisations algorithmique valent la peine. En pratique j'ai pu constater que cet avis est majoritaire dans les milieux universitaires ou issu de ce milieu. Ce n'est pas qu'elle ne serait pas le faire, mais l'optimisation algorithmique à un fondement mathématique, et comme telle est placée au-dessus de tout. Malheusement au détriment des autres.

Toutefois il ne faut pas non plus tomber dans le travers de vouloir à tout prix faire de l'optimisaiton de code. Il faut savoir rester raisonnable. Essayons d'y voir un peu plus clair sur le sens qu'a le fait d'optimisation un code de nos jours en particulier face au compilateur moderne et a l'optimisaiton algorithmique.

Certaines personnes estiment que l'optimisation manuelle est une perte de temps. Ils pensent soit que le compilateur sait mieux optimiser un microprocesseur, soit que l'optimisation de code n'a pas de sens, mais que par contre l'optimisation algorithmique est plus utile. Pour ce second cas, nous le traiterons dans le paragraphe suivant, quant au premier voyons ce qu'il en est.

Il est tout à fait vrai que les compilateurs ont fait un certain nombre de progrès depuis ces dix dernières années, de même il est vrai que les microprocesseurs modernes intègrent des mécanismes parfois très complexes qu'il est difficile de maîtriser / comprendre parfaitement pour la très grande majorité des développeurs. Ceci étant posé, il ne faut pas oublier qu'un compilateur est un automate, et qu'en tant que tel son intelligence est limitée et qu'il fait ce qu'on lui demande de faire. Dans le premier cas tout développeur qui optimise du code apprend qu'en organisant des instructions de telle ou telle manière il peut grandement aider un compilateur à mieux optimiser le code, dans le second cas si vous lui demandez de calculer en valeur entière i = i + i - i + 1 - 1, il le fera. Un compilateur ne peut en aucun cas se substituer à certaines optimisations de codes et il y en a souvent bien plus que certains ne le croient.

Pour terminer il existe, quoiqu'on en dise, des personnes réfractaires à l'optimisation de code. S'il cela peut être compréhensible dans certaines situations particulières (certains programmes, certains algorithmes), dans l'ensemble je trouve cette démarche très conservative, voire inquiétante. Effectivement, il est en pratique assez désastreux qu'un développeur ne maîtrise pas ou trop mal les mécanismes des microprocesseurs et des compilateurs. Or ceux-ci s'acquièrent en grande partie lorsqu'on pratique l'optimisation de code.

Quelle que soit l'optimisation de code que vous ferez, cela ne vous permettra d'avoir qu'un gain linéaire d'un point de vue de la complexité algorithmique de votre programme. Ces gains ne dépassent que très rarement un facteur 2. Par contre l'optimisation algorithmique vous permet d'avoir non seulement parfois des gains importants pouvant dépasser un facteur 2, mais aussi alléger la complexité et rendre votre programme d'autant plus rapide qu'il y a un grand nombre de données à traiter.

La question est donc : quel intérêt d'optimiser le code si une optimisation algorithmique permet un gain bien meilleur ? La réponse est simple, une fois que vous avez fait l'optimisation algorithmique, vous pouvez encore pousser plus loin la vitesse d'exécution de votre code en faisant de l'optimisation de code.

Encore une fois on se peut demander quel est l'intérêt de gagner 5% ou 10% à un code ? Il est clair qu'il y a quelque chose de l'ordre de la conception que l'on se fait de la programmation. Il y a évidemment le défi de faire toujours mieux, mais il y a aussi le principe de travail bien fait où on donne le maximum de soi-même pour satisfaire les besoins des utilisateurs. C'est donc une démarche intellectuelle et personnelle. Maintenant ceux qui s'imaginent que faire de l'optimisation de code consiste à passer de longues nuits blanches en interchangeant 2 lignes de programmation pour voir quelle configuration le compilateur arrive le mieux à optimiser vont être déçus. Il existe un certain nombre de trucs et d'astuces qui, utilisés dès l'écriture des premières lignes d'un code, vous assureront d'un minimum d'optimisations de code.

un dernier point. Il faut se méfier des optimisations algorithmiques. La calcul de la complexité est basé sur le concept de limite. On fait tendre à l'infini le nombre d'itération de l'algorithme et/ou le nombre d'opération. Mais dans la pratique on ne tend pas vers un nombre infini d'opération. C'est ainsi que le programme de calcul la plus rapide de grand nombre que j'ai pu voir était un programme avec une complexité en 0(n²) alors que normalement ce sont les algorithmiques avec une compelxité en O(n*ln) qui le sont. Ce paradoxe s'explique par le fait que si on ne calcul des grands nombres qu'avec quelques dizaine ou centaine de chiffres l'affirmation est vrai mais pas si on calcul avec un nombre n de chiffres avec n très grand. Ce qu'il faut retenir est qu'il ne faut pas utiliser l'algorithme le plus performant en terme de complexité nécessirement, mais celui qui est le plus performant avec les données que vous avez à traiter.

Prenons le cas d'une fonction date qui doit transformer le mois donné comme un entier en un mois alphabétique. On crée donc un tableau qui contient les 12 mois de l'année. Parfait jusque là. A présent il faut afficher une liste de textes avec leur mois de création en appelant notre fonction date. A chaque fois qu'on l'appelle elle recrée le tableau des mois en lettre. Là c'est moins parfait.

L'idéal serait que le programme conserve en mémoire l'initialisation de la table faite lors du premier appel. C'est ce que permet de faire le mot 'static' si on le place juste devant le type de la variable. Exemple :

Il faut bien comprendre que 'static' est d'autant plus efficace qu'on appelle souvent notre fonction. Par contre appeler une seule fois 'static' n'a aucun intérêt.

Static est une classe de mémorisation, c'est a dire qu'il indique au compilateur comment doit être géré l'espace allouer a une variable. Il y a aussi : extern, et register.

Placer 'const' devant une déclaration d'une variable ne produit pas directement d'optimisation. par contre il indique au compilateur que la variable ne sera pas modifiée. C'est très utile au compilateur, car certains algorithmes d'optimisation dont ils disposent ne peuvent être activés que s'ils sont assurés que les données ne seront jamais modifiées. Utiliser 'const' c'est donc s'assurer que le compilateur pourra mettre en oeuvre toutes les optimisations envisageables. Son utilisation est la suivante

Const int toto=5;

void fonction(const char *source);

Dans la pratique, je dois avouer que si j'utilise const quand cela est possible, je n'ai malheureusement aucun code exemple à vous donner qui vous montrerait un gain de performances. La raison est que je n'ai jamais pu mesurer un gain de performances en utilisant const. Cela dépend évidemment des compilateurs et du type de programme qu'on développe. Si quelqu'un a un exemple concret qu'il se fasse connaître :).

Const apporte quand même un petit plus en terme de lisibilité de programme. Const est un qualificateur comme volatile. Il indique au compilateur comment se comporte la variable. l'autre qualificateur est volatile.

Pour utiliser un pointeur, on a recourt àla fonction malloc pour allouer un espace mémoire nécessaire au contenu que pointe le pointeur. Dans la même logique, on peut utiliser un malloc pour allouer un espace à l'adresse que pointe le pointeur de pointeur. On a donc

char **ptr;

ptr = (char **) malloc(sizeof(char *));

Le problème c'est que faire un malloc ça prend du temps alors évidemment proportionnellement au type de contenu (4 octets pour du code 32 bits) ça fait assez lourd. sans compter le free (ptr) qu'il faudra faire. La solution est la suivante :

char *ptr[1];

Vous n'avez plus besoin de malloc ni de free pour déclarer votre pointeur de pointeur. Voici quelques exemples d'utilisation :

ptr[0] = (char *) malloc(x); // affectation d'une zone mémoire au pointeur

fonction((char **) ptr); // passage de paramètre de ptr

Tant que notre pointeur de pointeur ne pointe que sur un seul autre pointeur cette solution reste viable, mais s'il pointe sur un tableau de pointeur alors on se retrouve avec le même problème que de savoir s'il faut utiliser un tableau ou un pointeur. On ne pourra donc pas dans certains cas utiliser la forme *ptr[n] ou n > 1. Prenons comme exemple la gestion des caches des enregistrements d'Hydrogen. Le nombre d'enregistrements d'une base à une autre peut avoir un rapport de 1 à 1000. Il est donc déraisonnable de penser faire un pointeur *cache[10000000] par exemple alors que seule une base peut potentiellement contenir autant d'enregistrements. Cela signifierait pour les autres qu'on réserve plusieurs Mo pour gérer quelques enregistrements. La solution *ptr[n], n'est donc viable que lorsqu'on manipule des objets statiques en nombre / taille.

Les compilateurs, en règle générale, n'apprécient pas les pointeurs. Pourquoi ? Parce que comme tant leur l'adresse qu'ils contiennent, tant les données pointées vers cette adresse peuvent être modifiées à tout instant. La deuxième raison est que dans le cas de tableau ou structure, chaque élément peut avoir une taille différente. Or les compilateurs aiment bien avoir des structures où la position du prochain emplacement peut être connu par une simple opération arithmétique et non en accédant à une zone mémoire qui donne la position d'un contenu. De fait utilisez toujours des tableaux de taille fixe.

A quoi servent les pointeurs d'un point de vue optimisation alors ? En utilisant que l'espace mémoire nécessaire, ils permettent souvent de réduire considérablement l'espace mémoire utilisée. Dans certaines situations, c'est un atout en terme d'optimisation. Par exemple vous développez un script pour un serveur internet. Sans pointeur, ce script utilise 4 Mo et avec 1 Mo. Si votre serveur est équipé de 1 Go de RAM, vous pourrez avoir 1000 fois ce script en mémoire (en théorie, la pratique c'est autre chose), alors que sans pointeur, vous serez limité à 250. Bien sûr il y a la mémoire swap, qui permet d'étendre la quantité de mémoire disponible, mais on se heurte alors à d'importants ralentissements. Dans certaines situations, l'utilisation des pointeurs peut amener un gain de l'utilisation des mémoires caches.

Les pertes de performances les plus importantes que l'on peut constater dans le cas des pointeurs sont les structures. Si elles sont assez importantes, et leurs données souvent utilisées en proportion du reste du programme, l'utilisation des pointeurs doit être mûrement réfléchie.

Au final, l'utilisation des pointeurs ne doit se faire dans une problématique de programme optimisé, ne doit se faire que s'ils permetttent un gain important ou absolument nécessaire de place mémoire. On peut devoir aussi les utiliser pour d'autres raisons, mais celles-ci n'ont rien à voir avec des problématiques d'optimisation mais d'exécution.

Les conditions de branchement peuvent poser parfois de gros ralentissements. Deux solutions existent. L'une est la méthode des tableaux, l'autre d'avoir de l'astuce. La première est une technique classique, la seconde demande perspicacité et souvent persévérance.

La technique du tableau est utile quand vous avez un branchement qui s'effectue en fonction de plusieurs tests (au moins 3 ou 4 en fonction des circonstances). Toutefois elle se restreint souvent aux tests de comparaison avec des char. Pourquoi ? Parce que les char sont un ensemble fini assez petit. Cette technique est particulièrement efficace dans les filtres. Nous allons utiliser justement un filtre de caractère après saisie d'un champ.

Si on avait du faire des comparaisons pour chaque caratère ou par intervalle de de caractère le filtre aurait été 10 fois plus lent sinon plus. Vous contaterez que j'ai utilisé static const pour la déclaration du tableau.

Pour les astuces, je peux vous donner un exemple mais pas vous dire comment avoir de l'astuce. L'exemple que je vais donner consiste dans la fonction strcmp() que nous allons réécrire. La fonction strcmp() teste si deux chaines sont égales. Si oui elle renvoie 0 si non elle renvoie la différence entre les deux caratères qui sont différents. A cela s'ajoute un double test à faire pour savoir si l'on n'est pas arrivé à la fin d'une des deux chaines puisqu'il est posible que les chaines n'aient pas la même taille. On obtient donc la fonction suivante :

On fait donc 3 tests à chaque passage dans la boucle. Avec un peu d'astuce il est possible de réduire à deux tests.

Trouver ce genre d'astuces est parfois evident d'autres fois non mais l'astuce utilisée pour strcmp() permet un gain d'environ 25% ce qui est loin d'être négligeable.

Cet article se veut collectif. Si vous souhaitez corriger, améliorer un chapitre aucun problème. si vous voulez ajouter un chapitre aucun problème non plus. Cet article est un outil destiné à tous et accessible à tous de manière totalement libre. En fait le plus gros problème n'est pas d'écrire cela, mais de vous convaincre de participer. Alors, allez-y ! :).