Optimiser l’utilisation de la mémoire : les enseignements de 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 mémoire 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 de grandes quantités de données, elle peut être exposée au thrashing et ralentir considérablement. Deux solutions sont possibles : optimiser l'application pour utiliser la mémoire plus efficacement, ou ajouter davantage de RAM physique au système.

Voyons quelle solution Doxygen utilise pour optimiser l'utilisation de la mémoire et éviter le 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 requises et stocke les résultats dans des instances des classes 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 courant 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 rechargées en mémoire lorsqu'on en a de nouveau besoin.

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.
• Lorsque 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 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 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 impacter les performances de votre cache.
• De la taille maximale du cache.
• De l'algorithme utilisé pour retirer des entrées du cache. Lorsque le cache atteint sa taille maximale, 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 dans le fichier de configuration :

int cacheSize =Config_getInt("SYMBOL_CACHE_SIZE");

Rendre ce paramètre configurable est utile, car sur une machine dotée d'une grande quantité de mémoire physique, vous pouvez augmenter la taille du cache pour améliorer les performances. 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 par presque toutes les méthodes de 

. Elle est appelée chaque fois que l'état de 

doit être consulté. Elle vérifie si le membre est chargé, le charge si nécessaire, et retire du cache le membre le moins récemment utilisé.

L'avantage de l'utilisation du cache

L'utilisation d'un cache peut améliorer les performances d'une application, mais apporte-t-elle un bénéfice significatif, ou s'agit-il simplement d'une micro-optimisation qui ne vaut pas la complexité ajoutée ?

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, le processus peut prendre des heures et affecter significativement les performances du système.

Conclusion

L'utilisation d'un cache peut améliorer significativement 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 un cache pour ses propres applications.