(Basis) Performanten C++ Code schreiben?

__jb__

Hallo zusammen,

kennt jemand von Euch zufällig ein gute Zusammenfassung, worauf zu achten ist, das der Code performant ist? Ich habe über Google bereits eine gute Auflistung, wie ich finde, gefunden: http://www.tantalon.com/pete/cppopt/main.htm
Allerdings wurde das damals mit dem Microsoft Visual C++ 6.0 Compiler gemessen. Soweit ich weiß ist das bereits eine Ecke her. Ist diese Auflistung bei den aktuellen Rechnerarchitekturen und Compilern noch aktuell?

Ich Ziele auf so Basis Performance-Tipps ab, wie:
- Wie übergebe ich die Parameter richtig?
- Wann nutze ich welchen Container?
- Wie verwende ich die C++ Konstrukte richtig?
- ...

Je nach Fragestellung findet man hier im Forum auch tolle Antworten darauf, aber gibt es dafür bereits eine Zusammenfassung (für einen aktuelleren Compiler - idealerweise für MS VS2013)?

Und hier noch ein Beispiel. Mir war das nicht so geläufig, und dies möchte ich mit Euch teilen
Wer kennt folgendes Code-Beispiel nicht?!?

for(std::list<int>::iterator itr=list.begin(); itr != list.end(); itr++) {
 // tbd
}

Erste Verbesserung von Post- auf Pre-Increment:

for(std::list<int>::iterator itr=list.begin(); itr != list.end(); ++itr) {
 // tbd
}

Ich habe dann durch Zufall mal folgenden Code gesehen. Und somit die 2. Laufzeit-Verbesserung:

for(std::list<int>::iterator itr=list.begin(), end = list.end(); itr != end; ++itr) {
 // tbd
}

Daraufhin mal eine kleine Performance-Messung durchgeführt. (20-Mal eine Liste mit 1.000.000 Elementen durch iteriert. Angaben in Millisekunden.)

DEBUG   RELEASE
Variante 1:   319.3     5.6    (post-increment)
Variante 2:   134.5     5.2    (pre-increment)
Variante 3:    46.5     4.9    (condition)

Klar im Release unterscheidet sich das wieder kaum, allerdings entwickle ich in Debug und nicht in Release und somit doch ein kleiner aber feiner Unterschied.
Code ist unter folgendem Link zu finden (Qt wurde für die Messung verwendet): http://ideone.com/4w4R32

Vielen Dank Euch.

Viele Grüße,

Jakob

JulianH

Vieles von dem, was du in der Liste aufgeführt hast, hat m.M.n. mit Erfahrung zu tun, weil eben auch die Anforderungen beachtet werden müssen.
Bei Standard-Containern ist die Implementierung im Standard nicht eindeutig definiert. Wenn man nur wenige Elemente in einem Container vorsieht, sollte man std::vecotr/std::string/std::array (std::vecotr verhält sich für die meisten Algorithmen für die ersten paar 100 Elemente nahezu linear) verwenden, ansonsten Messungen durchführen.

Die von dir gezeigen Optimierungen mit der Liste sind auch so Sachen wo ich eigentlich gehofft hätte, dass der Opzimizer das selbst hinkriegt. Wenn ich nacher etwas Zeit habe teste ich das vielleicht nochmal genauer.

Wenn ich jetzt keinen Fehler gemacht habe, dann ist alles so wie ich es mir schon gedacht habe: Alle 4 Varianten erzeugen den exakt gleichen Maschinencode. Getestet mit gcc 5.3, clang 3.7 und Visual Studio 2015.

__jb__

Hi sebi707,

vielen Dank fürs anschauen des Maschinencodes.
Ich hatte die Messung mit Visual Studio 2013 gemacht.

Den exakt gleichen Maschinencode in der "Release" Konfiguration, oder?

Viele Grüße,

Torsten Robitzki

Hallo Jakob,
mein Tipp: schreib die Software so, dass sie korrekt ist und das Design Änderungen erlaubt. Dann guckst Du, ob die Performance reicht. Wenn Sie nicht reicht, dann misst Du mit einem Profiler, optimierst die Hotspots und bist fertig.

Du erkennst ja schon ganz gut an Deinen Zahlen, dass Deine Optimierungen "fast" keinen Unterschied machen. Wenn Du mal in die Situation kommst, dass die Performance wirklich zu schlecht ist, dann brauchst Du in der Regel Faktoren an Verbesserungen und die bekommst Du in der Regel nicht mit diesen Mikro-Optimierungen hin, sondern eher mit anderen Algorithmen / Designs.

Ansonsten bietet sich natürlich an, die entsprechende Literatur (Effective Modern C++; Exceptional C++, etc.) mal gelesen zu haben, um einen Überblick über die Kosten einzelnder Sprachkonstrukte zu bekommen.

Und es gilt nach wie vor die drei Regeln der Optimierung
- Don't do it
- Don't do it yet
- Profile before you optimize

mfg Torsten

jb schrieb:

Den exakt gleichen Maschinencode in der "Release" Konfiguration, oder?

Ja jeweils die Release Konfiguration. Ich habe den Test gerade nochmal mit Visual Studio 2013 wiederholt und erhalte wieder für alle 4 Fälle den gleichen Code.

Columbo

Da der Inkrement sowieso geinlined wird, und der zugrundeliegende Zeiger eben skalar ist, wird der Optimizer sicherlich das post- als ein pre-increment behandeln. Das der Iterator, den end() zurückgibt, sich nicht ändert und daher extrahiert werden kann, dürfte der Optimizer ebenso feststellen (siehe Loop-invariant code motion).

Wenn man ihn anwirft, versteht sich. Ansonsten ist Optimierung für die Katz.

Edit: Wobei die oben erwähnte "scalar promotion" eben auch nur für Skalare funktioniert - der Grund, warum range-based for, welches einen zweiten Iterator für end definiert, als potenziell performanter angepriesen wurde.

__jb__

Hallo zusammen,

vielen Dank für Eure Meinungen, Buchempfehlungen und Ergänzungen.

Entnehme ich Euren Antworten richtig, dass für eine Performance-Messung nur die Release-Konfiguration (+ Optimierer) relevant ist/sein sollte?
Klar diese Konfiguration wird am Ende "ausgeliefert".

Allerdings sollte man doch als Entwickler auch für Debug (damit arbeite ich zumindest, wenn ich ein Programmentwurf durchführe) die Kosten der Konstrukte kennen - auch wenn der Optimierer das alles auflöst - oder nicht? Ich finde es halt krass, dass die 3. Variante des for-loop's um einiges schneller ist. Oder ist das nach eurer Meinung und Erfahrungen zu "niti-kriti" gedacht?

Und jetzt noch ein paar Off-Topic Fragen:

sebi707 schrieb:

Ich habe den Test gerade nochmal mit Visual Studio 2013 wiederholt und erhalte wieder für alle 4 Fälle den gleichen Code.

Danke Dir. Aber sag mal, welchen Compiler hast Du nicht installiert? Gibt es einen Grund, dass Du so viele installiert hast?

Arcoth schrieb:

(siehe Loop-invariant code motion).

Wie erlangt man den das Wissen wie ein spezielles Konstrukt heißt? Muss man dafür den C++ Standard lesen? Ich stolper hier im Forum immer wieder über solche Begriffe, kenne zwar die Code-Zeilen und verstehe meistens auch was passiert, aber die korrekte Nennung fehlt mir.

Vielen Dank Euch.

Viele Grüße,

Jakob

kurze_frage

Arcoth schrieb:

Da der Inkrement sowieso geinlined wird, und der zugrundeliegende Zeiger eben skalar ist, wird der Optimizer sicherlich das post- als ein pre-increment behandeln. Das der Iterator, den end() zurückgibt, sich nicht ändert und daher extrahiert werden kann, dürfte der Optimizer ebenso feststellen (siehe Loop-invariant code motion).

ersteres vielleicht, auch wenn es schwer ist eine allgemeine Garantie darauf zu geben, zumindest ich würde mich das nicht trauen.

aber überschätzt du nicht den optimizer im return Fall von end()?

Torsten Robitzki

jb schrieb:

Allerdings sollte man doch als Entwickler auch für Debug (damit arbeite ich zumindest, wenn ich ein Programmentwurf durchführe) die Kosten der Konstrukte kennen - auch wenn der Optimierer das alles auflöst - oder nicht? Ich finde es halt krass, dass die 3. Variante des for-loop's um einiges schneller ist. Oder ist das nach eurer Meinung und Erfahrungen zu "niti-kriti" gedacht?

So lange es die Arbeit nicht stört, ist es doch völlig egal, welche Performance ein debug release hat. Und wenn die Performance gut genug ist, dann liefere ich auch liebend gerne ein debug release aus (oder lass zumindest die asserts drinnen).

Die drei Variante Deiner untersuchten Schleife unterscheiden sich bummelig um 10% und in 90% aller Fälle steht diese Schleife eh in einem Stück Software, das für die Performance total unbedeutend ist. Also: ja, zu "niti-kriti" gedacht

Hier noch ein Link zur Keynote der diesjährigen Meeting C++ Understanding Compiler Optimization - Chandler Carruth. Da beton Carruth noch mal, dass Deine dritte Optimierung von jedem vernünftigen Compiler durchgeführt werden "sollte".

Mechanics

jb schrieb:

Entnehme ich Euren Antworten richtig, dass für eine Performance-Messung nur die Release-Konfiguration (+ Optimierer) relevant ist/sein sollte?

Debug Performance ist an sich ist überhaupt nicht interessant. Alle Optimierungen und Messungen werden im Release durchgeführt. Man sollte das aber schon irgendwie einschätzen können. Wenn dein Programm im Debug kaum bedienbar ist, ist normalerweise nicht davon auszugehen, dass das im Release Modus plötzlich um Größenordnungen schneller wird.
Einerseits sollte man "Premature optimiziation is the root of all evil" und alle ähnlichen Aussagen stets im Hinterkopf behalten. Andererseits spricht auch nichts dagegen, einfach die schnellere Variante hinzuschreben, wenn das sonst keine Nachteile mit sich bringt.
Sonst summiert sich das alles irgendwann auf. Jeder schreibt irgendwelchen Code und meint, er wäre nicht performancekritisch. Jahre später wird vielleicht eine High Level Funktion hinzugefügt, die den ganzen anderen Code aufruft und wo es schon interessant ist, wie schnell die durchläuft. Und dann ist man plötzlich mit sehr viel Code konfrontiert, der einfach nicht optimal ist und immer wieder ein bisschen was verschwendet, wo das absolut nicht nötig wäre.

jb schrieb:

Danke Dir. Aber sag mal, welchen Compiler hast Du nicht installiert? Gibt es einen Grund, dass Du so viele installiert hast?

Die vielen Visual Studio Versionen habe ich mir mit der Zeit installiert (die alten müsste ich eigentlich mal deinstallieren). Dann habe ich noch Zugriff auf diverse Linux PCs und VMs wo verschiedene Versionen von gcc, icc und clang drauf sind. Gerade für solche Performance Fragen aber auch andere Sachen kann man so gut mal auf verschiedenen Compilern testen.

Mechanics schrieb:

Wenn dein Programm im Debug kaum bedienbar ist, ist normalerweise nicht davon auszugehen, dass das im Release Modus plötzlich um Größenordnungen schneller wird.

Ich hab das aber auch schon anders erlebt. Vor allem die Debug Iteratoren von Visual Studio sind einfach mal unglaublich langsam. Ich hatte schon ein Projekt da war die Debug Version von Visual Studio auf einer aktuellen Intel CPU so schnell wie die Release Version auf einem 168 MHz ARM Mikrocontroller.

Columbo

kurze_frage schrieb:

ersteres vielleicht, auch wenn es schwer ist eine allgemeine Garantie darauf zu geben, zumindest ich würde mich das nicht trauen.

Was post- und pre-increment für Skalare unterscheidet, nämlich der "verzögerte" side-effect, ist hier völlig gleich, denn zwischen dem Beginn der Auswertung und dem side-effect passiert rein gar nichts. Sogar wenn wir von vector<> oder list<>::iterator reden, wird der Optimizer den verworfenen Rückgabewert auf den im Rumpf definierten Iterator zurückverfolgen und diesen einfach streichen (vorausgesetzt, der Nutzer kann keine Unterschiede bzgl. Seiteneffekten beobachten, was relativ leicht zu beweisen ist, indem wir die zugehörigen Funktionen analysieren). Sprich,

iterator operator++(int) {
    auto i = *this; // (3) Ungenutztes automatisches Objekt wird gestrichen
    ++*this;
    return i; // (2) Ungenutzte Temporary wird gestrichen
}

// […]

++myIter; // (1) discarded-value expression, Rückgabewert ungenutzt

aber überschätzt du nicht den optimizer im return Fall von end()?

end() besteht aus einem return -Statement und kann als geinlined betrachtet werden.

Falls ein internes iterator -Objekt zurückgegeben wird, haben wir performance-mäßig schon ein Optimum, da durch das vec._End ja effektiv keine Indirektion erfolgt (da vec und vec._End automatische Objekte sind).

Falls ein Iterator-Objekt durch einen Zeiger konstruiert wird, kann der Optimizer durch das bereits erwähnte loop-invariant code motion feststellen, dass dieses Objekt stets den gleichen Wert hat und keine side-effects durch dessen Konstruktion erzeugt werden. Wir arbeiten schlussendlich doch nur mit Skalaren, der Optimizer hat hier also keinen grundlegendes Problem.

__jb__

Hallo zusammen,

vielen Dank für Eure Antworten

Und noch ein paar Verständnisfragen:

Mechanics schrieb:

Alle Optimierungen und Messungen werden im Release durchgeführt.

[1] Wie messt ihr den dann die Performance? Kapselt ihr dann immer diese Funktionen in kleine Testprogramme? Wenn ja, dann kann es aber doch sein, dass der Optimierer u.U. was nicht optimiert was er im ursprünglichen Code machen würde - oder?

[2] Mir ist das Tool VerySleepy bekannt, um "Hot-Spots" zu finden, allerdings geht das doch nur, wenn ich Debug-Informationen zur Verfügung habe - und somit bin ich doch gezwungen die Messungen in Debug zu machen - oder?

Noch eine Erfahrung vom MS Visual Studio 2013 Optimierer: Ich hatte mal den Fall dass der Optimierer eine Methode so "optimiert" hat, dass das Verhalten sich zwischen Debug und Release sich unterschieden haben. Und das habe ich überhaupt nicht erwartet. Die Lösung damals war, die Optimierung für diesen Codeanteil zu deaktivieren.

Mechanics schrieb:

Einerseits sollte man "Premature optimiziation is the root of all evil" und alle ähnlichen Aussagen stets im Hinterkopf behalten.

Okay danke Dir. Mir ging es ja auch nicht darum gleich "unleserlichen"-"hoch-performanten-code" am Besten noch mit Assembler Abschnitten zu schreiben. Es war auf der Ebene gedacht, wenn ich weiß das mein Vektor 24 Elemente hat, das ich diesen gleich auf diese Größe abändere.

[3] Dazu noch eine Frage: Wird sowas vom Optimierer erkannt und auch optimiert (da es sich um eine STL Klasse handelt)? (Ist die STL ein Bestandteil des C++ Standards oder ist die STL einfach eine Basis Bibliothek die immer zum jeweiligen Standard von den Herstellern zur Verfügung gestellt wird?)

std::vector< int > vec;
for(int i=0; i < 24; ++i) {
  vec.push_back( i );
}

Wird daraus ein?

// ...
vec.resize(24); 
for(...){
}
// ...

Torsten Robitzki schrieb:

Hier noch ein Link zur Keynote der diesjährigen Meeting C++ Understanding Compiler Optimization - Chandler Carruth. Da beton Carruth noch mal, dass Deine dritte Optimierung von jedem vernünftigen Compiler durchgeführt werden "sollte".

Danke für den Keynote werde ich mir noch bei Gelegenheit anschauen. Der Entwickler sollte ja trotzdem noch mitdenken, wenn ich das "sollte" so lese ^^

Vielen Dank.

Viele Grüße,

Jakob

Torsten Robitzki

Hallo Jakob,

jb schrieb:

[1] Wie messt ihr den dann die Performance? Kapselt ihr dann immer diese Funktionen in kleine Testprogramme? Wenn ja, dann kann es aber doch sein, dass der Optimierer u.U. was nicht optimiert was er im ursprünglichen Code machen würde - oder?

Naja, Du fängst in der Regel nicht an zu messen, wenn Du nicht _vorher_ festgestellt hast, dass Du in einer bestimmten Situation ein Problem hast. Und genau diese Situation versuchst Du zu erfassen. Du möchtest dann auch diese gesamte Situation (einen bestimmten Usecase) verbessern und nicht einzelne Funktionen, sinnfrei optimieren. Wenn Du einen Server hast, den Du kontinuierlich unter realistische Last setzen kannst, dann kannst Du den direkt vermessen. Wenn es eine Funktion ist, die Du aus einer GUI heraus aufrufst, kann es sinnvoll sein, diese Funktion zum Messen in ein Schleife zu packen und mehrfach aufzurufen.

Um dem Problem auf die Spur zu kommen, hilft es meisten schon mal, wenn man erkennt, ob der Flaschenhals die CPU, oder evtl. IO ist. Je nach dem sieht die Lösung meist auch komplett unterschiedlich aus.

Ich finde statistische Profiler ganz gut, weil Sie recht bequem ohne Instrumentalisierung auskommen und das Verhalten eines Programs nur minimal beeinflussen (z.B. Google Perftools).

Es ist aber auf jeden Fall ratsam, sich vorher mit den Werkzeugen vertraut zu machen, da Performance-Probleme häufig zu ungünstigen Zeiten im Projektverlauf auftreten :-(.

mfg Torsten

jb schrieb:

[2] Mir ist das Tool VerySleepy bekannt, um "Hot-Spots" zu finden, allerdings geht das doch nur, wenn ich Debug-Informationen zur Verfügung habe - und somit bin ich doch gezwungen die Messungen in Debug zu machen - oder

Ich habe schon mit Intel Parallel Studio (gibts als Student kostenlos) gearbeitet. Das funktioniert auch mit der Release Version. Man hat ja schon Debug-Infos zur verfügung nur sind einige Variablen oder ganze Funktionen eventuell wegoptimiert oder geinlined, sodass man sie nicht wieder findet.

jb schrieb:

Noch eine Erfahrung vom MS Visual Studio 2013 Optimierer: Ich hatte mal den Fall dass der Optimierer eine Methode so "optimiert" hat, dass das Verhalten sich zwischen Debug und Release sich unterschieden haben. Und das habe ich überhaupt nicht erwartet. Die Lösung damals war, die Optimierung für diesen Codeanteil zu deaktivieren.

Das ist mit großer Sicherheit ein Fehler in deinem Programm. Könnte auch ein Fehler im Compiler sein, ist allerdings unwahrscheinlich. Der Optimizer darf keinen gültigen Code kaputt machen!

jb schrieb:

[3] Dazu noch eine Frage: Wird sowas vom Optimierer erkannt und auch optimiert (da es sich um eine STL Klasse handelt)? (Ist die STL ein Bestandteil des C++ Standards oder ist die STL einfach eine Basis Bibliothek die immer zum jeweiligen Standard von den Herstellern zur Verfügung gestellt wird?)
std::vector< int > vec;
for(int i=0; i < 24; ++i) {
  vec.push_back( i );
}
Wird daraus ein?
// ...
vec.resize(24); 
for(...){
}
// ...

Die STL ist Teil des Standards und wird dort beschrieben wie es zu funktionieren hat. Spezielle Compiler-Optimierungen die nach bestimmten STL Konstruktionen suchen sind mir nicht bekannt (kann gut sein, dass es trotzdem welche gibt). Ich denke solche Optimierungen sind auch eher kontraproduktiv. Nicht jeder Entwickler nutzt die STL und es wäre viel sinnvoller allgemeine Fälle zu optimieren. Sowas wie im gezeigen Beispiel dürfte allerdings schwierig werden zu optimieren.

Tobiking2

sebi707 schrieb:

jb schrieb:

Noch eine Erfahrung vom MS Visual Studio 2013 Optimierer: Ich hatte mal den Fall dass der Optimierer eine Methode so "optimiert" hat, dass das Verhalten sich zwischen Debug und Release sich unterschieden haben. Und das habe ich überhaupt nicht erwartet. Die Lösung damals war, die Optimierung für diesen Codeanteil zu deaktivieren.

Das ist mit großer Sicherheit ein Fehler in deinem Programm. Könnte auch ein Fehler im Compiler sein, ist allerdings unwahrscheinlich. Der Optimizer darf keinen gültigen Code kaputt machen!

Wenn Nebenläufigkeit im Spiel ist passiert das schon. Da reicht es aber die entsprechende Variablen mit volatile zu kennzeichnen um die Optimerung in deren Kontext zu deaktivieren.

Tobiking2 schrieb:

Wenn Nebenläufigkeit im Spiel ist passiert das schon. Da reicht es aber die entsprechende Variablen mit volatile zu kennzeichnen um die Optimerung in deren Kontext zu deaktivieren.

Für Multithreading ist volatile überhaupt das falsche Werkzeug. Dafür benutzt man Locks oder Atomics. Und Optimierungen deaktivieren kann auch keine Lösung sein.

Torsten Robitzki

Tobiking2 schrieb:

Wenn Nebenläufigkeit im Spiel ist passiert das schon. Da reicht es aber die entsprechende Variablen mit volatile zu kennzeichnen um die Optimerung in deren Kontext zu deaktivieren.

Bitte erst informieren, bevor Du so einen Blöd... einem offensichtlichem Anfänger an die Hand gibst. `volatile` hat exakt GARNIX mit multithreading zu tun.

Wenn nach Optimierung, ein nebenläufiges Programm nicht mehr funktioniert, dann ist das sehr wahrscheinlich "undefined behaviour" im Spiel und dann sollte man den Fehler finden und beheben und nicht irgend welche möglichen Optimierungen kaput machen, bis es wieder funktioniert.