Bei der C++-Programmierung bedeutet Optimierung weit mehr, als nur einzelne Codezeilen auf mehr Leistung zu trimmen. Im Kern geht es darum, kluge Designentscheidungen zu treffen. Dafür gibt es mehrere Gründe:
- Auswahl der Algorithmen: Die Wahl des Algorithmus kann die Performance drastisch beeinflussen. Ein klassisches Beispiel ist die Verwendung eines Sortieralgorithmus mit O(n log n) statt eines Verfahrens mit O(n²).
- Datenstrukturen: Die passende Datenstruktur – etwa eine Hash-Tabelle statt einer verketteten Liste für schnelle Suchzugriffe – kann die Effizienz erheblich steigern.
- Speicherverwaltung: Ein effizienter Umgang mit Speicher und möglichst wenige Allokationen bzw. Freigaben können die Performance deutlich verbessern. Techniken wie Memory Pools oder der korrekte Einsatz von Smart Pointern machen häufig einen großen Unterschied.
- Nebenläufigkeit und Parallelität: Systeme, die mehrere Threads oder Prozesse effektiv nutzen, können deutlich leistungsfähiger sein. C++11 führte dafür eine standardisierte Thread-Unterstützung ein.
- Vorzeitige Optimierung vermeiden: Meist ist es effektiver, zunächst sauberen und wartbaren Code zu schreiben und erst anschließend die tatsächlich kritischen Bereiche gezielt zu optimieren.
Doxygen-Fallstudie: Memory Thrashing durch Designentscheidungen vermeiden
Wenn laufende Prozesse mehr Speicher anfordern, als im System verfügbar ist, beginnt der Kernel, Speicherseiten zwischen RAM und Datenträger auszulagern. Dadurch soll genügend physischer Speicher freigegeben werden, um die Speicheranforderungen des anfordernden Prozesses zu erfüllen.
Eine übermäßige Nutzung dieses Auslagerns wird als Thrashing bezeichnet. Sie ist unerwünscht, weil sie die Gesamtleistung des Systems reduziert – vor allem, weil Datenträger wesentlich langsamer als RAM sind.
Wenn Ihre Anwendung große Datenmengen im Speicher halten muss, kann Thrashing auftreten und die Anwendung drastisch verlangsamen. Im Wesentlichen gibt es zwei Lösungen: den Speicherverbrauch der Anwendung optimieren oder dem System mehr physischen RAM hinzufügen.
Sehen wir uns an, welchen Ansatz Doxygen verwendet, um den Speicherverbrauch zu optimieren und Thrashing zu vermeiden.
Doxygen ist der De-facto-Standard 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 seinen Einsatz bei Entwicklung und Pflege des Projekts.
Doxygen verarbeitet die Quelldateien, parst sie, extrahiert die benötigten Informationen und speichert die Ergebnisse 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 größten Speicheranteil beanspruchen Informationen über Methoden und Variablen, die durch die Klasse MemberDef repräsentiert werden. Je nach Anzahl der Methoden und Variablen eines Projekts können diese Instanzen zusammen mehr als 1 GB belegen.
Bei manchen Projekten beeinträchtigt das Vorhalten all dieser Instanzen im Arbeitsspeicher die Systemleistung erheblich; die Dokumentationserzeugung kann dann viele Stunden dauern.
Wie optimiert Doxygen den Speicherverbrauch?
Doxygen verwendet eine auf einem Datenträger-Cache basierende Lösung. Ein Datenträger-Cache ist eine verbreitete Methode, den Speicherverbrauch zu optimieren. Dabei werden Daten, die sonst im RAM verbleiben müssten, auf dem Datenträger gespeichert. Der Cache besteht aus zahlreichen Slots mit jeweils bestimmten Daten. Überschreitet seine Größe einen festgelegten Wert, werden Slots freigegeben. Die ausgelagerten Daten bleiben auf dem Datenträger und werden 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 erzeugt werden muss, prüft Doxygen, ob ein Cache-Slot verfügbar ist. Ist das der Fall, wird die Instanz im Speicher angelegt. Andernfalls wird sie in einer Datendatei auf dem Datenträger gespeichert und eine Indexdatei mit ihrer Position aktualisiert.
- Muss Doxygen auf eine MemberDef-Instanz zugreifen, prüft es zunächst, ob sie sich im Cache befindet. Falls nicht, ermittelt Doxygen anhand der Indexdatei ihre Position in der Datendatei und lädt sie von dort in den Speicher.
Die Performance des Caches hängt von mehreren Faktoren ab:
- Der Container: Das kann eine Queue, ein Array, eine Liste oder ein benutzerdefinierter Container sein. Die Wahl des Containers kann die Cache-Performance beeinflussen.
- Die maximale Größe des Caches.
- Der Algorithmus zum Entfernen von Cache-Einträgen. Sobald der Cache seine maximale Größe erreicht, muss entschieden werden, welche Einträge entfernt werden. Beispielsweise könnten 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-Instanzen. Diese Klasse ist dafür verantwortlich, 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 lässt sich der Cache vergrößern und damit seine Performance verbessern. In neueren Doxygen-Versionen wurde dieser Parameter allerdings aus der Konfigurationsdatei entfernt; stattdessen wird ein Standardwert verwendet.
3 – Der Algorithmus zum Entfernen 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 der sehr gut kommentierte Code der Methode makeResident zeigt, wird bei vollem Cache der am längsten nicht verwendete Eintrag entfernt.
Diese Methode wird von nahezu allen MemberDef-Methoden aufgerufen. Bei jedem Zugriff auf den Zustand eines MemberDef-Objekts wird geprüft, ob das Element geladen ist; falls nicht, wird es geladen und gegebenenfalls das am längsten nicht verwendete Element aus dem Cache entfernt.
Auswirkungen des Caches
Ein Cache kann die Anwendungsleistung verbessern. Doch handelt es sich um eine wirklich relevante Optimierung oder 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 mit unterschiedlichen Cache-Größen durch. Als wir den Cache deaktivierten und einige C++-Projekte mit dieser modifizierten Version analysierten, stieg die Parsing-Zeit stark an – teilweise von 5 auf 25 Minuten. Bei großen Projekten kann der Vorgang Stunden dauern und die Systemleistung erheblich beeinträchtigen.
Fazit
Wirksame C++-Optimierung beginnt bei fundierten Designentscheidungen. Mit den richtigen Algorithmen, Datenstrukturen und Speicherverwaltungstechniken sowie einem sinnvollen Einsatz von Nebenläufigkeit lassen sich erhebliche Performance-Gewinne erzielen. Dieser strategische Blick auf das Design ist der eigentliche Schlüssel zur Optimierung in C++.