Speichernutzung optimieren: Erkenntnisse aus Doxygen

Wenn die auf Ihrem Rechner laufenden Prozesse mehr Speicher anfordern, als das System bereitstellen kann, beginnt der Kernel, Speicherseiten auf den Datenträger auszulagern und bei Bedarf wieder einzulesen. Dadurch wird genügend physischer Speicher freigegeben, um die Speicheranforderung des jeweiligen Prozesses zu erfüllen.

Eine übermäßige Nutzung dieses Auslagerungsmechanismus wird als Thrashing bezeichnet. Sie ist unerwünscht, weil sie die Gesamtleistung des Systems deutlich reduziert – vor allem, weil Festplatten wesentlich langsamer als RAM sind.

Wenn Ihre Anwendung große Datenmengen verarbeiten muss, kann sie von Thrashing betroffen sein und dadurch drastisch langsamer werden. Dafür gibt es zwei mögliche Lösungen: die Anwendung so optimieren, dass sie den Speicher effizienter nutzt, oder dem System mehr physischen RAM hinzufügen.

Sehen wir uns an, welche Lösung Doxygen verwendet, um die Speichernutzung zu optimieren und Thrashing zu vermeiden.

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

Doxygen nimmt Quelldateien als Eingabe, analysiert sie, um die benötigten Daten zu extrahieren, und speichert die Ergebnisse in Instanzen der Klassen DirDef, FileDef, NamespaceDef, ClassDef und MemberDef. Sie alle erben von der Klasse Definition.

Die Instanzen dieser Klassen werden anschließend zur Erzeugung der Dokumentation verwendet. Den größten Speicherbedarf verursachen die Informationen über Methoden und Variablen, die durch die Klasse MemberDef repräsentiert werden. Je nach Anzahl der Methoden und Variablen in den verarbeiteten Projekten kann der Speicherbedarf dieser Instanzen auf mehr als 1 GB anwachsen.

Bei manchen Projekten kann das Vorhalten all dieser Instanzen im Arbeitsspeicher die Systemleistung beeinträchtigen; die Erzeugung der Dokumentation kann dann viele Stunden dauern.

Wie optimiert Doxygen die Speichernutzung?

Doxygen setzt auf eine cachebasierte Lösung. Die Verwendung eines Caches ist eine gängige Methode, um die Speichernutzung zu optimieren. Die Idee besteht darin, die Daten, die im Arbeitsspeicher benötigt werden, in einem Cache vorzuhalten. Dieser Cache enthält zahlreiche Slots, von denen jeder bestimmte Daten speichert. Überschreitet der Cache eine festgelegte Größe, werden einige Slots freigegeben. Die betreffenden Daten werden auf den Datenträger verschoben und bei erneutem Bedarf wieder in den Arbeitsspeicher geladen.

Bei Doxygen ist der Algorithmus sehr einfach:

• Es wird ein Cache mit 65.535 Slots definiert.
• 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 aktualisiert, die festhält, an welcher Position sich die Daten befinden.
• Wenn Doxygen auf eine MemberDef-Instanz zugreifen muss, prüft es zunächst, ob sie sich im Cache befindet. Ist sie dort nicht vorhanden, ermittelt Doxygen mithilfe der Indexdatei ihre Position in der Datendatei, springt an diese Stelle und lädt die Daten vom Datenträger.

Die Leistung des Caches hängt von folgenden Faktoren ab:

• Der Container: Dabei kann es sich um eine Queue, ein Array, eine Liste oder einen speziell entwickelten Container handeln. Die Wahl des Containers kann die Leistung des Caches beeinflussen.
• Die maximale Größe des Caches.
• Der Algorithmus zum Entfernen von Einträgen aus dem Cache. Sobald der Cache seine maximale Größe erreicht, muss entschieden werden, welche Einträge freigegeben werden. Beispielsweise können Sie:
  • 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");

Diesen Parameter konfigurierbar zu machen ist sinnvoll, da sich auf einem Rechner mit viel physischem Speicher die Cache-Größe erhöhen lässt, um die Leistung zu verbessern. In neueren Doxygen-Versionen wurde dieser Parameter allerdings aus der Konfigurationsdatei entfernt; stattdessen wird ein Standardwert verwendet.

3. Der Algorithmus zum Freigeben von Cache-Einträgen

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

Wie im Code der Methode 

beschrieben – der übrigens sehr gut kommentiert ist –, wird bei vollem Cache der am längsten nicht verwendete Eintrag entfernt.

This method is invoked by almost all 

 -Methoden aufgerufen. Sie wird immer dann ausgeführt, wenn auf den Zustand von 

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

Der Vorteil eines Caches

Ein Cache kann die Leistung einer Anwendung verbessern. Doch bringt er tatsächlich einen deutlichen Vorteil, 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 als Parser. Wir führten zahlreiche Tests mit unterschiedlichen Cache-Größen durch. Als wir den Cache deaktivierten und einige C++-Projekte mit dieser modifizierten Version analysierten, stieg die Parsing-Zeit drastisch an – teilweise von 5 auf 25 Minuten. Bei großen Projekten kann der Vorgang Stunden dauern und die Systemleistung erheblich beeinträchtigen.

Fazit

Bei der Verarbeitung großer Datenmengen kann ein Cache die Anwendungsleistung erheblich verbessern. Zu untersuchen, wie Open-Source-Projekte ihre Caches implementieren, kann bei der Entwicklung eines Caches für die eigenen Anwendungen äußerst hilfreich sein.