Modernes C++ in der Praxis – Folge 3

Die wegweisenden Artikel "The Free Lunch is Over" [1] und "Welcome to the Jungle" [2] der C++-Koryphäe Herb Sutter bringen ein Problem moderner Software-Entwicklung auf den Punkt: Der Gleichschritt bei Performanceverbesserung der CPU und Anforderungen der Software ist nach 30 Jahren merklich aus dem Takt geraten. Es reicht nicht mehr aus, einfach auf eine schnellere CPU zu setzen. In der modernen Hardwarewelt müssen Programmiersprachen mit homogenen, ja sogar mit heterogenen Multicore-Architekturen umgehen können. C++11 schafft das mit Hilfe der neuen Multithreading-Funktionalität.

Rechenaufgabe

Bevor diese Artikelserie auf deren verzwickte Details eingeht, soll zuerst ein einfaches Beispiel den Respekt vor dem Unbekannten nehmen. Das Skalarprodukt zweier gleich großer Vektoren »v« und »w« der Länge »n+1« ist (vereinfacht) dadurch definiert, dass die einzelnen Werte »v[i]« und »w[i]« multipliziert und deren Produkte addiert werden:

v[0]*w[0] + v[1]*w[1] + ... v[n]*w[n]

Wem diese Erklärung nicht formal genug ist, der sei auf [3] verwiesen. Die Berechnung erledigt in Listing 1 der Algorithmus »std::inner_product()« aus der Standard Template Library [4].

01 #include <chrono>
02 #include <iostream>
03 #include <random>
04 #include <vector>
05
06 static const int NUM= 10000000;
07
08 long long getDotProduct(std::vector<int>& v,std::vector<int>& w){
09   return std::inner_product(v.begin(),v.end(),w.begin(),0LL);
10 }
11
12 int main(){
13
14   std::cout << std::endl;
15
16   // get NUM random numbers from 0 .. 100
17   std::random_device seed;
18
19   // generator
20   std::mt19937 engine(seed());
21
22   // distribution
23   std::uniform_int_distribution<int> dist(0,100);
24
25   // fill the vectors
26   std::vector<int> v, w;
27   v.reserve(NUM);
28   w.reserve(NUM);
29   for (int i=0; i< NUM; ++i){
30     v.push_back(dist(engine));
31     w.push_back(dist(engine));
32   }
33
34   // measure the execution time
35   std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
36   std::cout << "getDotProduct(v,w): " << getDotProduct(v,w) << std::endl;
37   std::chrono::duration<double> dur  = std::chrono::system_clock::now() - start;
38   std::cout << "Sequential Execution: "<< dur.count() << std::endl;
39
40   std::cout << std::endl;
41
42 }

Das abgedruckte Programm berechnet das Skalarprodukt zweier Vektoren mit 10 Millionen Elementen. Die Rechenarbeit findet in der Funktion »getDotProduct()« in Zeile 8 statt. Ungewöhnlich ist nur die Initialisierung des Rückgabewerts »0LL« . Dieses C++11-Literal steht für die Zahl »long long 0« und stellt sicher, dass das Ergebnis der summierten Multiplikationen in den Rückgabetyp passt.

Diese ungewöhnlich große Variable ist notwendig, denn das Ergebnis des Skalarprodukts (Abbildung 1) bewegt sich in einem sehr hohen Bereich: Der Datentyp »long long« kann Zahlen im Wertebereich von mindestens -9 223 372 036 854 755 808 bis +9 223 372 036 854 755 807 (mehr als 9 Trillionen) darstellen. Einen schönen Überblick über Datentypen für verschieden große natürliche Zahlen gibt der Wikipedia-Artikel unter [5].

Abbildung 1: Berechnen des Skalarprodukts durch einen einzigen Thread.

Zufall beschafft Material

Um die Vektoren in den Zeilen 30 und 31 (Listing 1) mit Werten für das Rechenbeispiel zu füllen, initialisiert Zeile 20 den Zufallszahlenerzeuger mit einem zufälligen Startwert. Dieser produziert gleich verteilte Zufallszahlen im Bereich von 0 bis 100. Die Zeilen 27 und 28 stellen mit »v.reserve(NUM)« sicher, dass der Speicher für den Vektor in einem Rutsch reserviert wird. Das ergibt bei Vektoren dieser Länge durchaus Sinn, denn es erspart das aufwändige mehrfache Reservieren von Speicher. Zeile 36 veranlasst die Berechnung und gibt das Skalarprodukt der zwei Vektoren aus. Dank der neuen Zeitbibliothek »chrono« ist ziemlich einfach zu bestimmen, wie lange das Ausführen der Funktion dauert. Zeile 35 ermittelt die Zeit vor dem Funktionsaufruf, Zeile 37 stellt die Zeit danach fest und berechnet die Zeitdifferenz.

Wer eine kompakte Darstellung der neuen Zeitbibliothek sucht, wird in der Webpräsenz von Anthony Williams [6] fündig. Abbildung 1 zeigt, wie lange der PC des Autors zum Berechnen des Skalarprodukts braucht.