Optimizing Memory Usage: Insights from Doxygen

Versuchen die auf einem Rechner laufenden Prozesse mehr Speicher zu belegen, als physisch verfügbar ist, beginnt der Kernel Speicherseiten zwischen RAM und Datenträger auszulagern. Dadurch wird genügend physischer Speicher freigegeben, um weitere Speicheranforderungen erfüllen zu können.

Excessive use of swapping is called thrashing and is undesirable because it lowers overall system performance, mainly because hard drives are far slower than RAM.

Muss eine Anwendung große Datenmengen verarbeiten, kann Thrashing auftreten und die Performance drastisch einbrechen. Grundsätzlich gibt es zwei Lösungen: die Speichernutzung der Anwendung optimieren oder dem System mehr physischen RAM hinzufügen.

Let’s see which solution Doxygen uses to optimize memory usage and avoid thrashing.

Doxygen ist de facto das Standardwerkzeug zur Erzeugung von Dokumentation aus annotiertem C++-Quellcode, unterstützt jedoch auch viele andere verbreitete Programmiersprachen wie C, Objective-C, C#, PHP, Java und Python. Ein großer Dank gilt Dimitri van Heesch für seine enorme Arbeit an Entwicklung und Pflege des Projekts.

Doxygen liest Quelldateien ein, analysiert sie, extrahiert die benötigten Daten und speichert die Ergebnisse in Instanzen der Klassen DirDef, FileDef, NamespaceDef, ClassDef und MemberDef. Sie alle erben von der Klasse Definition.

Diese Instanzen werden anschließend zur Erzeugung der Dokumentation verwendet. Den größten Speicherbedarf verursachen Informationen über Methoden und Variablen, die durch die Klasse MemberDef repräsentiert werden. Abhängig von der Anzahl der Methoden und Variablen eines Projekts kann der Speicherbedarf dieser Instanzen auf mehr als 1 GB anwachsen.

Bei manchen Projekten beeinträchtigt das Vorhalten all dieser Instanzen im Arbeitsspeicher die Systemleistung; die Dokumentationserzeugung kann dann viele Stunden dauern.

Wie optimiert Doxygen die Speichernutzung?

Doxygen uses a cache-based solution. Using a cache is a common way to optimize memory usage. The idea is to store in a cache the data that needs to be in memory. This cache contains many slots, each holding a specific piece of data. Some slots are released when the cache exceeds a certain size. The released data is moved to disk and loaded back into memory when needed again.

Bei Doxygen ist der Algorithmus sehr einfach:

• Einen Cache mit 65.535 Slots anlegen.
• Wenn eine MemberDef-Instanz erstellt werden muss, prüft Doxygen, ob ein Cache-Slot verfügbar ist. Ist dies der Fall, wird die Instanz im Arbeitsspeicher angelegt. Andernfalls wird sie in einer Datendatei auf dem Datenträger gespeichert und eine Indexdatei mit ihrer Position aktualisiert.
• Benötigt Doxygen Zugriff auf eine MemberDef-Instanz, prüft es zunächst, ob sie sich im Cache befindet. Falls nicht, ermittelt Doxygen mithilfe der Indexdatei ihre Position in der Datendatei und lädt sie von dort.

Die Performance des Caches hängt von mehreren Faktoren ab:

• Der Container: Das kann eine Queue, ein Array, eine Liste oder ein eigener Container sein. Die Wahl kann die Cache-Performance beeinflussen.
• Die maximale Cache-Größe.
• The algorithm used to remove entries from the cache. When the cache reaches its maximum size, you have to decide which entries to release. For example, you could:
  • Die zuerst geladenen Slots freigeben.
  • Die zuletzt geladenen Slots freigeben.
  • Die am seltensten verwendeten Slots freigeben.

1. Der Container

Doxygen definiert die Klasse ObjCache als verkettete Liste von CacheNode-Objekten. Diese Klasse ist dafür zuständig, Instanzen zum Cache hinzuzufügen und daraus zu entfernen.

So deklariert Doxygen seinen Cache:

Doxygen::symbolCache   =new ObjCache(16+cacheSize);// 16 -> room for 65536 elements, 

2. Cache-Größe

Doxygen liest die maximale Cache-Größe aus der Konfigurationsdatei:

int cacheSize =Config_getInt("SYMBOL_CACHE_SIZE");

Ein konfigurierbarer Wert ist sinnvoll, weil sich auf Rechnern mit viel physischem Speicher die Cache-Größe erhöhen und damit die Performance verbessern lässt. In neueren Doxygen-Versionen wurde dieser Parameter jedoch aus der Konfigurationsdatei entfernt; stattdessen wird ein Standardwert verwendet.

3. Algorithmus zum Freigeben von Cache-Einträgen

Der folgende Ausschnitt aus dem Doxygen-Quellcode ist dafür zuständig, Cache-Einträge freizugeben, sobald die maximale Größe erreicht ist:

Wie im 

Methodencode ausführlich kommentiert, wird bei vollem Cache der am längsten nicht verwendete Eintrag entfernt.

This method is invoked by almost all 

 Methoden aufgerufen. Sie kommt immer dann zum Einsatz, wenn auf den 

Zustand zugegriffen werden muss. Dabei wird geprüft, ob das Member geladen ist; falls erforderlich, wird es geladen und das am längsten nicht verwendete Member aus dem Cache entfernt.

The advantage of using the cache

Ein Cache kann die Performance einer Anwendung verbessern. Doch ist der Nutzen wirklich erheblich oder handelt es sich lediglich um eine Mikrooptimierung, die die zusätzliche Komplexität nicht rechtfertigt?

Bevor wir Clang als C/C++-Parser für unser Produkt einsetzten, verwendeten wir in der ersten Version Doxygen. Wir führten zahlreiche Tests zur Cache-Größe durch. Nachdem wir den Cache deaktiviert hatten, stieg die Parsing-Zeit bei einigen C++-Projekten drastisch an – teilweise von fünf auf 25 Minuten. Bei großen Projekten kann der Vorgang Stunden dauern und die Systemleistung erheblich beeinträchtigen.

Fazit

Beim Verarbeiten großer Datenmengen kann ein Cache die Performance einer Anwendung erheblich verbessern. Zu untersuchen, wie Open-Source-Projekte ihre Caches implementieren, ist daher eine wertvolle Hilfe beim Entwurf eines eigenen Cache-Systems.