Performancetuning

Martin Kompf

Stoppuhr Wenn die Programmausführung quälend langsam vonstatten geht, dann ist ein Tuning der Performance nötig. Wir zeigen, wie dies mittels einfacher C++ Bordmittel möglich ist.

Zeigt eine Software nicht die gewünschte Ausführungsgeschwindigkeit, so bedient sich der Entwickler in der Regel eines Profilers, um die performancekritischen Abschnitte einzugrenzen. Solche Profiler erfordern allerdings eine gewisse Einarbeitungszeit. Im folgenden wird daher eine einfache Methode vorgestellt, die bei kleineren Projekten ebenfalls zum Ziel führen kann.

Das Beispiel

Zur Demonstration verwenden wir ein kleines Beispielprogramm, welches 50000 Zufallszahlen erzeugt und in einem Vektor speichert. Anschließend werden das größte und kleinste Element des Vektors berechnet und ausgegeben:

#include <iostream>
#include <vector>
#include <cstdlib>
 
using namespace std;
 
int main()
{
    vector<int> vi;
 
    for (int i = 0; i < 50000; ++i) {
        vi.insert(vi.begin(), rand());
    }
     
    vector<int>::const_iterator imax = max_element(vi.begin(), vi.end());
    cout << "The largest element is " << *imax << endl;
 
    vector<int>::const_iterator imin = min_element(vi.begin(), vi.end());
    cout << "The smallest element is " << *imin << endl;
}

Beim Ausführen des Programms zeigt sich, dass es eine Laufzeit von über einer Sekunde hat, was nicht akzeptabel ist. Um das Programm beschleunigen zu können, muss der Entwickler zunächst erst einmal feststellten, wo genau sich der Flaschenhals befindet: Ist die Erzeugung des Vektors so langsam oder nimmt die Ermittlung von Minimum und Maximum zu viel Zeit in Anspruch?

Wo ist der Flaschenhals?

Zur Ermittlung der Laufzeit von Programmteilen kann man sich der Funktion clock() aus der Standard C Library bedienen. Sie liefert einen von der Ausführungszeit des Programmes abhängigen Zählerstand zurück. Man kann sich nun vor dem kritischen Programmabschnitt diesen Zählerstand holen und in einer Variablen vom Typ clock_t zwischenspreichern. Am Ende des Programmabschnittes ruft man wieder clock() auf und bildet die Differenz zum gemerkten Zählerstand. Um von dieser Differenz auf eine in Sekunden gemessene Zeit zu kommen, muss man den Wert noch durch die in <time.h> definierte Konstante CLOCKS_PER_SEC dividieren.

Diesen Ablauf wollen wir in einer kleinen Hilfsklasse timer kapseln:

#include <ctime>
#include <iostream>
 
using namespace std;
 
class timer
{
public:
    timer(int number = 0) : n(number), start(clock()) { }
    ~timer();
private:
    int n;
    clock_t start;
};
 
inline timer::~timer()
{
    cout << "timer " << n << " took "<< double(clock()-start)/CLOCKS_PER_SEC
        << " seconds" << endl;

}

Die Zeitmessung gestaltet sich mittels dieser Klasse sehr einfach: Zunächst wird der auszumessende Programmabschnitt durch Umfassen mit geschweiften Klammern { } zu einem Block zusammengefasst. Unmittelbar am Anfang dieses Blocks wird nun ein Objekt der Klasse timer statisch erzeugt - das ist alles! Wir machen dabei davon Gebrauch, dass bei der Erzeugung eines Objektes dessen Konstruktor aufgerufen wird (das initialisiert die Variable start mit clock()) und dass beim Verlassen des Gültigkeitsbereiches einer Variablen (also am Ende des Blocks) der Destruktor des Objekts ausgeführt wird. Im Destruktor von timer erfolgt dann die beschriebene Messung und Ausgabe der Zeitdifferenz.

Die Messung bringt es ans Tageslicht

Unser Beispielprogramm wird nun durch zwei Zeitmessungen ergänzt: Eine für die Vektorerzeugung und eine für die Minimum-/Maximumbestimmung:

int main()
{
    vector<int> vi;
 
    {
    timer t0(0);
     
    for (int i = 0; i < 50000; ++i) {
        vi.insert(vi.begin(), rand());
    }
    }
  
    {
    timer t1(1);
    
    vector<int>::const_iterator imax = max_element(vi.begin(), vi.end());
    cout << "The largest element is " << *imax << endl;
 
    vector<int>::const_iterator imin = min_element(vi.begin(), vi.end());
    cout << "The smallest element is " << *imin << endl;
    }
}

Nach erneutem Compilieren und Ausführen des Programms erhalten wir interessante Informationen:

timer 0 took 5.878 seconds
The largest element is 32767
The smallest element is 1
timer 1 took 0 seconds

Beschleunigt

Die meiste Zeit wird also beim Einfügen der Vektorelemente verbraten! Wir können uns bei der Optimierung des Programmes nun ausschließlich auf diesen Teil konzentrieren. Der mit den STL Containern vertraute Entwickler erkennt auch sofort das Problem: Das Einfügen eines Elements an den Anfang eines Vektors ist eine sehr zeitaufwendige Operation, da dabei alle Vektorelemente nach hinten verschoben werden müssen. Besser und schneller ist hier das Anfügen des neuen Elements am Ende des Vektors. Wir ersetzen also

        vi.insert(vi.begin(), rand());

durch

        vi.push_back(rand());

und lassen das Programm nochmals ablaufen. Die Zeitmessung zeigt nun eindrucksvoll den Erfolg des Tunings:

timer 0 took 0.01 seconds
The largest element is 32767
The smallest element is 1
timer 1 took 0 seconds

Weitere interessante Artikel:

Links zum Thema: