Optimiser la mémoire en C++ : étude de cas Doxygen

Lorsque les processus exécutés sur votre machine tentent d'allouer plus de mémoire que votre système n'en a de disponible, le noyau commence à déplacer des pages de mémoire vers et depuis le disque (swap). Cela permet de libérer suffisamment de mémoire physique pour satisfaire les besoins d'allocation de RAM du demandeur.

L'utilisation excessive du swap 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 traiter une grande quantité de données, elle peut être exposée au thrashing et ralentir considérablement. Deux solutions existent : soit optimiser vos applications pour utiliser la mémoire plus efficacement, soit ajouter davantage de RAM physique au système.

Découvrons quelle solution Doxygen utilise pour optimiser son utilisation de la mémoire et éviter le problème de thrashing.

Doxygen est l'outil standard de facto pour générer de la documentation à partir de sources C++ annotées, mais il prend également en charge d'autres langages de programmation populaires comme C, Objective-C, C#, PHP, Java, Python et bien d'autres. Un grand merci à Dimitri van Heesch pour son formidable travail de développement et de maintenance du projet.

Doxygen prend les fichiers sources en entrée, les analyse pour extraire les données nécessaires et stocke le résultat dans des instances de classes du 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, le stockage de 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 fondée sur un cache ; l'utilisation d'un cache est un moyen populaire d'optimiser l'utilisation de la mémoire. L'idée est de stocker dans un cache les données qui ont besoin d'être en mémoire. Ce cache contient de nombreux emplacements (slots), chacun contenant une donnée spécifique. Certains emplacements sont libérés lorsque le cache dépasse une certaine taille. Les données libérées sont déplacées vers le disque, et si l'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éfinir un cache avec 65 535 emplacements.
• Lorsqu'une instance de MemberDef doit être créée, Doxygen vérifie si un emplacement du cache est disponible. Si c'est le cas, 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 enregistrer où ces données sont stockées dans le fichier de données.
• Si Doxygen a besoin d'accéder à une instance de MemberDef, il vérifie si elle est présente dans le cache. Si elle n'y est pas, Doxygen lit dans le fichier d'index l'emplacement où ses données sont stockées, se positionne à cet endroit dans le fichier de données et la charge depuis le disque.

Les performances du cache dépendent :

• Du conteneur : ce peut être une file, un tableau, une liste, ou peut-être un conteneur personnalisé. Le choix du conteneur peut affecter les performances du cache.
• De la taille maximale du cache.
• De l'algorithme utilisé pour libérer des entrées du cache. Lorsque le cache atteint son maximum, il faut décider quelles entrées libérer. Par exemple, vous pouvez :
  • 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'objets 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 depuis le fichier de configuration :

int cacheSize =Config_getInt("SYMBOL_CACHE_SIZE");

C'est une bonne idée de rendre 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 plus 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 de libération des entrées du cache

Voici l'extrait de code du code source de Doxygen responsable de la libération des entrées du cache lorsque celui-ci atteint son maximum :

Comme précisé dans la 

le code de la méthode, 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 pour presque toutes les méthodes de 

; elle est appelée chaque fois qu'il faut accéder à l'état de 

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

L'utilisation d'un cache peut améliorer les performances de votre application, mais s'agit-il d'une optimisation importante, ou seulement d'une micro-optimisation qui ne vaut pas la peine d'être ajoutée à votre application ?

Avant d'utiliser Clang comme parseur C/C++ pour notre produit, nous avons utilisé Doxygen comme parseur pour notre première version. Nous avons effectué 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 augmenté de façon spectaculaire, passant parfois de 5 minutes à 25 minutes. Pour les grands projets, cela peut prendre des heures et affecter significativement les performances du système.

Conclusion

L'utilisation d'un cache est un moyen puissant d'améliorer les performances d'une application lorsqu'on travaille avec de grandes quantités de données. Explorer la manière dont les projets open source implémentent leurs caches peut être très utile lorsqu'on conçoit le sien pour ses propres applications.