En programmation C++, l’optimisation ne se limite pas à retoucher le code pour gagner en performance. Elle repose fondamentalement sur des choix de conception judicieux. Voici pourquoi :
- Le choix des algorithmes: Le choix d’un algorithme peut radicalement affecter les performances. Utiliser un tri en O(n log n) plutôt qu’en O(n²) en est l’exemple type.
- Les structures de données: Choisir la bonne structure de données (par exemple une table de hachage plutôt qu’une liste chaînée pour des recherches rapides) peut apporter des gains d’efficacité significatifs.
- La gestion de la mémoire: Une utilisation efficace de la mémoire et la minimisation des allocations/désallocations peuvent améliorer les performances. Des techniques comme le pooling mémoire ou l’usage approprié des pointeurs intelligents peuvent faire une grande différence.
- La concurrence et le parallélisme: Concevoir des systèmes qui exploitent efficacement plusieurs threads ou processus peut améliorer les performances. C++11 a introduit le support standard des threads, ce qui y contribue.
- Éviter l’optimisation prématurée: Se concentrer d’abord sur un code propre et maintenable, puis optimiser les sections critiques ensuite, est généralement plus efficace.
Étude de cas Doxygen : combattre le thrashing mémoire par des choix de conception
Lorsque les processus de votre machine tentent d’allouer plus de mémoire que le système n’en a de disponible, le noyau commence à échanger des pages mémoire vers et depuis le disque. Cela permet de libérer suffisamment de mémoire physique pour répondre aux besoins d’allocation de RAM du demandeur.
L’usage excessif du swapping s’appelle le thrashing ce qui est indésirable, car cela dégrade les performances globales du système, les disques durs étant bien plus lents que la RAM.
Si votre application doit manipuler une grande quantité de données, vous serez exposé au thrashing et votre application pourrait ralentir considérablement. Il existe deux solutions : soit optimiser votre application pour utiliser la mémoire plus efficacement, soit ajouter de la RAM physique au système.
Découvrons quelle solution Doxygen utilise pour optimiser son usage mémoire et éviter le problème du thrashing.
Doxygen est l’outil standard de facto pour générer de la documentation à partir de sources C++ annotées, mais il supporte aussi d’autres langages populaires comme C, Objective-C, C#, PHP, Java, Python et bien d’autres. Merci à Dimitri van Heesch pour son formidable travail de développement et de maintenance du projet.
Doxygen prend en entrée les fichiers sources, les analyse pour extraire les données nécessaires, et stocke le résultat dans des instances de classes de type DirDef, FileDef, NamespaceDef, ClassDef et MemberDef. Toutes héritent de la classe Definition.
Les instances de ces classes seront ensuite utilisées pour générer la documentation. Les données qui consomment le plus de mémoire sont les informations sur les méthodes et les variables, représentées par la classe MemberDef. La taille de ces instances peut dépasser 1 Go, selon le nombre de méthodes et de variables des projets traités.
Pour certains projets, stocker toutes ces instances en mémoire peut affecter les performances du système, et la génération de la documentation peut prendre de nombreuses heures.
Comment Doxygen optimise-t-il la mémoire ?
Doxygen utilise une solution basée sur un cache disque ; utiliser un cache disque est un moyen populaire d’optimiser l’usage mémoire. L’idée est de stocker sur disque des données qui devraient sinon rester en mémoire ; ce cache contient de nombreux emplacements, chacun contenant une donnée spécifique, et certains emplacements sont libérés si la taille du cache dépasse une certaine valeur. Les données libérées restent présentes sur disque et, si on en a de nouveau besoin, elles sont rechargées en mémoire.
Dans le cas de Doxygen, l’algorithme est très simple :
- Définit un cache de 65 535 emplacements.
- Lorsqu’une instance de MemberDef doit être créée, Doxygen vérifie si un emplacement du cache est disponible ; si oui, l’instance est créée en mémoire ; sinon, elle est stockée dans un fichier de données sur le disque, et un fichier d’index est mis à jour pour mémoriser où ces données sont stockées dans le fichier.
- Si Doxygen doit accéder à une instance de MemberDef, il vérifie sa présence dans le cache. Si elle n’y est pas, Doxygen utilise le fichier d’index pour déterminer où les données sont stockées, se positionne à cet endroit dans le fichier de données et les charge depuis le disque.
Les performances du cache dépendent de :
- Le conteneur : ce peut être une file, un tableau, une liste ou un conteneur personnalisé. Le choix de l’un de ces conteneurs peut impacter les performances de votre cache.
- La taille maximale du cache.
- L’algorithme utilisé pour évincer des entrées du cache. Quand le cache atteint son maximum, il faut décider quelles entrées libérer ; par exemple, on peut :
- Libérer les premiers emplacements chargés.
- Libérer les derniers emplacements chargés.
- Libérer les emplacements les moins utilisés.
1- Le conteneur
Doxygen définit la classe ObjCache, qui est une liste chaînée d’instances de CacheNode ; cette classe est responsable de l’ajout et de la suppression d’instances dans le cache.
Voici comment Doxygen déclare son cache :
Doxygen::symbolCache =new ObjCache(16+cacheSize);// 16 -> room for 65536 elements, 2- La taille du cache
Doxygen récupère la taille maximale du cache dans le fichier de configuration :
int cacheSize =Config_getInt("SYMBOL_CACHE_SIZE");C’est une bonne idée de laisser ce paramètre configurable, afin de pouvoir augmenter le cache si vous disposez d’une machine avec une grande quantité de mémoire physique, et ainsi améliorer les performances du cache. Cependant, dans les versions récentes de Doxygen, ce paramètre a été retiré du fichier de configuration et une valeur par défaut est utilisée.
3- L’algorithme d’éviction des entrées du cache
Voici l’extrait du code source de Doxygen responsable de la libération du cache lorsqu’il atteint son maximum :
Comme indiqué dans le code de la méthode makeResident, très bien commenté, l’élément le moins récemment utilisé est supprimé si le cache est plein.
Cette méthode est invoquée par presque toutes les méthodes de MemberDef ; elle est appelée chaque fois qu’il faut accéder à l’état d’un MemberDef pour vérifier si ce membre est chargé ou non, le charger si ce n’est pas le cas, et retirer du cache le membre le moins récemment utilisé.
L’impact de l’utilisation du cache
Utiliser un cache peut améliorer les performances d’une application, mais s’agit-il d’une optimisation significative, ou d’une simple micro-optimisation qui ne vaut pas la complexité ajoutée ?
Avant d’utiliser Clang comme parseur C/C++ pour notre produit, nous utilisions Doxygen comme parseur dans notre première version. Nous avons fait de nombreux tests sur la taille du cache ; lorsque nous avons désactivé le cache et analysé certains projets C++ avec cette version modifiée, le temps d’analyse a beaucoup augmenté, passant parfois de 5 à 25 minutes. Pour les gros projets, cela peut prendre des heures et affecter significativement les performances du système.
Conclusion
Une optimisation C++ efficace est profondément ancrée dans des choix de conception éclairés. En sélectionnant les bons algorithmes, les bonnes structures de données et les bonnes techniques de gestion mémoire, et en exploitant la concurrence lorsque c’est pertinent, les développeurs peuvent obtenir des gains de performance significatifs. C’est cette approche stratégique de la conception qui constitue la véritable force de l’optimisation en C++.