Tutorial 1: Programmoptimierungen
Willkommen zum ersten rand()-Tutorial von Kongo. Das erste Tutorial ist der
Optimierung von Programmen gewidmet, um noch schnelleren Code zu schreiben.
Bei irgendwelchen Fragen, Beschwerden, Wünschen (z.B. fürs nächste
Tutorial) schreib an kongo@codeworx.org.
Wenn du für diese Kapitel noch Informationen hast und du denkst dir: "Das
muss auch noch rein!", dann schreib mir. Ich werde dieses Tutorial dann
nachbessern. Feedback ist Willkommen.
Jedes Spiel, das man programmiert, soll noch schneller und besser werden. Jedoch
kann der Code den man selbst schreibt, schnell die Performance drücken.
Wie kann man noch schnelleren Code schreiben? Dies sind nur Aufzählungen
von Programmierkniffen, also probier einfach herum.
Mathematische Tricks
- Verwende Integer mit Integer und Floats mit Floats. Konvertierungen sind
langsam, darum vermeide sie bis zum Schluß.
- Vermeide Divisionen - Divisionen brauchen bis zu 39 mal länger als andere
Operationen. Als Beispiel sei gegeben das Normalisieren eines Vektors. Normalerweise
wird der normalisierte Vektor berechnet, indem alle Elemente durch seine Länge
dividiert werden. Das wären 3 Divisionen. Schneller wäre es, wenn
wir 1/'Länge des - Vektors' rechnen und dann alle Elemente des Vektors
mit diesem Faktor multiplizieren. Jetzt haben wir nur mehr 1 Division und 3
Multiplikationen.
- Multiplikationen oder Divisionen können durch Bit-Shifts ersetzt werden.
x << y == x *2y und x >> y == x / 2y
- Um Ein Array von Floats auf 0 zu setzen, verwende folgenden Code: memset(
(void*)float_array, 0, sizeof(float)*num_floats );
- Wenn du weißt, dass du einen Wert ein paar Zeilen später wieder
benötigst, speichere in anstatt in noch mal zu berechnen.
- a*b + a*c = a*(b+c); Dadurch erspart man sich eine Multiplikation.
- b/a + c/a = (1/a) * (b+c); Hier ersetzt man zwei Divisionen durch eine Division
und einer Multiplikation. Da multiplizieren schneller ist als dividieren, spart
man ein bisschen Prozessorzeit.
Misc
- Anstatt Schleifen, schreibe diese wenn möglich aus.
- Funktionen wie sin, cos, tan, exp, arcsin,... sind nicht sehr schnell. Hier
wäre eine Tabelle, mit vorberechneten Werten um einiges schneller.
- Verwende für kleine Funktionen die öfters verwendet werden das inline
Schlüsselwort. (inline, __inline, __forceinline)
- Die Float-Konstante float x = 2.42f; ist schneller als x = 2.42; Wenn du f
nicht dem konstanten Wert hinzufügst, werden solche Ausdrücke zu double
konvertiert.
- Versuche Algorithmen auf verschiedene Weisen zu implementieren. Präfix-Dekrementierung
--cnt kann auf manchen Compilern weniger Code erzeugen als Postfix-Dekrementierung
cnt--.
- Verwende const so oft wie möglich. Der Compiler könnte es als Hinweis
zum optimieren verstehen.
- Sende nie Strukturen oder Werte, die größer als 4-Byte sind, per
Wert (by Value). Parameterübergabe per Adresse (by Adress) ist da schneller,
da kleinere Werte auf den Heap gelegt werden.
- Daten sollten in der Reihenfolge in den Speicher geladen werden, wie sie auch
verwendet werden.
- Verwende für zeit-kritische Funktionen keine Parameter. Verwende globale
Variablen. Dadurch erspart du dir, das die Werte auf den Heap gelegt werden
und von dort wieder entfernt werden.
- Die Funktionen malloc() und free() sind auf manchen Systemen langsam. Reserviere
daher am Anfang einen größeren Bereich und teile diesen dann auf,
anstatt immer wieder diese Funktionen aufzurufen.
- Verwende 32-Bit Variablen. Heutige Prozessoren sind total 32-bit. Das bedeutet,
sie mögen keine 8- oder 16-bit Werte.
- Einfache Instruktionen sind für den Compiler einfacher zu verstehen.
Anstatt Instruktionen in Eine zusammenzufassen, teile sie auf.
- Integers sind bei Additionen und Subtraktionen schneller als Floats.
- Purer Assembler Code ist der letzte Ausweg, um best. Funktionen schneller
zu machen. Versuche eher einen besseren Alogrithmus zu finden.
- Versuche verschiedene Compileroptionen, anstatt immer die Standardeinstellungen
zu verwenden.
Zeiger-Dereferenzierung
Code wie dieser:
for (int i = 0; i < Num; i++)
{
Render_Context->Back->Surf->bit[i] = Val;
}
kann durch folgenden ersetzt werden:
unsigned char *Surf_Bits = Render_Context->Back->Surf->Bit[0];
for (int i = 0; i < Num; i++)
{
Surf_Bits[i] = Val;
}
Dadurch ersparst du dir die ganzen Zeiger Dereferenzierungen, die ja eigentlich
unnötig sind.
Schnellere Klassen
Unser Beispiel für dieses Unterkapitel ist eine Klasse für Vektoren.
Wir haben ein paar Operatoren überladen, einen Konstruktor, Kopierkonstruktor
und einen Destruktor geschrieben.
class Vector3
{
float m_x;
float m_y;
float m_z;
Vector3();
Vector3(Vector3& vec);
~Vector3();
Vector3 operator+(Vector3 vec);
Vector3 operator*(Vector3 vec);
};
So.. das erste was wir hier überlegen ist, brauchen wir den Destruktor?
Der Compiler kann einen mindestens gleich schnellen Leer-Destruktor erstellen.
Wir haben nichts, dass einen Destruktor benötigt. Des weiteren können
wir versuchen die Operatorfunktionen schneller zu machen. Hier ein Beispiel
für eine nicht sehr gut durchdachte Funktion des Operator +.
Vector3 operator+(Vector3 vec)
{
Vector3 retVec;
retVec.m_x = m_x + vec.m_x;
retVec.m_y = m_y + vec.m_y;
retVec.m_z = m_z + vec.m_z;
return retVec;
}
Hier gibt es sehr viel zu optimieren. Fangen wir einfach ganz oben an. Der
Parameter wird per Wert übergeben. Daraus folgt, dass Speicher allokiert
wird und der Kopierkonstruktor aufgerufen wird. Besser wäre es, eine Referenz
auf den Vektor zu machen. Des weiteren haben wir eine Variable bereitgestellt,
die die neuen Werte nimmt und dann wieder zurückgibt. Daraus folgt, dass
wir erstens wieder einen Aufruf eines Konstruktors haben, obwohl wir die Werte
ja sowieso ändern und zweitens wird am Schluß der Kopierkonstruktor
aufgerufen, da retVec ja eine lokale Variable ist.
Unsere optimierte Funktion sieht wie folgt aus:
Vector3 operator+( const Vector3 &vec) const
{
return Vector3(m_x + vec.m_x, m_y + vec.m_y, m_z + vec.m_z);
}
Zusätzlich haben wir einen neuen Konstruktor geschrieben, der die drei
Werte annimmt. Wir ersparen uns in der optimierten Funktion drei Kopierkonstruktoraufrufe.
Das ist zwar nicht viel Ersparnis im Großen, jedoch für eine so kleine
Funktion kann dies eine große Zeitersparnis bedeuten.
SIMD
SIMD (oder auch Intel's Streaming SIMD Extensions) bedeutet Single Instruction
Multiple Data. Also eine Instruktion, mehrere Daten. SIMD ist eine Erweiterung
der Pentium-Prozessoren, durch die wir noch schnelleren Code schreiben können.
Mit den SIMD Extensions können wir zB. 4 Multiplikationen oder 4 Additionen
auf einmal berechnen. Ein SIMD Register kann 4 floating-point Variablen beinhalten.
Also können wir in ein Register einen ganzen Vektor laden, oder in vier
Register eine ganze 4x4-Matrix.
Für eine Matrix*Matrix Funktion benötigen wir standardmäßig
64 Multiplikationen und 48 Additionen. Mit SIMD benötigen wir jedoch nur
mehr 16 Multiplikationen und 12 Additionen. Dadurch ersparen wir uns sehr viel
Zeit in der Berechnung für diese Matrix*Matrix Funktion.
Unter den Links ganz unten, findest du ein Tutorial für SIMD: 'An Optimized
Matrix Library'.
Assembler Optimierungen
Unter Visual C++ (6.0) kann man sich den Assemblercode, den der Compiler erstellt,
ausgeben lassen. Dadurch kann man untersuchen, wie genau und gut der Compiler
arbeitet. Selbstgeschriebener Assemblercode ist immer schneller als jeder Compiler.
Compiler können nicht so gut sein, dass sie das händische nacharbeiten
ersetzen. Unter 'Optionen' -> 'Einstellungen' -> Reiter 'C/C++' kann man
unter 'Typ der Listing-Datei:' den Typ der Ausgabedatei einstellen. Hier können
wir Kombinationen von Assembler-, Maschinen- und Quellcode auswählen. Für
jede Quelldatei (*.cpp) wird jetzt eben diese Datei zusätzlich erstellt.
Links
Jim
Blinn's Corner: Optimizing C++ vector Expressions
An
Optimized Matrix Library in C++
Cleaning
Memory and Partial Register Stalls in Your Code
GameDev:
Performance Programming Applied to C++
Flipcode
Tutorial: Faster Vector Math Using Templates
Bücher
Dov Bulka, David Mayhew: Efficient C++ Performance Programming Techniques.
Addison Wesley, ISBN 0-201-37950-3
Copyright (c) by Kongo
Bei Fragen, Beschwerden, Wünschen E-mail an kongo@codeworx.org
Tutorial vom 26.06.2001