Programme optimieren

„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 („cacht“), 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 cachen. 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.

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:

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.

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, std::basic_string (und dessen Abkommen wie std::string), std::unordered_set und std::unordered_map 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", "!"};

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.

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.

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.

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.

struct array { int ints[100]; };

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

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

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

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.
}

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
}

// 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);

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;
}

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;
}

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;
}

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;
}