... Speicher braucht und der Code somit keine std::bad_alloc-Ausnahme wirft.• Der Algorithmus deckt Datentypen wie std::unique_ptr ab, die sich nicht kopieren, sondern lediglich verschieben lassen.
Der in Listing 1 gezeigte swap()-Algorithmus veranschaulicht das; er basiert auf der Move-Semantik.
Das sieht einfach aus, ist es aber leider nicht: Das Listing verwendet den Datentyp BigArray, der hier ein ernsthaftes
Problem aufwirft. Er unterstützt nur Copy-, aber keine Move-Semantik. Zum Beispiel stellt sich die Frage, was passiert, wenn Zeile 7 zwei BigArray-Variablen tauscht, während der swap()-Algorithmus unter der Haube Move-Semantik verwendet 1.
Überraschung! Tatsächlich passiert nichts, es funktioniert einfach. Die traditionelle Copy-Semantik springt für die Move-Semantik ein und dient als eine Art Fallback. Oder, um es anders zu formulieren: Verschieben ist ein optimiertes Kopieren. Doch warum?
Der swap()-Algorithmus fordert Move-Semantik an, da std::move einen Rvalue zurückgibt. Eine konstante Lvalue-Referenz kann einen Rvalue binden. Zugleich besitzen der Copy-Konstruktor und der Copy-Zuweisungsoperator eine konstante Lvalue-Referenz als Argument. Besäße BigArray einen Move-Konstruktor und einen Move-Zuweisungsoperator, die jeweils eine Rvalue-Referenz erwarten würden, hätten beide eine höhere Priorität als ihre Copy-Gegenstücke.
Verwenden Algorithmen Move-Semantik, kommt diese automatisch zum Einsatz, sofern die Datentypen sie unterstützen. Tun sie das nicht, springt die Copy-Semantik ein. Im Worst Case besitzt das Programm dieselben Performance-Charakteristiken wie ein vor C++11 entstandenes Programm.
Rechne zur Compile-Zeit
Einen ähnlichen allgemeinen Fokus wie die vorgestellte Performance-Regel „Design to enable optimization“ besitzt die Aufforderung: „Move computation from run time to compile time“ . Ein Beispiel für die damit verbundene Regel zeigt Listing 2. Der altbekannte gcd()-Algorithmus ermittelt dort zur Laufzeit des Programms den größten gemeinsamen Teiler zweier Zahlen. gcd() verwendet für seine Berechnung den euklidischen Algorithmus .
Wenn Sie gcd() als konstanten Ausdruck deklarieren, können Sie ihn so zur Funktion erklären, die C++ auch zur Übersetzungszeit ausführt. Es gibt in C++14, im Gegensatz zu C++11, nur noch wenige Einschränkungen für constexpr-Funktionen. So darf gcd() keine statischen oder Thread-lokalen Variablen verwenden. Ebenfalls nicht zulässig sind Ausnahmebehandlungen und goto-Anweisungen. Sie müssen Variablen direkt initialisieren, und diese müssen einen literalen Typ besitzen. Listing 3 demonstriert eine Implementierung und Anwendung der constexpr-Variante des gcd()-Algorithmus.
1 Die Move-Semantik wird hier auf einen kopierbaren Datentyp angewandt.
2 Der gcd()-Algorithmus lässt sich so umsetzen, dass C++ ihn zur Übersetzungszeit ausführt.
3 Der Compiler Explorer zeigt die Assembler-Anweisungen zur Zeile 16 von Listing 3.
Wenn Sie den gcd()-Algorithmus zur constexpr-Funktion erklären, bedeutet das jedoch nicht, dass C++ ihn automatisch zur Übersetzungszeit ausführt. Vielmehr erhält die Funktion gcd() so lediglich das Potenzial dafür. C++ führt eine constexpr-Funktion nur dann zwingend zur Übersetzungszeit aus, wenn sie in einem konstanten Ausdruck auftritt.
4 Die Struktur einer std::forward_list, die nur in eine Richtung wachsen kann.
In Zeile 16 steht ein konstanter Ausdruck, der das Ergebnis mit der constexpr-Variablen res aufpickt, in Zeile 20 hingegen nicht: res2 ist kein konstanter Ausdruck. Hätten Sie also res2 als constexpr auto res2 deklariert, würde der Compiler das postwendend mit einer Fehlermeldung quittieren. Der Grund: val in Zeile 20 ist kein konstanter Ausdruck. In Abbildung 2 sieht man das Programm in Aktion.
Lässt sich beweisen, dass C++ die Zeile 16 zur Übersetzungszeit ausführt? Klar: Abbildung 3 zeigt die der Zeile entsprechenden Assembler-Anweisungen, die GCC 7.3 mit maximaler Optimierung erzeugt. Die Ausgabe hat der Compiler Explorer von Matt Godbolt festgehalten. Der Funktionsaufruf gcd(121, 11) reduziert sich direkt auf das Ergebnis 11.
Kosten sparen
Entwickler setzen gern Templates ein, um Entscheidungen zur Übersetzungszeit zu treffen. Auch dazu stellen die C++ Core Guidelines ein schönes Beispiel vor. Eine beliebte Technik besteht etwa darin, einen Handle für das Speichern von Daten auf dem Stack anzulegen, wenn die Daten klein genug ausfallen. Ist dies nicht der Fall, verwaltet C++ sie auf dem Heap.
Diese Idee setzt zum Beispiel die SSO (Small String Optimization) um. Das heißt, dass der Code einen std::string nur dann auf dem Heap anlegt, wenn er eine gewisse Größe übersteigt. Der entscheidende Grund für diese Optimierung besteht darin, dass das Allozieren von Speicher eine relativ teure Angelegenheit ist. Listing 4 skizziert die Idee.
Wie funktioniert das Ganze nun? std::conditional in Zeile 14 ist ein ternärer Operator aus der Type-Traits-Bibliothek . Im Gegensatz zum ternären Operator (a ? b: c) führt das Programm ihn zur Übersetzungszeit aus. Evaluiert Zeile 14 std::condition<sizeof(T)… zu true, kommt die erste Alternative zum Zug, sonst die zweite
Zugriffsfrage
Die letzte vorgestellte Regel zur Performance beschäftigt sich mit der Vorhersagbarkeit von Speicherzugriffen, der Access Memory Predictability .
Liest das Programm eine Variable vom Datentyp int, umfasst das tatsächlich deutlich mehr als 4 Bytes: Es liest eine ganze Cacheline und speichert sie im Cache. Auf modernen Architekturen umfasst eine solche Cacheline meist 64 Bytes. Fordert die CPU nun nochmals eine Variable aus dem RAM an und befindet sich diese bereits im Cache, verwendet die Leseoperation direkt den Cache und wird damit deutlich schneller.
5 Ein std::deque ist eine doppelt verkettete Liste und ein Mittelding zwischen std::list und std::forward_list.
6 Ausführungszeit für die Summation unter Linux.
7 Ausführungszeit für die Summation unter Windows.
Ein Container wie std::vector legt seine Daten in einem kontinuierlichen Speicherbereich ab und nutzt als Datenstruktur Cachelines optimal aus. Er besitzt eine definierte Größe und Kapazität und wächst nur in eine Richtung. Seine Kapazität entspricht mindestens seiner Größe, und er zeigt zudem an, wann er Speicher neu allozieren muss. Das greift auch für std::string und std::array, wobei std::array keine Kapazität besitzt.
Die Argumente für std::vector gelten nicht für die weiteren Sequenzcontainer std::list oder std::forward_ list. Beide bestehen aus doppelt oder einfach verknüpften Knoten 4. Die std::forward_ list wächst aber anders als eine std::list nur in eine Richtung.
Ein std:: deque bewegt sich zwischen den beiden Extremen, denn es handelt sich dabei um eine Art doppelt verkettete Liste von Speicherbereichen 5.
8 Die Ausführungszeit für die einzelnen Summationen im grafischen Überblick.
In der Praxis
Soweit die Theorie zu den Cachelines. Listing 5 wirft implizit die Frage auf, ob es einen Performance-Unterschied bringt, alle Elemente eines std::vector, eines std::deque, einer std::list oder einer std::forward_list zu lesen und mithilfe des Algorithmus std::accumulate aufzusummieren. Das Programm liefert gleich die Antwort dazu.
Es erzeugt zuerst 100 Millionen Zufallszahlen zwischen 0 und 100 (Zeile 35). Dann summiert es die Zahlen mit einem std::vector (Zeile 46), einem std:: deque (Zeile 52), einer std::list (Zeile 57) sowie einer std::forward_list (Zeile 62). Die eigentliche Arbeit findet in der Funktion sumUp() in Zeile 15 statt.
Listing 6 stellt eine typische Implementierung des std::accumulate-Algorithmus vor. Alle vier Container verwenden dieselbe Implementierung, ihr Laufzeitverhalten unterscheidet sich aber deutlich. Abbildung 6 und 7 stellen die Ausführungszeiten der Programme unter Linux und Windows dar. Beide Programme wurden mit maximaler Optimierung übersetzt. Insgesam führt das zu drei einfachen Beobachtungen:
• std::vector läuft unter Linux 10-mal schneller als std::list oder std::forward_ list, unter Windows sogar 30- mal schneller.
• std::vector läuft unter Linux 1,5-mal schneller und unter Windows 5-mal schneller als std::deque. Der Grund liegt vermutlich darin, dass die zusammenhängenden Speicherbereiche unter Linux größer sind als unter Windows. Damit ähnelt die Zugriffszeit unter Linux der eines std::vector.
• std::deque ist unter Linux und Windows gleichermaßen 6-mal schneller als std::list oder std::forward_list. Die Grafik mit den Ausführungszeiten in Abbildung 8 unterfüttert die Beobachtung direkt mit Daten.
Die Messungen legen nahe, dass die Zugriffszeit auf die Elemente der Container der dominante Faktor für die Gesamt-Performance ist. Wer eine Datenstruktur besser für Cachelines optimiert, erhält kürzere Zugriffszeiten. Also: std::vector ist schneller als std::deque, das wiederum ist schneller als std::list und std::forward_list. (kki/jlu)
Weitere Infos und interessante Links
www.lm-online.de/qr/45507
Dateien zum Artikel herunterladen unter
www.lm-online.de/dl/45507
© Michal Bednare123RF
