Wenn die auf Ihrem Rechner laufenden Prozesse mehr Speicher reservieren möchten, als physisch verfügbar ist, beginnt der Kernel damit, Speicherseiten auf die Festplatte auszulagern und wieder einzulesen. Dadurch wird genügend physischer Speicher freigegeben, um den RAM-Bedarf des anfordernden Prozesses zu erfüllen.
Eine übermäßige Nutzung des Swappings wird als Thrashing bezeichnet und ist unerwünscht, weil sie die Gesamtleistung des Systems reduziert – vor allem, weil Festplatten deutlich langsamer als RAM sind.
Wenn Ihre Anwendung große Datenmengen verarbeiten muss, kann sie von Thrashing betroffen sein und sich drastisch verlangsamen. Es gibt zwei Lösungen: Entweder optimieren Sie die Anwendung für eine effizientere Speichernutzung oder Sie erweitern das System um zusätzlichen physischen RAM.
Sehen wir uns an, welche Lösung Doxygen verwendet, um die Speichernutzung zu optimieren und Thrashing zu vermeiden.
Doxygen ist der De-facto-Standard zur Erzeugung von Dokumentation aus annotiertem C++-Quellcode, unterstützt aber auch zahlreiche andere verbreitete Programmiersprachen wie C, Objective-C, C#, PHP, Java und Python. Großer Dank gilt Dimitri van Heesch für seinen enormen Einsatz bei der Entwicklung und Pflege des Projekts.
Doxygen nimmt die Quelldateien als Eingabe, parst sie, extrahiert die benötigten Daten und speichert das Ergebnis in Instanzen der Klassen DirDef, FileDef, NamespaceDef, ClassDef und MemberDef. Sie alle erben von der Klasse Definition.
Diese Klasseninstanzen werden anschließend zur Erzeugung der Dokumentation verwendet. Den meisten Speicher beanspruchen Informationen über Methoden und Variablen, die durch die Klasse MemberDef repräsentiert werden. Abhängig von der Anzahl der Methoden und Variablen in den verarbeiteten Projekten können diese Instanzen zusammen mehr als 1 GB belegen.
Bei manchen Projekten kann das Speichern all dieser Instanzen im Arbeitsspeicher die Systemleistung beeinträchtigen, sodass die Dokumentationserzeugung viele Stunden dauern kann.
Wie optimiert Doxygen die Speichernutzung?
Doxygen verwendet eine Cache-basierte Lösung. Ein Cache ist eine verbreitete Möglichkeit, die Speichernutzung zu optimieren. Die Idee besteht darin, nur die Daten im Cache zu halten, die sich im Arbeitsspeicher befinden müssen. Der Cache enthält viele Slots, von denen jeder bestimmte Daten aufnimmt. Überschreitet der Cache eine festgelegte Größe, werden einige Slots freigegeben. Die entsprechenden Daten werden auf die Festplatte verschoben und bei erneutem Bedarf wieder in den Arbeitsspeicher geladen.
Bei Doxygen ist der Algorithmus sehr einfach:
- Einen Cache mit 65.535 Slots definieren.
- Wenn eine MemberDef-Instanz erstellt werden muss, prüft Doxygen, ob ein Cache-Slot verfügbar ist. Falls ja, wird die Instanz im Arbeitsspeicher erzeugt. Andernfalls wird sie in einer Datendatei auf der Festplatte gespeichert und eine Indexdatei aktualisiert, die die Position der Daten in dieser Datei festhält.
- Muss Doxygen auf eine MemberDef-Instanz zugreifen, prüft es zunächst, ob sie im Cache vorhanden ist. Falls nicht, liest Doxygen aus der Indexdatei, wo die Daten gespeichert sind, springt zur entsprechenden Position in der Datendatei und lädt sie von der Festplatte.
Die Leistung des Caches hängt von folgenden Faktoren ab:
- Der Container: Er kann eine Queue, ein Array, eine Liste oder ein benutzerdefinierter Container sein. Die Wahl des Containers kann die Cache-Leistung beeinflussen.
- Die maximale Größe des Caches.
- Der Algorithmus zum Freigeben von Cache-Einträgen. Wenn der Cache seine maximale Größe erreicht, muss entschieden werden, welche Einträge entfernt werden. Zum Beispiel können Sie:
- die zuerst geladenen Slots freigeben.
- die zuletzt geladenen Slots freigeben.
- die am wenigsten 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");Es ist sinnvoll, diesen Parameter konfigurierbar zu machen. Auf einem Rechner mit viel physischem Speicher kann der Cache so vergrößert und seine Leistung verbessert werden. In neueren Doxygen-Versionen wurde dieser Parameter jedoch aus der Konfigurationsdatei entfernt und durch einen Standardwert ersetzt.
3. Der Algorithmus zum Freigeben von Cache-Einträgen
Hier ist der Ausschnitt aus dem Doxygen-Quellcode, der Cache-Einträge freigibt, sobald der Cache seine maximale Größe erreicht:
Wie im Code der Methode
makeResidentbeschrieben, der sehr gut kommentiert ist, wird bei vollem Cache der am längsten nicht verwendete Eintrag entfernt.
Diese Methode wird für fast alle
MemberDef-Methoden aufgerufen. Sie wird jedes Mal ausgeführt, wenn auf den
MemberDef-Zustand zugegriffen werden muss, um zu prüfen, ob dieses Element geladen ist, es gegebenenfalls zu laden und das am längsten nicht verwendete Element aus dem Cache zu entfernen.
Die Auswirkungen der Cache-Nutzung
Ein Cache kann die Leistung Ihrer Anwendung verbessern. Doch bringt er eine deutliche Optimierung oder handelt es sich nur um eine Mikrooptimierung, deren Implementierung sich kaum lohnt?
Bevor wir Clang als C/C++-Parser für unser Produkt einsetzten, verwendeten wir in der ersten Version Doxygen. Wir führten zahlreiche Tests mit verschiedenen 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
Ein Cache ist ein wirkungsvolles Mittel, um die Anwendungsleistung bei der Verarbeitung großer Datenmengen zu verbessern. Zu untersuchen, wie Open-Source-Projekte ihre Caches implementieren, kann beim Entwurf eines eigenen Caches äußerst hilfreich sein.