C++11: ranged loop - optimization

[Klaus82]

Hallo,

ich sehe mir gerade ein paar Vorträge der Going Native 2013 an und hänge bei einem speziellen Vortrag bei 0:41:

Da schreibt er eine for Schleife in den neuen C++11 Standard Syntax um. Kann mir jemand genauer sagen, warum der neue Syntax schneller ist?

Der Vortragende erklärt es im Video, aber ich komme nicht mit.

Gruß,
-- Klaus.

[Sone]

Die Version

for( auto iter = v.begin(); iter != v.end(); ++ iter)

ruft in jedem Schleifendurchlauf end() auf. Wohingegen der Standard range-based for etwa so definiert:

auto && __range = range-init;

for ( auto __begin = begin-expr,
           __end = end-expr;
      __begin != __end;
      ++__begin )
{
	for-range-declaration = *__begin;
	statement
}

Hier wird also end-expr vor der Schleife nur einmal ausgewertet.

Eine weitere Begründung von ihm ist das einige Schleifenoptimierungen bei range-based for vorgenommen werden können, die der Compiler bei der obigen Variante nicht vornehmen kann, weil er nicht genügend Informationen hat.

[knivil]

Ob es schneller ist sei dahingestellt, den wenn ein Tool es aus der Schleife holen kann, dann kann es der Kompiler auch.

[dot]

knivil schrieb:

Ob es schneller ist sei dahingestellt, den wenn ein Tool es aus der Schleife holen kann, dann kann es der Kompiler auch.

Spätestens, wenn der Compiler den Aufruf von .end() nichtmehr inlinen kann, wird ihm auch das kaum noch gelingen, denn um diese Transformation durchzuführen, muss er ja beweisen, dass .end() in jedem Durchlauf den selben Wert liefert; obige Definition einer range-based for loop dagegen, ist in jedem Fall optimal...

[TNA]

knivil schrieb:

Ob es schneller ist sei dahingestellt, den wenn ein Tool es aus der Schleife holen kann, dann kann es der Kompiler auch.

Das Tool arbeitet heuristisch, ohne nachzuweisen, dass der Code in allen fällen wirklich exakt äquivalent ist. Das ist quasi "nur" ein sehr intelligentes "Suchen und ersetzen". Dort wurde auch gesagt. das sehr gute Compiler in einigen Fällen die selben Optimierungen machen können aber nicht in allen. Natürlich gibt es alleine wegen der besseren Übersichtlichkeit genug Grund die neue Syntax zu verwenden.

[lto]

dot schrieb:

knivil schrieb:

Ob es schneller ist sei dahingestellt, den wenn ein Tool es aus der Schleife holen kann, dann kann es der Kompiler auch.

Spätestens, wenn der Compiler den Aufruf von .end() nichtmehr inlinen kann, wird ihm auch das kaum noch gelingen, denn um diese Transformation durchzuführen, muss er ja beweisen, dass .end() in jedem Durchlauf den selben Wert liefert; obige Definition einer range-based for loop dagegen, ist in jedem Fall optimal...

Jeder vernünftige Compiler bekommt das hin.

[Ethon]

Außer end() befindet sich in einer dynamisch gelinkten Bibliothek.

[Sone]

Ethon schrieb:

Außer end() befindet sich in einer dynamisch gelinkten Bibliothek.

Was hier aber unmöglich ist, weil alle Container Templates sind.

Es können sich aber einige von end() aufgerufene Funktionen in einer DLL befinden, das wäre dann der Fall. Das ist aber recht selten - das finde ich bspw. beim GCC nicht. Und daher gilt das Argument nicht.

[kurze_frage]

lto schrieb:

Jeder vernünftige Compiler bekommt das hin.

und du meinst Chandler Carruth erzählt aus irgendwelchen Markeding Gründen oder weil er es nicht besser weiss irdenwas?

ich mein der Typ is auf compiler optimizer spezialisier, der sollte es doch eigentlich wissen

[Nexus]

Siehe auch: Is the range based for loop beneficial to performance?

[Sone]

Eigentlich sollte aber end(), gerade wenn es nur ein Getter auf eine interne Membervariable ist, geinlined werden.

Und ob man dann auf den internen, privat gespeicherten end-Iterator in vector zugreift, oder auf seinen eigenen lokalen, ist letztendlich egal.

Edit: Für den GCC, Nun gut, da ist es nicht sofort ein Iterator, aber er erzeugt einen Iterator durch einen Zeiger.

iterator
      end() _GLIBCXX_NOEXCEPT
      { return iterator(this->_M_impl._M_finish); }

Wobei _M_finish ein Zeiger ist..

Kann wahrscheinlich optimiert werden, weil die Kopie des Zeigers zum internen Zeiger von __normal_iterator dem Compiler eigentlich als überflüssig erscheinen sollte.

Aber da würde ich nicht meine Hand ins Feuer halten.

[dot]

lto schrieb:

dot schrieb:

knivil schrieb:

Ob es schneller ist sei dahingestellt, den wenn ein Tool es aus der Schleife holen kann, dann kann es der Kompiler auch.

Spätestens, wenn der Compiler den Aufruf von .end() nichtmehr inlinen kann, wird ihm auch das kaum noch gelingen, denn um diese Transformation durchzuführen, muss er ja beweisen, dass .end() in jedem Durchlauf den selben Wert liefert; obige Definition einer range-based for loop dagegen, ist in jedem Fall optimal...

Jeder vernünftige Compiler bekommt das hin.

Wenn du es mit STL Containern zu tun hast, dann in der Regel wohl ja, aber im Allgemeinen gibt es eben Fälle, wo selbst der vernünftigste aller Compiler das rein prinzipiell nicht hinbekommen kann. Natürlich kann man immer per Hand seine Schleife optimieren...

Ich seh jedenfalls keinen Grund dazu, range-based for loops zu meiden. Ich kann damit kürzeren, ausdrucksstärkeren, besser lesbaren Code schreiben und bekomme im schlechtesten Fall gleich guten Maschinencode als mit einer funktional äquivalenten aber komplizierteren, normalen for loop...

[Nexus]

Sone schrieb:

Und ob man dann auf den internen, privat gespeicherten end-Iterator in vector zugreift, oder auf seinen eigenen lokalen, ist letztendlich egal.

Nein, denn bei einem end() -Aufruf ist es massiv schwieriger zu beweisen, dass sich der Wert zwischen den Iterationen nicht ändert, als bei einer lokalen Variable.

Der Scope der Membervariable ist viel grösser und vom Scope des Containers abhängig. Bei selbstgeschriebenen Containern sind ausserdem Multithreaded-Zugriffe, pro Aufruf neu berechnete end() -Iteratoren und tief verschachtelte Funktionen nicht auszuschliessen (bei der STL auch nicht, aber da kann der Compiler a priori Annahmen treffen). Insofern wundert es mich nicht, dass hier mit Range-Based For durchaus optimiert werden kann.

[Klaus82]

Puh,
da hatte ich etwas losgetreten. Auf jeden Fall danke für die Antworten, auch wenn mir viele wieder viel zu hoch sind.

Ich denke ich bleibe bei der Aussage: Wenn ein Programm das schafft, dann kann das der Compiler auch.

Auf jeden Fall sollte ich mir den Compiler und das nette Feature alles einzurücken genauer anschauen, ich bin beim Quellcode auch so ein Layout-Perfektionist.

Gruß,
-- Klaus.