Lorsque les processus qui s'exécutent sur votre machine tentent d'allouer plus de mémoire que ce dont dispose votre système, le noyau commence à transférer des pages mémoire vers le disque et inversement. Cela permet de libérer suffisamment de mémoire physique pour satisfaire les 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 traiter une grande quantité de données, elle peut être exposée au thrashing et ralentir considérablement. Deux solutions existent : soit optimiser votre application pour utiliser la mémoire plus efficacement, soit ajouter plus de RAM physique au système.
Explorons la solution qu'utilise Doxygen 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 aussi en charge 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 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 des types 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 totale de ces instances peut dépasser 1 Go, selon le nombre de méthodes et de variables dans les 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 ; utiliser un cache est un moyen populaire d'optimiser l'utilisation de la mémoire. L'idée est de conserver dans un cache les données qui doivent résider en mémoire. Le cache contient de nombreux emplacements, chacun contenant une donnée spécifique, et certains emplacements sont libérés lorsque le cache dépasse une certaine taille. Les données libérées sont déplacées sur le 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éfinir 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 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 son emplacement dans ce fichier.
- Lorsque Doxygen doit accéder à une instance de MemberDef, il vérifie si l'instance 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 les charge depuis le disque.
Les performances du cache dépendent de :
- 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 sa taille maximale, il faut décider quelles entrées libérer. Par exemple, on pourrait :
- 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 du retrait des instances du 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 cela permet d'augmenter la taille du cache sur les machines disposant de beaucoup de mémoire physique, améliorant ainsi 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 du code source de Doxygen responsable de la libération des entrées du cache lorsque celui-ci atteint sa taille maximale :
Comme spécifié dans le makeResident 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 MemberDef, elle est appelée chaque fois qu'il faut accéder à l'état de MemberDef pour vérifier si ce membre est chargé ou non. S'il n'est pas chargé, Doxygen le charge et retire 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 d'une application, mais la mise en cache apporte-t-elle une optimisation significative, 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 utilisions Doxygen comme parseur pour notre première version, et nous avons effectué de nombreux tests sur la taille du cache. Lorsque nous avons désactivé le cache et analysé quelques projets C++ avec cette version modifiée, le temps d'analyse a augmenté de façon significative — passant parfois de 5 minutes à 25 minutes. Pour les gros projets, cela prenait des heures et avait un impact important sur les performances du système.
Conclusion
L'utilisation d'un cache peut être un moyen puissant d'améliorer les performances d'une application lorsqu'on manipule de grandes quantités de données. Explorer la façon dont les projets open source implémentent la mise en cache peut être très utile pour décider comment l'implémenter dans vos propres applications.