Letzte relevante Änderung: 08.03.2018

Programme optimieren

Obwohl sich die Leistungsfähigkeit moderner Computer ständig erhöht – sowohl die Festplatten- und RAM-Kapazitäten als auch die Rechengeschwindigkeit von CPUs und GPUs haben sich im Laufe der letzten Jahre weiter vervielfacht – stoßen sie noch immer an Grenzen. Einerseits, weil die Komplexität der Probleme – also unsere Ansprüche – sich erhöhen, andererseits auch, weil weniger Wert auf die Optimierung von Programmen gelegt wird. Zumindest in letztem Punkt kann durch die im Folgenden dargestellten Techniken Abhilfe geschaffen werden. Diese Techniken beziehen sich im Wesentlichen auf die Programmiersprachen C++ und teilweise auch C; lassen sich jedoch teilweise oder sinngemäß natürlich auch auf andere Sprachen übertragen.

Inhaltsverzeichnis:

Optimierung kann hauptsächlich auf drei Ziele ausgerichtet sein: Geschwindigkeitssteigerung, Reduktion des RAM-Verbrauchs und Verkleinerung der Programmgröße. Diese drei Ziele schließen sich dabei weder grundsätzlich aus, noch verhalten sie sich stets komplementär zueinander. Eine Steigerung der Komplexität eines Programms (und damit auch der kompilierten Binärdatei) kann notwendig sein, um mehr Funktionalität oder schnellere Algorithmen unterzubringen; sie kann allerdings auch Ausdruck von redundantem, d. h. überflüssigem Code sein, der entweder überhaupt nicht, oder sogar ohne Zusatznutzen ausgeführt wird und dann auch Rechenzeit kostet. Grundsätzlich lässt sich festhalten: Eine Verkleinerung des Programms trägt zumindest insoweit zu mehr Geschwindigkeit und weniger RAM-Verbrauch bei, als die Ladezeit reduziert und der Speicherverbrauch des binären Programmcodes selbst (den das Betriebssystem während der Ausführung im RAM vorhält) sinkt. Dieser Vorteil wird allerdings, da die Ladezeit des Programms und dessen eigener Speicherverbrauch meist relativ gering sind, schnell aufgefressen, wenn derartige Optimierungen mit schlechteren Algorithmen erkauft werden. In eben jenen Algorithmen liegt auch in der Regel größeres Verbesserungspotential als in sog. Mikrooptimierungen am Quellcode. Der Fokus dieser Erläuterungen liegt dennoch eher bei Mikrooptimierungen, da die Programmalgorithmen oft anwendungsspezifisch sind, und sich daher wenig Allgemeines darüber sagen lässt. Dabei geht es grundsätzlich darum, wie man effizienteren Code schreibt, und weniger darum, die Fähigkeiten moderner CPUs – etwa durch Multithreading – besser auszlasten.

Zwischenergebnisse wiederverwenden

C, C++, Caching

„Warum eine Berechnung zweimal durchführen, wenn man sich einfach das Ergebnis merken kann?“ ist das Credo dieses Abschnitts. In diesem Punkt liegt ein großer Zielkonflikt begraben, denn je mehr man zwischenspeichert („casht“), um es später wieder zu verwenden, desto mehr Speicher benötigt das Programm. In Zeiten relativ großer RAM-Kapazitäten moderner PCs geht die Tendenz dahin, Caching der Neuberechnung vorzuziehen. Je umfangreicher der Neuberechnungsaufwand, je kleiner der Speicherbedarf für das Zwischenergebnis, je öfter die Wiederverwendung und je kürzer der Abstand zwischen den Verwendungen, desto mehr spricht dafür, ein Ergebnis zu cashen. Folgender Code, der einen Dateinamen in seine Bestandteile zerlegt, verdeutlicht dies:

bool parseFilename(const std::string& filename, std::string& name, std::string& extension) {
	if (filename.find('.') == std::string::npos)
		return false; // Kein Dateiname im name.extension-Stil
	name = filename.substr(0, filename.find('.'));
	extension = filename.substr(filename.find('.') + 1);
	return true;
}

Drei Mal durchsuchen wir filename nach einem Punkt, obwohl sich die Zeichenkette, die wir durchsuchen, nicht verändert. Dabei ist std::string::find() durchaus eine aufwändige Operation, muss sie doch jedes Mal durch die Zeichenkette iterieren, um nach dem angegebenen Zeichen suchen. Der Speicherbedarf für einen Integer vom Typ size_t ist hingegen denkbar klein, zumal hier davon ausgegangen werden kann, dass er erstens in einem Register zwischengespeichert wird und zweitens entsprechender Speicherbedarf auch ohne Caching notwendig wäre, nämlich drei Mal während der Auswertung des Rückgabewertes von std::string::find(). Besser wäre:

bool parseFilename(const std::string& filename, std::string& name, std::string& extension) {
	std::size_t point = filename.find('.');
	if (point == std::string::npos)
		return false; // Kein Dateiname im name.extension-Stil
	name = filename.substr(0, point);
	extension = filename.substr(point + 1);
	return true;
}

In diesem Beispiel dürfte die Entscheidung für Caching sehr leicht fallen. Grundsätzlich ist in Fällen, wo es sich um einzelne zu speichernde Variablen handelt, zu caching zu raten, wenn der Rechenaufwand über einige triviale Operatoren hinausgeht und davon auszugehen ist, dass der Compiler dies nicht selbst optimieren kann. Nebenbei sei angemerkt, dass hin und wieder keine Kopie des Wertes erzeugt werden muss, sondern eine Referenz oder ein Zeiger auf das Ergebnis ausreicht. Dies trifft bei größeren Objekten, etwa std::string oder eigenen Klassen zu, setzt allerdings voraus, dass das referenzierte Objekt zum Zeitpunkt der Wiederverwendung noch existiert und bis dahin auch nicht modifiziert wurde.

Die richtigen Container verwenden

C++, STL, Container

Schwerer fällt die Entscheidung, wenn es sich um größere Datenmengen handelt. Während man die grundsätzliche Abwägung nach den o. g. Kriterien treffen muss und keine eindeutige Handlungsempfehlung gegeben werden kann, ist bei der Speicherung die Wahl eines geeigneten (STL-)Containers von großer Bedeutung. Folgende drei Funktionen prüfen, ob eine gegebene Zahl eine Primzahl ist, und nutzen dabei auf verschiedene Weise einen Cache (wie man den Algorithmus des Primzahltests selbst verbessern kann, wird weiter unten diskutiert).

bool isPrim1(uint64_t zahl) {
	if (zahl < 2) return false;
	static std::unordered_map<uint64_t, bool> cache; // Speichert für alle schon geprüften Zahlen, ob es sich um eine Primzahl handelt.
	auto it = cache.find(zahl);                      // Hier setzen wir übrigens die Technik aus dem vorigen Beispiel um. Ein Ergebnis, zweimal genutzt.
	if (it != cache.cend())                          // Wenn gefunden, verwende gespeichertes Ergebnis.
		return it->second;
	for (uint64_t i = 2; i*i <= zahl; i++) {
		if (zahl%i == 0) {
			cache[zahl] = false;             // Ergebnis speichern
			return false;
		}
	}
	return true;
}

bool isPrim2(uint64_t zahl) {
	static std::vector<bool> cache = { false, false, true }; // Speichert für jede Zahl, ob es sich um eine Primzahl handelt.
	                                                         // vector<bool> verbraucht 1 bit pro Zahl.
	if (zahl < cache.size())
		return cache[zahl];
	uint64_t i = cache.size();
	cache.resize(zahl+1);                                    // Schaffe Platz für neue Zahlen
	for (; i <= zahl; i++) {
		cache[i] = true;
		for (uint64_t j = 2; j*j <= i; j++) {
			if (i%j == 0) {
				cache[i] = false;
				break;
			}
		}
	}
	return cache[zahl];
}

bool isPrim3(uint64_t zahl) {
	static uint64_t lastChecked = 2;
	static std::unordered_set<uint64_t> cache = { 2 }; // Speichert alle bekannten Primzahlen im Bereich von 0...lastChecked.
	if (zahl <= lastChecked)
		return cache.find(zahl) != cache.cend();
	bool prim = false;
	for (; lastChecked <= zahl; lastChecked++) {       // Vergrößere geprüften Bereich
		prim = true;
		for (uint64_t j = 2; j*j <= lastChecked; j++) {
			if(lastChecked%j == 0) {
				prim = false;
				break;
			}
		}
		if (prim)
			cache.insert(lastChecked);
	}
	return prim;
}

isPrim2() und isPrim3() sind darauf optimiert, dass möglichst viele Zahlen in einem zusammenhängenden Zahlenbereich getestet werden, weil sie für einen sich dynamisch vergrößerten Bereich der Zahlen von 0 aufwärts die Ergebnisse vorhalten. isPrim2() verbraucht dabei voraussichtlich mehr Speicher (abhängig von der Dichte der Primzahlen und vom Speicheroverhead von std::unordered_set. Da Primzahlen häufiger vorkommen, als man auf Anhieb denken mag, dürfte in diesem konkreten Fall die std::vector<bool>-Lösung in den meisten Fällen sogar weniger Speicher verbrauchen), ist jedoch wesentlich schneller, da anstatt einer Suchoperation lediglich ein Indexzugriff auf den Cache durchgeführt werden muss. isPrim1() hingegen erfordert Suchoperationen und berechnet keine Primzahlen „auf Vorrat“ und ist aufgrund der entfallenen Vorrats-Berechnung dann die effizienteste der drei Implementationen, wenn nur eine kleine Anzahl verschiedener großer Zahlen getestet wird. Insgesamt zeigt sich: Die Kosten für die Vorratshaltung, und die Art der Speicherung im Hinblick auf die Zugriffsart (Suche oder Indexzugriff) sollten gut abgewogen werden. Zu diesem Zweck folgt nun eine Tabelle, die die Eigenschaften der STL-Container zusammenfasst:

Container Indexzugriff Rohzugriff Suche Einf./Entf. Deallokierend Sortierend Duplikate Iteratoren Besonderheiten
std::array Ja Ja langsam Nein - Nein Ja Random-Access Container mit fester Größe
std::vector Ja Ja langsam Ende
(langsam)
NeinNein Ja std::vector<bool> ist hierbei speziell: Jedes Element ist dann nur 1 Bit groß.
std::basic_string Ja konstant langsam Nein Nein Ja Mit Zusatzfunktionen für Zeichenketten.
std::deque Ja Nein langsam Anfang, Ende Blockweise Nein Ja
std::forward_list Nein Nein langsam Überall
(schnell)
JaNein Ja Unidirektional Einfach verkettete Liste, weniger Speicherverbrauch als std::list. Einfügen und Entfernen nur hinter einem Element.
std::list Nein Nein langsam Ja Nein Ja Bidirektional
std::set Nein Nein schnell Ja Ja Ja Nein Bidirektional,
Schlüssel konstant
Weniger Speicherverbrauch als unsortierte Variante, aber ggf. langsamer.
std::multiset Nein Nein Ja Ja Ja Ja
std::unordered_set Nein Nein sehr schnellJa Ja Nein Nein Erfordert std::hash-Implementation.
std::unordered_multiset Nein Nein Ja Ja Nein Ja
std::map Ja Nein schnell Ja Ja Ja Nein Schlüssel-Wert-Paare; Suche schnell nach Schlüsseln, langsam nach Werten. Sortierte Variante hat geringeren Speicherverbrauch. Unsortierte Variante erfordert std::hash-Implementation.
std::multimap Nein Nein Ja Ja Ja Ja
std::unordered_map Ja Nein sehr schnellJa Ja Nein Nein
std::unordered_multimap Nein Nein Ja Ja Nein Ja
std::queue Nein Nein Nein Ende Vielleicht Nein Ja Nein FIFO-Container, Zugriff nur auf vorderstes Element.
std::priority_queue Nein Nein Nein Ende Vielleicht Ja Ja
std::stack Nein Nein Nein Anfang Vielleicht Nein Ja LIFO-Container, Zugriff nur auf oberstes Element.

Es sind grundsätzlich immer die Container zu bevorzugen, die die gewünschten Operationen mit größtmöglicher Geschwindigkeit (ggf. abwägen) bereitstellen, aber nicht mehr als diese. Zusätzliche, aber für den Anwendungsfall nicht benötigte Funktionen können z. B. mit erhöhtem Speicherbedarf einhergehen. So ist std::forward_list zwar mit durchweg weniger Funktionalität als std::list ausgestattet, benötigt allerdings auch pro Element keinen Verweis auf das Vorgängerelement und spart sogar die Speicherung der Länge ein, und konsumiert daher also weniger RAM. Falls std::forward_list also für den Anwendungsfall ausreicht, ist sie die bessere Wahl.

Container richtig befüllen

C++, STL, Container

Hat man sich dann für einen Container entschieden, lassen sich diese oftmals auf effiziente und weniger effiziente Arten befüllen. So bieten die o. g. vier Container mit Indexzugriff, die beiden Listencontainer, sowie Stacks und Queues, Funktionen wie push_back() an, um einzelne Elemente hinzuzufügen. Zu diesen Funktionen lässt sich zweierlei sagen:

  1. Seit C++11 existieren alternativ zu den „push“-Methoden auch „emplace“-Methoden. Zwar profitieren auch die „push“-Methoden von rValue-Referenzen und ersparen so bei Objekten mit Daten auf dem Heap eine kostspielige Kopieraktion beim Einfügen. Wird jedoch das Objekt ohnehin direkt im Aufruf erzeugt, lässt sich mit der „emplace“-Methode die Kopieraktion sogar vollständig eliminieren:
    std::vector<std::string> vec;
    vec.push_back(std::string("foo")); // Pre-C++11 mit explizitem Konstruktoraufruf
    vec.push_back("foo");              // Pre-C++11 mit implizitem Konstruktoraufruf
    vec.emplace_back("foo");           // Optimierte Variante. Das Objekt wird vor Ort (d. h. im Container) konstruiert.
  2. Bei std::vector und std::basic_string kann es sinnvoll sein, die Benutzung der „push“- oder „emplace“-Methoden vorzubereiten. Diese Container können bei Vergrößerung gezwungen sein, einen neuen, größeren Speicherbereich zu allokieren und den kompletten schon existierenden Inhalt in diesen umzukopieren – eine zeitraubende Sache. Fügt man nun direkt hintereinander mehrfach (etwa in einer Schleife) einzelne neue Elemente hinzu, kann dies sogar mehrfach passieren, weil der Container nicht weiß, wieviele Elemente noch kommen werden, und er deshalb die Größe seiner Allokationen nicht vorab an den Bedarf anpassen kann. Zu diesem Zweck bieten diese Container die Methoden resize() und reserve() an. Erstere vergrößert den Container unmittelbar, letztere weist den Container an, für die angegebene Zahl an Elementen Speicher zu reservieren. Weiß man also vorher, wieviele Elemente man dem Container hinzufügen wird, sollte man von reserve() Gebrauch machen.

Seit C++11 gibt es außerdem sog. Initialisierungslisten (std::initializer_list). Mit diesen kann man Container sogar bequem direkt befüllen:

std::vector<std::string> vec = {"Hallo", "Welt", "!"};

Benutzerdefinierte Allokatoren

C++, Allokatoren

Hat all das nicht geholfen, und der verwendete Container ist noch immer zu langsam im Hinzufügen neuer Objekte – gerade bei Listen-Containern ist dies oft ein Problem – kann es helfen, einen eigenen Allokator zu implementieren, um die standardmäßige Speicherverwaltung des Containers zu ersetzen. Etwa im Falle einer Liste, wird standardmäßig für jedes Element eine Allokation fällig. Jedes einzelne dieser Objekte erzeugt Aufwand in der Speicherverwaltung, die über all diese erzeugten Objekte Buch führen muss. Dann kann es sinnvoll sein, eine Speicherverwaltung zu bauen, die einen Pool verwaltet, d.h. Allokationen sammelt und zusammenfasst. Der Nachteil, dass keine einzelnen Elemente wieder freigegeben werden können, sondern nur am Ende der Gesamtpool, fällt in solchen Fällen oft nicht ins Gewicht.

Seit C++11 und der Einführung von std::allocator_traits ist das Entwickeln von Allokatoren weit weniger unerfreulich als früher. Letztlich müssen im Regelfall nur die Methoden allocate(n) und deallocate(p, n) sowie operator== und operator!= implementiert werden. Die Operatoren müssen dabei Objekte verschiedenen Typs vergleichen können. Die für den hier geschilderten Zweck nötigen (oder zumindest hilfreichen) Allokatoren mit internem Status („statefull allocators“) sind seit C++11 möglich. Entscheidend ist allerdings, dass der Pool außerhalb der Allokator-Instanz verwaltet wird, und diese lediglich auf ihn verweist. Diverse im Internet zu findende Beispielimplementationen missachten dies und erzeugen Speicherzugriffsfehler. Eine funktionierende beispielhafte Implementation findet sich hier.

Strings richtig benutzen

C++, Strings

Ein Spezialfall der richtigen Auswahl von STL-Containern ist die Frage, ob man std::string und seine Geschwister benutzen sollte, oder lieber bei dem aus C bekannten und gefürchteten char* bleiben sollte. Es mag zwar Geschmackssache sein, welche der beiden Varianten man für „schöner“ befindet; im Hinblick auf Optimierung lassen sich aber durchaus objektive Antworten geben. Der Overhead von std::string ggü. rohen Zeichenketten besteht in zwei Dingen: Erstens wird zusätzlich zur Zeichenkette selbst auch deren Länge abgespeichert. Dies ist eine Form des oben schon erwähnten Cachings. Zweitens sind String-Literale fest in den Code einkompiliert, während die Erzeugung eines std::string mit einem Konstruktoraufruf einhergeht. Dafür bekommt man jedoch ein gekapseltes Objekt, um dessen Speicherverwaltung man sich keine Gedanken mehr machen muss, und dass zahlreiche Operationen ggü. den C-Funktionen aus <cstring> stark vereinfacht. Aus Optimierungssicht stellt sich daher die Frage: Wann kommen welche Vorteile zum Tragen?

Solange es sich um konstante Strings, d. h. Literale, handelt, sind C-Strings klar vorzuziehen, wenn keine Aktionen damit vorgenommen werden, für die es nötig oder hilfreich ist, wenn die Länge des Strings bekannt ist, und wenn nicht zu einem späteren Zeitpunkt ohnehin std::string-Objekte daraus erzeugt werden müssten. Ist dies jedoch der Fall, oder sind die Strings nicht konstant, ist von C-Strings abzuraten. Der Grund liegt darin, dass strlen() eine sehr teure Operation ist, und auch in anderer Hinsicht der Umgang mit std::strings komfortabler ist. Im Hinblick auf strlen() gelten insbesondere die oben zum Thema Caching dargestellten Erwägungen, denen zufolge angesichts großer RAM-Kapazitäten zu empfehlen ist, kleinere Zwischenergebnisse, wie etwa die Länge eines Strings, zu cachen. Das Anwendungsspektrum, in dem zur Nutzung von C-Strings zu raten ist, ist deswegen relativ klein.

Insbesondere ist jedoch dazu zu raten, nicht ständig zwischen beiden Varianten zu wechseln. Zwar ist std::string::c_str() harmlos, umgekehrt ist jedoch die Erzeugung von STL-Strings aus C-Strings zeitaufwändig und sollte deshalb nicht öfter als notwendig durchgeführt werden. Kaskaden wie std::string(str.c_str()) sind zwar offensichtlich überflüssig, schleichen sich jedoch – meist subtil verteilt über mehrere Funktionen, die sich untereinander aufrufen – hin und wieder trotzdem in den Code ein.

Zum Schluss kann es zuweilen geraten sein, eine const char*-Überladung als Wrapper bereitzustellen, der dann lediglich die Hauptfunktion mit std::string als Parameter aufruft, falls die Funktion oft mit String-Literalen aufgerufen wird. Dies verlagert den Code zur Erzeugung der std::string-Instanz in eine einzelne Funktion und spart damit die redundante Generation des dazugehörenden Binärcodes ein, wenn auch auf Kosten eines zusätzlichen Funktionsaufrufs.

Objekte verkleinern durch Flags

C, C++, Flags, Bitfelder

Nachdem wir uns damit befasst haben, wie sich größere Mengen von Objekten effizient speichern lassen, wenden wir uns nun von Containern vorläufig ab, und überlegen, ob man die Objekte selbst nicht verkleinern könnte. Die erste Technik bezieht sich dabei auf solche Objekte, die mehrere Variablen vom Typ bool als Member haben. Die Beispielklasse

class Variable {
public:
	bool isVolatile;
	bool isConst;
	bool isStatic;
};

belegt 3 Bytes, weil sizeof(bool) 1 Byte (und nicht 1 Bit) beträgt. Dies ist nötig, weil 1 Byte die kleinste addressierbare Einheit eines Rechners ist. Um Platz zu sparen, kann man diese Flags (sogar bis zu 8 derartiger Flags) jedoch problemlos in einer Variable von 1 Byte Länge unterbringen. Zu diesem Zweck gibt es Bitfelder:

class Variable {
public:
	bool isVolatile : 1; // Diese Variable hat dann die Länge von 1 Bit (auch andere Größen sind möglich).
	bool isConst    : 1; // Solche Variablen sind nicht addressierbar, entsprechend kann man keine Pointer oder Referenzen auf sie erzeugen.
	bool isStatic   : 1; // Der Compiler füllt die Klasse dann auf 8 Bit = 1 Byte Länge auf.
};

Um zu verstehen, wie der Compiler mit diesem Feldern intern umgeht, lassen sich diese auch selbst implementieren:

class Variable {
	uint8_t flags;                                               // Hier speichern wir unsere drei Flags
	enum FLAGS { _isVolatile = 0x1, _isConst = 0x2, _isStatic = 0x4 };
	void setFlag(FLAGS flag, bool value) {
		if (value)
			flags |= flag;
		else
			flags &= flag;
	}
public:
	bool isVolatile() const { return flags & _isVolatile; }      // Über diese Funktionen werden die Flags gelesen.
	bool isConst() const { return flags & _isConst; }
	bool isStatic() const { return flags & _isStatic; }
	void isVolatile(bool value) { setFlag(_isVolatile, value); } // Übe diese Funktionen können die Flags gesetzt werden.
	void isConst(bool value) { setFlag(_isConst, value); }
	void isStatic(bool value) { setFlag(_isStatic, value); }
};

Intern werden also Bitoperationen für den Zugriff verwendet. Diese sind das Herzstück jeder CPU und kosten daher keine nennenswerte zusätzliche Rechenzeit. Die Größe des Objektes konnte jedoch ggü. dem Ausgangsbeispiel auf ⅓ reduziert werden.

Füllbytes vermeiden

C, C++, Füllbytes

Eine zweite Technik besteht darin, durch geschicktes Arrangieren der Member einer Klasse/Struktur die Anzahl der vom Compiler erzeugten Füllbytes zu verringern. Solche Bytes erzeugen Compiler, weil der Zugriff auf Speicherbereiche durch deren Adressausrichtung optimiert werden kann. Das heißt, ein uint32_t kann i.d.R. schneller aus dem Speicher gelesen werden, wenn er an 4-Byte-Grenzen ausgerichtet ist. Da die Reihenfolge der Membervariablen, in der sie in der Klasse deklariert werden, auch ihrer Reihenfolge im Speicher entspricht, kann der Compiler gezwungen sein, Füllbytes zwischen die Variablen zu legen, um die Speicherausrichtung („alignment“) zu optimieren.

class Object {
	uint8_t  var1;
	uint64_t var2;
	uint16_t var3;
};

Aus diesem Grund beträgt sizeof(Object) 18, und nicht 11. Hinter var1 fügt der Compiler nämlich 7 Füllbytes ein, um var2 an 64-bit-Grenzen auszurichten. Ein erster Schritt nach vorne (ohne Performanceeinbußen, denn die Ausrichtung von kleineren Objekten an größeren Grenzen bringt keine Vorteile) wäre Folgendes:

class Object {
	uint8_t  var1;
	uint16_t var3;
	uint64_t var2;
};

Damit läge var3 nämlich innerhalb der ohnehin generierten 7 Füllbytes. Nun befinden sich noch hinter var1 1 Füllbyte, um var3 auszurichten, und hinter var1 noch einmal 4 Füllbytes. sizeof(Object) beträgt nun 16. Aber es geht noch besser. Wenn nämlich die Member nach absteigender Größe angeordnet werden, sind keinerlei Füllbytes notwendig, und die Klasse wäre nur noch 11 Bytes (manche Compiler fügen allerdings am Schluss noch 5 Füllbytes an, um auch die Größe der Struktur an 8-Bytes-Grenzen auszurichten. Diese Füllbytes lassen sich allerdings nicht mehr wegoptimieren) groß:

class Object {
	uint64_t var2;
	uint16_t var3;
	uint8_t  var1;
};

Der MSVC bietet als Hilfestellung die Warnung C4820 an, die standardmäßig deaktiviert ist. Während der Optimierung ist es jedoch sinnvoll, diese temporär zu aktivieren, um die Stellen, an denen Füllbytes auftreten, schnell identifizieren zu können.

Bedingungen optimal anordnen

C, C++, Bedingungen

Ein kleiner Optimierungstrick besteht darin, mit || oder && verknüpfte Bedingungen so zu arrangieren, dass die schneller zu berechnende Bedingung links steht. Der Grund ist, dass bei einer &&-Verknüpfung die zweite Bedingung nur noch geprüft wird, wenn die erste nicht bereits false war, bzw. umgekehrt bei || die zweite Bedingung nicht geprüft wird, wenn die Erste bereits true ergab. Dies ist nicht nur eine theoretische Optimierungsoption für den Compiler, sondern vom Standard vorgeschrieben. Andernfalls wäre es auch nicht möglich, elegant Nullpointer-Tests einer Bedingung vorweg zu stellen (if (var && var->checkSomething())). Dieses Verhalten kann man sich also zunutze machen: (a <= 4 && strlen(str) == 20) ist effizienter als (strlen(str) == 20 && a <= 4), weil strlen() als Aufruf einer Funktion (die überdies bekanntlich durch die gegebene Zeichenkette iterieren muss, um deren Länge zu ermitteln) deutlich langsamer ist, als der Vergleich von a mit 4. Ist a also größer als 4, muss und wird der Aufruf von strlen(str) nicht mehr durchgeführt werden. Voraussetzung für diese Optimierung ist, dass sich die beiden Bedingungen nicht in einer Weise gegenseitig beeinflussen, dass ihre Reihenfolge nicht verändert werden darf und dass die erste Bedingung keine Nebeneffekte hat, die es nötig machen, dass sie in jedem Fall ausgewertet wird.

Parameterübergabe per Referenz

C, C++, Referenzen

Nehmen wir nun folgendes, 400 Bytes großes Array an (um nicht mit den Nebenwirkungen von C-Arrays bei Parameterübergaben konfrontiert zu werden, verpacken wir es in einer struct):

struct array { int ints[100]; };

Wir möchten nun eine Funktion schreiben, die den Inhalt eines solchen Arrays auf den Bildschirm ausgibt. Die naheliegendste Variante wäre:

void printArray(array arr) {
	for(int i = 0; i < 100; i++)
		printf(" %u", arr.ints[i]);
}

Hierbei entstehen aber Probleme: Bei einem Funktionsaufruf werden Parameter auf den Stack gelegt, und dessen Größe ist begrenzt. Dieser könnte also überlaufen; zweitens ist aber schon das Kopieren von 400 Bytes auf den Speicher eine zeitraubende Angelegenheit und eigentlich nicht nötig, denn die Funktion verändert das Array ja nicht, und wir brauchen also keine Kopie, sondern könnten direkt mit dem Original arbeiten. In C hätten wir folgende Möglichkeit:

void printArray(const array* arr) {
	for(int i = 0; i < 100; i++)
		printf(" %u", arr->ints[i];
}

Hierbei würden auf einem 64-bit-System 8, auf einem 32-bit-System 4 Bytes, nämlich die Adresse des Arrays, auf den Stack gelegt – in unserem Fall also eine Verbesserung um den Faktor 50 bzw. 100. Allerdings bieten const* keine große Typsicherheit, außerdem könnte man auch Nullzeiger übergeben, die man abfangen müsste. Darum geht es in C++ noch eleganter:

void printArray(const array& arr) {
	for(int i = 0; i < 100; i++)
		printf(" %u", arr.ints[i]);
}

Lediglich der Prototyp der Funktion hat sich ggü. der Ausgangsfunktion geändert, aber es werden, wie im zweiten Beispiel, nur 4 bzw. 8 Bytes auf den Stack gelegt. Eine Referenz (mit & gekennzeichnet), ist eine Art Aliasname für das Objekt,das ihr beim Funktionsaufruf übergeben wurde. Intern wird er wie ein Pointer behandelt, allerdings wird das durch die Syntax versteckt. Es ist deswegen auchnicht möglich, einer Referenz nachträglich eine andere Variable zuzuweisen. Typsicherheit wird gewährleistet, const versichert, dass das übergebene Objekt nicht verändert werden kann. Parameter,die größer als ein Pointer auf dem jeweiligen System sind, sollten also möglichst per Pointer, bzw. in C++ per const-Referenz übergeben werden. Seit C++11 existieren auch sog. rValue-Referenzen, auf die wir im nächsten Abschnitt eingehen.

rValue-Referenzen und Move-Konstruktoren

C++11, Referenzen

Kopieren von Objekten, insbesondere von potentiell großen Objekten oder STL-Containern ist üblicherweise eine zeitraubende Angelegenheit und sollte vermieden werden. Allerdings stellt sich die Frage, wozu überhaupt eine umfangreiche Kopieraktion nötig ist, wenn direkt nach der Konstruktion der Kopie das alte Element zerstört wird. Derartige Situationen kommen recht häufig vor, beispielsweise, wenn STL-Container als Rückgabewert einer Funktion genutzt werden. Könnte nicht die neue Instanz einfach die Daten der alten übernehmen?

C++11 führt zu diesem Zweck Rechtswertreferenzen (üblicherweise rValue-Referenzen genannt) ein. Mittels dieser kann ein Objekt Zeiger an eine neue Instanz weitergeben, um das Kopieren von Daten zu vermeiden. Damit wird das erstellen temporärer Kopien von Objekten, wie sie beispielsweise entstehen, wenn Klassenobjekte zurückgegeben oder als Parameter nicht als Referenz übergeben werden, weitaus weniger zeitaufwändig.

Ein sogenannter Move-Konstruktor, der das alte Objekt als rValue-Referenz nimmt und sich mit dessen Daten initialisiert übernimmt also die vom alten Objekt allokierten Speicherbereiche und leert das alte Objekt, im Gegensatz zu einem Kopierkonstruktor, der das alte Objekt intakt lässt und für das neue Objekt Kopien des Speichers erzeugen würde. Das Grundprinzip sei an folgendem Beispiel-Move-Konstruktor verdeutlicht (Klasse::data ist ein Zeiger auf einen Speicherbereich):

Klasse(Klasse&& rvalue) {
	this->data = rvalue->data;
	rvalue->data = 0; // Dies ist nötig! Andernfalls würde der Destruktoraufruf von rvalue (nach
	                  // Rückkehr aus diesem Konstruktor) die Daten der neue Instanz zerstören.
}

Die Standardbibliothek implementiert Move-Konstruktoren und rValue-Referenz-Überladungen des Zuweisungsoperators, wo dies sinnvoll ist. Außerdem werden, genauso wie schon bei Kopieroperatoren und -konstruktoren, unter gewissen Bedingungen diese Überladungen automatisch erzeugt. Ein C++11-Compiler nutzt, wo es ohne Abwärtskompatibilitätsprobleme möglich ist, automatisch diese Überladungen. Um die Benutzung zu erwzingen, kann std::move(obj) verwandt werden. Die STL-Funktion std::swap(a, b) wird damit in C++11 folgendermaßen optimiert:

template<typename T>
void swap(T& a, T& b) {
	T tmp(std::move(a)); // Verschiebe a nach tmp
	a = std::move(b);    // Verschiebe b nach a
	b = std::move(tmp);  // Verschiebe tmp nach a
}

Konstante Ausdrücke

C++11, constexpr

Mit dem durch C++11 eingeführten Schlüsselwort constexpr kann dem Compiler die Optimierungen von Funktionen, Konstruktoren und Variablen erleichtert werden. Das Schlüsselwort signalisiert, dass ein Objekt einen konstanten und schon zur Erstellungszeit berechenbaren Wert hat, bzw. dass ein Konstruktor ein solches Objekt erzeugt, und bei einer Funktion, dass diese einen solchen Wert liefert (constexpr-Eingabewerte vorausgesetzt). Die Berechnung wird dann tatsächlich bei der Erstellung durchgeführt und bei der Ausführung des Programms eingespart. Ist die Berechnung bei einer Funktion nicht möglich, wird die Funktion zur Laufzeit ausgeführt, als wäre sie nicht als konstanter Ausdruck deklariert. Exemplarisch sei folgender Code gezeigt:

// Diese Funktion berechnet - wie std::hypot() - die Länge der Hypothenuse eines rechtwinkligen Dreiecks.
constexpr double hypot(double t1, double t2) {
	return std::sqrt(t1*t1, t2*t2);
}

// 'var1' wird ein zur Laufzeit berechenbarer Wert zugewiesen wird, denn hypot() ist constexpr.
constexpr double var1 = hypot(3.0, 2.1);

// 'var2' wird kein zur Laufzeit berechenbarer Wert zugewiesen. hypot() ist zwar constexpr,
// aber einer ihrer Eingabewert ist es nicht.
constexpr double var = hypot((double)std::rand(), 2.1);

Diese Funktionalität unterliegt jedoch der manchmal unerfreulichen Einschränkung, dass nur Literal-Typen (etwa int oder char*) und daraus gebildete Klassen/Strukturen constexpr sein können. Der Grund ist, dass etwa eine std::string-Instanz im Konstruktor eine Allokation durchführen muss, die natürlich kein konstanter Ausdruck ist.

Rekursion und tiefe Callstacks

Rekursion, Callstacks

Rekursive Algorithmen, also solche Funktionen, die sich selbst aufrufen, gelten zwar als als ziemlich elegant und lassen sich in einigen Fällen auch einfacher als iterative Algorithmen implementieren, haben jedoch eine unerfreuliche Nebenwirkung. Derartige Funktionen neigen zu Stack-Überläufen, wenn sie sich sehr oft selbst aufrufen. Der Grund dafür ist, dass jeder Aufruf der Funktion zusätzlichen Speicher auf dem Stack konsumiert: Einerseits durch die lokalen Variablen, da jeder Aufruf der Funktion neue Instanzen dieser Variablen auf dem Stack anlegt, aber die des übergeordneten Aufrufs noch nicht wieder freigegeben wurden, andererseits erzeugt der Funktionsaufruf selbst bereits einen „Stackframe“, der bereits einige Bytes konsumiert. Derartige Stack-Überläufe kann man natürlich auch ohne Rekursion erzeugen, wenn man entweder sehr große Variablen auf dem Stack erzeugt, oder viele verschiedene Funktionsaufrufe (etwa durch Wrapper-Funktionen) verschachtelt. Aus der Java-Welt existiert dazu eine herrliche Anekdote über die Facebook-App: Durch den übertriebenen Einsatz „moderner“ Entwicklungsmethoden, in diesem Fall das Zersplittern des Codes auf unzählige Mini-Funktionen (die dann hauptsächlich nur noch Wrapper sind) und der verschachtelte Aufruf dieser ganzen Funktionen, lief der Stack der Java-VM Dalvik über. Die Pointe ist, dass die zuständigen Entwickler sich öffentlich dafür feierten, dass sie einen Weg gefunden hatten, mittels eines – der Beschreibung zufolge nur als wahnsinnig zu bezeichnenden – Hacks den Stack zu vergrößern, anstatt die Design-Fehler ihrer Software zu beheben. Für uns ist die Moral der Geschichte: Verschachtelte Funktionsaufrufe können teuer sein. Von unnötigen Wrapperfunktionen sollte man deshalb die Finger lassen, oder dem Compiler eine Chance geben, sie zu „inlinen“, was, wenn eine Funktion in mehreren Sourcedateien aufgerufen wird, entweder die Implementation der Funktion im Header, oder die Nutzung von Linkzeitoptimierung (meist „LTCG“ oder „LTO“ genannt) voraussetzt.

Überlegungen zur Implementation besserer Algorithmen

Algorithmen

In der Einleitung schrieb ich, dass in der Verbesserung der Algorithmen zwar meist das größte Verbesserungspotential liegt, sich aber leider wenig Allgemeines dazu sagen lässt, wie man das umsetzt. Ein paar Überlegungen hierzu sollen zum Abschluss dennoch angestellt werden. Äußerst hilfreich ist es, zu wissen, für welche Teile des Programmcodes überhaupt viel Rechenzeit verwandt wird. Professionell geht man an derartige Fragestellungen mithilfe eines Profilers, etwa dem in Visual Studio Integrierten (zu finden im Menü „Debuggen“), heran. Eine grundsätzliche Überlegung kann man jedoch auch ohne einen Profiler anstellen: Die meiste Zeit geht oft dafür drauf, Aktionen zu wiederholt anzuwenden, d. h. für Schleifen. Gelingt es also, die Zahl der Schleifendurchläufe zu reduzieren, ist meist viel gewonnen. Betrachten wir als Beispiel (erneut) einen Primzahltest, und zwar diesmal eine besonders ineffiziente Implementation:

bool isPrim(uint64_t zahl) {
	bool result = true;
	if (zahl < 2) result = false;
	for (uint64_t i = 2; i < zahl; i++) {
		if ((zahl % i) == 0)
			result = false;
	}
	return result;
}

Es dürfte auf Anhieb klar sein, dass dies die wahrscheinlichst langsamste denkbare Implementation ist (zählt man mit ihr alle Primzahlen im Intervall von 0 bis 100.000, dauert dies auf meinem Rechner 90257 ms). Eine wichtige und hier anzuwendende Regel lautet: Ist das Ergebnis bekannt, kann man aus der Schleife ausbrechen. Dann sparen wir uns nämlich, nachdem wir bereits einen Teiler für zahl gefunden haben, noch nach Weiteren zu suchen:

bool isPrim(uint64_t zahl) {
	if (zahl < 2) return false;
	for (uint64_t i = 2; i < zahl; i++) {
		if ((zahl % i) == 0)
			return false;
	}
	return true;
}

Dieser Code ist nicht nur schneller (8146 ms), sondern obendrein sogar kürzer. Aber es geht noch mehr. Gibt es irgendeinen Grund, überhaupt zu prüfen, ob etwa die Zahl 100 sich durch 99 teilen lässt? Nein – es ist auf Anhieb absehbar, dass das nicht gelingen wird. Insgesamt scheidet jede Zahl oberhalb von 100/2=50 als Teiler aus. Aufgrund des Kommutativgesetzes kann man sogar schon bei Wurzel 100 abbrechen, weil dann bereits jede denkbare Kombination geprüft wurde:

bool isPrim(uint64_t zahl) {
	if (zahl < 2) return false;
	for (uint64_t i = 2; i*i <= zahl; i++) { // Dies ist besser als i <= sqrt(zahl), weil sqrt() eine langsame Fließkommaoperation ist.
		if ((zahl % i) == 0)
			return false;
	}
	return true;
}

Von besonderer Bedeutung ist, dass die Laufzeit mit der Größe der geprüften Zahl nun langsamer ansteigt. Optimal ist das Ergebnis (42 ms) jedoch noch immer nicht, denn es lässt sich noch immer jeder zweite Schleifendurchlauf einsparen, wenn man vorab einmal testet, ob zahl durch 2 teilbar ist:

bool isPrim(uint64_t zahl) {
	if (zahl < 2) return false;
	if (zahl == 2) return true;
	if ((zahl % 2) == 0) return false;
	for (uint64_t i = 3; i*i <= zahl; i += 2) { // Überspringe alle geraden Zahlen.
		if ((zahl % i) == 0)
			return false;
	}
	return true;
}

Diese letzte Implementation ist mit 21 ms im o. g. Test-Setup um 99,95 % schneller als die erste Variante. Es gibt zwar noch deutlich schnellere, aber dann auch mathematisch anspruchsvollere Primzahltests. Dieses Beispiel diente jedoch dazu, zu zeigen, wie sich bereits mit einfachen Überlegungen die Anzahl der Schleifendurchläufe und damit einhergehend die Programmlaufzeit drastisch reduzieren lassen.

Abschluss und Danksagung

Damit wären wir am Ende dieses kleinen Tutorials. Ich wünsche Ihnen viel Spaß und Erfolg dabei, die hier dargestellten Tipps in der Praxis auszuprobieren. Abschließend danke ich noch Dr. Erhard Henkes und dem c-plusplus.net-Forum, deren Experimente zum Testen der Goldbachschen Vermutung mich auf die Idee gebracht haben, diesen Artikel zu schreiben. Diese Inspiration trägt auch die Verantwortung dafür, dass ein Primzahltest hier so oft als Beispiel dienen musste.