Bereits Kunde? Jetzt einloggen.
Lesezeit ca. 5 Min.

C++ Core Guidelines – Folge 55: Performance by Design


Linux Magazin - epaper ⋅ Ausgabe 12/2020 vom 05.11.2020

Im aktuellen Artikel zu den C++ Core Guidelines stehen einmal mehr Regeln zur Performance im Fokus. Wer sie befolgt, den belohnt ein Software-Entwurf, der qua Design performant ist.


Artikelbild für den Artikel "C++ Core Guidelines – Folge 55: Performance by Design" aus der Ausgabe 12/2020 von Linux Magazin. Dieses epaper sofort kaufen oder online lesen mit der Zeitschriften-Flatrate United Kiosk NEWS.

Bildquelle: Linux Magazin, Ausgabe 12/2020

Beim Lesen der Kapitelüberschrift „Design to enable optimization“ in den C++ Core Guidelines dachte der Autor dieser Zeilen sofort an die Move-Semantik. Warum? Programmierer sollten, wo immer möglich, Algorithmen mit Move- und nicht mit Copy-Semantik implementieren. Die Vorteile liegen auf der Hand:
• Statt einer teuren Copy- genügt eine ressourcensparende Move-Operation.
• Der Algorithmus ist deutlich stabiler, da er keinen ...

Weiterlesen
epaper-Einzelheft 6,99€
NEWS 14 Tage gratis testen
Bereits gekauft?Anmelden & Lesen
Leseprobe: Abdruck mit freundlicher Genehmigung von Linux Magazin. Alle Rechte vorbehalten.

Mehr aus dieser Ausgabe

Titelbild der Ausgabe 12/2020 von News. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
News
Titelbild der Ausgabe 12/2020 von Zahlen & Trends. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Zahlen & Trends
Titelbild der Ausgabe 12/2020 von Kernel 5.9: RISC-V wird Tickless, Lizenzänderung, FSGSBASE-Support: Herbstliches Allerlei. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Kernel 5.9: RISC-V wird Tickless, Lizenzänderung, FSGSBASE-Support: Herbstliches Allerlei
Titelbild der Ausgabe 12/2020 von VMware verlagert seine Hausmesse ins Web: VMworld 2020. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
VMware verlagert seine Hausmesse ins Web: VMworld 2020
Titelbild der Ausgabe 12/2020 von Wie Event Stream Processing funktioniert: Alles fließt. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Wie Event Stream Processing funktioniert: Alles fließt
Titelbild der Ausgabe 12/2020 von Stream Processing leicht gemacht mit Apache StreamPipes: Fließend zum Fly-by. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Stream Processing leicht gemacht mit Apache StreamPipes: Fließend zum Fly-by
Vorheriger Artikel
Shell-Kommandos statistisch auswerten: Geschichte schreiben
aus dieser Ausgabe
Nächster Artikel iT-PROFI MARKT
aus dieser Ausgabe

... 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