C++17 und C++20: Gleichzeitigkeit in modernem C++
Eine, wenn nicht die Herausforderung für eine moderne Programmiersprache ist es, die Power, die in jedem modernen Rechner steckt, auf sichere Weise herauszukitzeln. Das ist mit bisherigen Multithreading-Abstraktionen für den sterblichen Programmierer nicht möglich. Daher bietet C++17 und vor allem C++20 deutlich bessere Abstraktionen an, die die bisherigen Abstraktionen atomare Variablen, Threads, Bedingungsvariablen oder Mutexe und Locks auf die Stufe einer Assemblersprache für Gleichzeitigkeit degradieren. Doch welche Abstraktionen werden wir in naher Zukunft erhalten und auf welche Abstraktionen können wir in ferner Zukunft hoffen? Genau diese Fragen werde ich in zwei Artikeln verfolgen.
Bevor es aber um diese Frage geht, steht ein kleiner Umweg an. Es gilt, die Begriffe Gleichzeitigkeit (engl. Concurrency), Parallelisierung und Multithreading zu klären: Gleichzeitigkeit ist der Oberbegriff, der Parallelisierung mit einschließt. Gleichzeitigkeit bedeutet, dass mehrere Aufgaben sich zeitlich überschneiden. Das bedeutet aber nicht, dass diese Aufgaben zum selben Zeitpunkt ausgeführt werden. Diese Eigenschaft zeichnet die Parallelisierung aus, bei der mehrere Aufgaben zeitgleich ausgeführt werden. Multithreading ist ein Implementierungdetail. Genausogut kann das Programm gleichzeitig auf mehreren Prozessen ausgeführt werden. In diesem Fall sprechen wir natürlich von Multiprocessing.
Jetzt kann es losgehen. Zuerst gilt es, das große Bild im Auge zu behalten.
Gleichzeitigkeit in C++
Der Zeitstrahl besitzt eine starke Tendenz nach rechts, denn mit der parallelen Standard Template Library (STL) in C++17 und insbesondere atomaren Smart Pointern, den std::future-Erweiterungen, Latches und Barrier, Coroutinen, Transactional Memory und Task-Blöcken in C++20 wird C++ um viele neue Konzepte erweitert, die alle Inhalt dieses und des nächsten Artikels sein werden.
Dieser Artikel wird die Parallelisierung zum Fokus haben. Genauer ausgedrückt, geht es um die Parallele Algorithmen der STL und die Task-Blöcke zum parallelen Ausführen von Aufgaben.
C++17: Parallele Algorithmen der STL
Die Idee ist schnell skizziert. Die Standard Template Library enthält gut 100 Algorithmen für das Suchen, Zählen und Manipulieren von Bereichen und deren Elemente. Mit C++17 wurden 69 der Algorithmen überladen und 8 neue Algorithmen hinzugefügt. Diese überladenen und neuen Algorithmen können mit einer sogenannte Execution Policy aufgerufen werden. Mit dieser Execution Policy lässt sich spezifizieren, ob der Algorithmus sequentiell, parallel oder parallel und vektorisiert ausgeführt wird. Vektorisierung bezeichnet die SIMD-Erweiterung (Single Instruction, Multiple Data) [1] des Befehlssatzes moderner Prozessoren, die eine Operation parallel auf mehreren Daten ausführen können. Welche überladene Version eines Algorithmus ausgewählt wird, steuert der Anwender über das sogenannte Policy Tag.
Ein einfaches Beispiel soll die Strategie der Algorithmen verdeutlichen.
vector<int> v = ...
// standard sequential sort
std::sort(v.begin(), v.end());
// sequential execution
std::sort(std::parallel::seq, v.begin(), v.end());
// permitting parallel execution
std::sort(std::parallel::par, v.begin(), v.end());
// permitting parallel and vectorized execution
std::sort(std::parallel::par_unseq, v.begin(), v.end());Schön ist an dem kleinen Beispiel zu sehen, dass die klassische Variante von std::sort (Zeile 4) mit C++17 immer noch zu Verfügung steht. Dagegen lässt sich jetzt mit C++17 explizit die sequentielle (7), die parallele (10) oder auch die parallele und vektorisierende Variante (13) von std::sort anfordern.
Zwei Besonderheiten gilt es aber im Kopf zu behalten: Zum einen muss ein mit der Exection Policy std::parallel::par_unseq versehener Algorithmus nicht parallel und vektorisiert ausgeführt werden. Zum anderen ist der Anwender für die richtige Anwendung des Algorithmus verantwortlich.
Ob ein Algorithmus parallel und vektorisierend (std::parallel::par_unseq) ausgeführt werden kann, hängt von vielen Faktoren ab. Unter anderem davon, ob die CPU und das Betriebssystem SIMD-Anweisungen unterstützen. Natürlich ist es auch eine Frage des Compilers und Optimierungslevels, mit dem der Code übersetzt wird. Bereits der kleine Codeschnipsel bringt mithilfe des online Compiler Explorer [2] diese interessanten Fakten ans Licht.
Zuerst der kleine Codeschnipsel:
const int SIZE= 8;
int vec[]={1,2,3,4,5,6,7,8};
int res[]={0,};
int main(){
for (int i= 0; i < SIZE; ++i){
res[i]= vec[i]+5;
}
}
res[i]= vec[i]+5 ist die entscheidende Zeile des Programms. Wird das Programm ohne Optimierung mit einem clang 3.6-Compiler übersetzt, erzeugt dieser für (Zeile 8) die Assembler Anweisungen in Abb.3.
Auch ohne tiefe Assembler-Kenntnisse ist klar: Hier findet alles sequentiell statt. Das ändert sich aber, wenn der clang 3.6 mit maximaler Optimierung (-O3) zum Einsatz kommt. Jetzt finden die Operationen auf mehreren Elementen gleichzeitig statt. Abb.4 zeigt die resultierenden Assembler-Anweisungen.
Sowohl die move-Operationen (movdqa) als auch die add-Operationen (paddd) arbeiten auf den besonderen Registern xmm0 und xmm1. Beide Register sind sogenannte SSE-Register und 128 Bits groß. SSE steht für Streaming SIMD Externsions [3].
Der Anwender ist für die richtige Anwendung der Algorithmen verantwortlich. Was heißt das? Die Algorithmen schützen nicht automatisch vor kritischen Wettläufen [4] (data races) oder Verklemmungen (deadlocks). Beispiel gefällig?
int numComp= 0;
std::vector<int> vec={1,3,8,9,10};
std::sort(std::parallel::vec, vec.begin(), vec.end(),
[&numComp](int fir, int sec){ numComp++; return fir < sec; });Das kleine Programmbeispiel enthält bereits einen kritischen Wettlauf um die Variable numComp. numComp (Zeile 1) soll die Anzahl der Operationen zählen. Das heißt insbesondere, in der Lambda-Funktion (Zeile 4) wird auf numComp lesend und schreibend zugegriffen. Damit besitzt der Code undefiniertes Verhalten. Um ein wohldefiniertes Programm zu erhalten, muss der Zugriff auf numComp atomar sein.
Die Exection Policy legt fest, ob ein Algorithmus sequentiell std::parallel::seq, parallel std::parallel::par oder parallel und vektorisierend std::parallel::unseq ausgeführt. Diese Entscheidung kann im Sourcode (statisch) oder zur Laufzeit (dynamisch) getroffen werden. Warum ist das notwendig? Die Erzeugung eines Threads ist eine teure Operation. Daher macht es keinen Sinn, einen Container mit wenigen Elementen mit einer parallelen oder parallel und vektorisierenden Strategie zu sortieren. In diesem Fall frisst der Verwaltungsaufwand den Vorteil der Parallelisierung mehr als auf. Noch drastischer können die Nebenwirkungen sein, wenn ein Teile-und-Herrsche-Algorithmus (divide and conquer algorithm) [5] zum Einsatz kommt. Ein klassisches Beispiel für einen Teile-und-Herrsche-Algorithmus ist der Quicksort-Algorithmus in Listing 1.
C++ - Listing 1: Der parallelisierte Quicksort Algorithmus
template
void quicksort(ForwardIt first, ForwardIt last){
if(first == last) return;
auto pivot = *std::next(first, std::distance(first,last)/2);
ForwardIt middle1 = std::partition(std::parallel::par, first, last,
[pivot](const auto& em){ return em < pivot; });
ForwardIt middle2 = std::partition(std::parallel::par, middle1, last,
[pivot](const auto& em){ return !(pivot < em); });
quicksort(first, middle1);
quicksort(middle2, last);
}
Jeder std::partition-Aufruf in Zeile 5 und 7 findet parallel statt. Hier ist die Gefahr natürlich groß, dass die Anzahl der gestarteten Threads deutlich zu groß für das System wird. Umso besser, dass es in C++17 auch eine dynamische Execution Policy gibt. Listing 2 stellt die ressourcenschonende Alternative vor.
C++ - Listing 2: Der parallelisierte Quicksort-Algorithmus mit dynamischer Execution Policy in C++17
std::size_t threshold= ...; // some value
template
void quicksort(ForwardIt first, ForwardIt last){
if(first == last) return;
std::size_t distance= std::distance(first,last);
auto pivot = *std::next(first, distance/2);
std::parallel::execution_policy exec_pol= std::parallel::par;
if ( distance < threshold ) exec_pol= std::parallel_execution::seq;
ForwardIt middle1 = std::partition(exec_pol, first, last,
[pivot](const auto& em){ return em < pivot; });
ForwardIt middle2 = std::partition(exec_pol, middle1, last,
[pivot](const auto& em){ return !(pivot < em); });
quicksort(first, middle1);
quicksort(middle2, last);
}
In Zeile 12 und 13 kommt die dynamische Execution Policy zu Einsatz. Per Default wird Quicksort parallel ausgeführt (Zeile 9). Falls aber die Länge des zu sortierenden Bereichs kleiner als eine vorgegebene Schwelle threshold (Zeile 1) ist, wird Quicksort sequentiell ausgeführt (Zeile 10).
69 der Algorithmen unterstützen eine parallel oder parallele und vektorisierende Execution Policy. In Abb.5 sind die Kandidaten.
Das ist noch nicht alles. Dazu gibt es acht neue Algorithmen (Listing 3).
C++ - Listing 3: Die acht neuen Algorithmen
std::for_each
std::for_each_n
std::exclusive_scan
std::inclusive_scan
std::transform_exclusive_scan
std::transform_inclusive_scan
std::parallel::reduce
std::parallel::transform_reduce
Besonders interessant ist std::parallel::transform_reduce. Warum? Die aus Haskell bekannte Funktion map entspricht der Funktion std::transform in C++. Wenn das kein Wink mit dem Zaunpfahl ist. Denn wird in dem Name std::parallel::transform_reducetransform durch map ersetzt, so heißt der Algorithmus std::parallel::map_reduce. MapReduce [6] ist das weltweit eingesetzte, parallele Framework, das in seiner ersten Phase jeden Wert auf einen neuen Wert abbildet und in seiner zweiten Phase diese neuen Werte auf das Ergebnis reduziert.
Dieser zweistufige Algorithmus lässt sich jetzt direkt in C++17 anwenden. So bildet in Listing 4 die Transform-Phase jedes Wort auf seine Länge ab und summiert die Reduce-Phase die Länge aller Wörter auf. Als Startwert kommt die 0 zum Einsatz.
C++ - Listing 4: MapReduce in C++17
std::vector str{"Only","for","testing","purpose"};
std::size_t result= std::parallel::transform_reduce(std::parallel::par,
str.begin(), str.end(),
[](std::string s){ return s.length(); },
0, [](std::size_t a, std::size_t b){ return a + b; });
std::cout << result << std::endl; // 21
Das Ergebnis ist die Summe aller Wörter eines Vektors. Parallel geht es weiter mit C++20.
Task-Blöcke mit C++
Task-Blöcke setzen das beliebte Fork-Join-Paradigma für die parallele Ausführung von Aufgaben um. Der Name Fork-Join lässt sich in einer Graphik (Abb.6) einfach erklären.
Wie funktioniert das Ganze? Der Erzeuger-Thread ruft define_task_block oder define_task_block_restore_thread auf. Dadurch steht ein Task-Block zur Verfügung, der neue Tasks erzeugen oder auf diese warten kann. Am Ende des Task-Blocks findet die Synchronisation statt. Das Erzeugen der neuen Tasks ist die Fork-Phase, die Synchronisation der Tasks die Join-Phase des Fork-Join-Prozesses. Zugegeben, die Idee des Paradigma ist überzeugend einfach. Wie schaut das Ganze im Code aus? Listing 5 stellt vor, wie sich mit dem Paradigma eine Baumstruktur rekursiv prozessieren lässt.
C++ - Listing 5: Rekursive Prozessierung einer Baumstruktur
Template
int traverse(node& n, Func && f){
int left = 0, right = 0;
define_task_block(
[&](task_block& tb){
if (n.left) tb.run([&]{ left = traverse(*n.left, f); });
if (n.right) tb.run([&]{ right = traverse(*n.right, f); });
}
);
return f(n) + left + right;
}
traverse in Listing 5 ist eine Funktions-Template, das auf jedem Knoten des Baumes node mit zwei Kindern die Funktion f (Zeile 2) aufruft. Das Schlüsselwort define_task_block definiert den Task-Block. In diesem kann der Task-Block tb neue Tasks starten. Genau das findet für den linken und rechten Zweig des Baumes in Zeile 6 und 7 statt. Zeile 9 stellt das Ende des Task-Blocks dar und ist damit der Synchronisationspunkt.
Das war schon der grobe Überblick. Jetzt folgen ein paar Details zu den Task-Blöcken. Der feine Unterschied zwischen define_task_block und define_task_block_restore_thread ist, dass bei define_task_block_restore_thread der Erzeuger-Thread des Task-Blocks auch nach dem Ende des Task-Blocks wieder der Thread ist, der die weiteren Anweisungen ausführt. Dies lässt sich am einfachsten an einem Codesbeispiel in Listing 6 aufzeigen.
C++ - Listing 6: define_task_block versus define_task_block_restore_thread
...
define_task_block([&](auto& tb){
tb.run([&]{[] func(); });
define_task_block_restore_thread([&](auto& tb){
tb.run([&]([]{ func2(); });
define_task_block([&](auto& tb){
tb.run([&]{ func3(); }
});
...
...
});
...
...
});
...
...
Task-Blöcke sichern zu, dass der Erzeuger-Thread des äußersten Task-Block (Zeile 2 - 14) nach dem Beenden des Tasks-Blocks auch wieder zum Zuge kommt. Das heißt, der Thread der die Anweisung in Zeile 2 ausführt, führt auch die Anweisungen in Zeile 15 und 16 wieder aus. Diese Zusicherung gilt aber nicht für alle verschachtelten Task-Blöcke. Daher führt der Erzeuger-Thread des Task-Blocks in Zeile 6 - 8 nicht automatisch die Zeilen 9 und 10 aus.
Ist diese Anforderungen notwendig, muss die Funktion define_task_block_restore_thread (Zeile 4) verwendet werden. Nun gilt, der Thread, der die Anweisung in Zeile 4 ausgeführt hat, führt auch die Anweisungen in Zeile 12 und 13 aus.
Ein Task-Block tb besitzt ein sehr eingeschränktes Interface. Er kann nicht explizit erzeugt werden. Dazu sind die zwei bereits verwendeten Funktionen define_task_block oder define_task_block_restore_thread notwendig. Der Task-Block tb ist in seinem Bereich sofort aktiv und kann daher eine neue Aufgabe durch tb.run starten oder warten (tb.wait), bis die Aufgabe fertig ist. Listing 7 zeigt die Methoden des Task-Blocks tb in der Anwendung.
C++ - Listing 7: Methoden eines Task-Blocks
define_task_block([&](auto& tb){
tb.run([&]{ process(x1, x2) });
if (x2 == x3) tb.wait();
process(x3, x4);
});
- Child stealing: Der Scheduler klaut die Aufgabe und führt sie aus.
- Parent stealing: Der Erzeuger-Thread führt die Aufgabe selbst aus. Der Scheduler schnappt sich in diesem Fall aber den Parent.
