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@gmx.at. 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 *2^y   und   x >> y == x / 2^y
• 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@gmx.at

Tutorial vom 26.06.2001