Können moderne Compiler "für" Schleifen auflösen, die mit Start- und Ende-Iteratoren ausgedrückt werden

  

Mir scheint, dass dies im Namen des Compilers mehr Intelligenz erfordert als gewöhnlich, um zunächst abzuleiten, dass der Iterator ein Direktzugriffsiterator ist, und dann herauszufinden, wie oft die Schleife ausgeführt wird.

Die STL, die vollständig aus Vorlagen besteht, hat den gesamten Code inline . So reduzieren sich Random-Access-Iteratoren bereits auf Zeiger, wenn der Compiler Optimierungen anwendet. Einer der Gründe, warum die STL erstellt wurde, war, dass ein Programmierer den Compiler nicht überlisten musste. Sie sollten sich auf die STL verlassen, um das Richtige zu tun, bis das Gegenteil bewiesen ist.

Natürlich liegt es immer noch an Ihnen, das richtige Werkzeug aus der STL zu wählen, um ...

Bearbeiten: Es wurde diskutiert, ob g++ Schleifen abrollt. In den Versionen, die ich benutze, ist Schleifen-Abrollung nicht Teil von -O , -O2 oder -O3 , und ich bekomme identische Assembly für die letzten beiden Ebenen mit dem folgenden Code:

Mit der entsprechenden Assembly -O2 assembly:

Wenn die Option -funroll-loops hinzugefügt wird, erweitert sich die Funktion in etwas viel Größeres. Aber die Dokumentation warnt vor dieser Option:

  

Unroll-Schleifen, deren Anzahl an Iterationen zum Zeitpunkt der Kompilierung oder beim Eintritt in die Schleife bestimmt werden kann. -funroll-loops impliziert -frunun-cse-after-loop. Es schaltet auch eine vollständige Schleifenablösung ein (d. H. Vollständiges Entfernen von Schleifen mit einer kleinen konstanten Anzahl von Iterationen). Mit dieser Option wird der Code größer und möglicherweise schneller ausgeführt.

Als weiteres Argument, um Sie davon abzuhalten, Loops selbst zu entrollen, beende ich diese Antwort mit einer Illustration der Anwendung von Duff's Device für die obige Funktion foo :

GCC hat ein anderes Schleifenoptimierungs-Flag:

  

-ftree-loop-optimize
  Führen Sie Schleifenoptimierungen für Bäume durch. Dieses Flag ist standardmäßig bei -O und höher aktiviert.

Diese Option ermöglicht einfache Schleifenoptimierungen für die innersten Schleifen, einschließlich des vollständigen Schleifen-Abrollvorgangs (Peeling) für Schleifen mit einer festen Anzahl von Iterationen. (Danke an Doc, dass er mich darauf hingewiesen hat.)

Ich würde vorschlagen, ob der Compiler die Schleife mit modernen Pipeline-Architekturen und Caches abwickeln kann oder nicht, es sei denn, Ihr "do stuff" ist trivial, es bringt wenig Nutzen, und dies wäre in vielen Fällen auch ein Leistung HIT statt eines Segens. Wenn Ihr "Do-Stuff" nicht-trivial ist, erzeugt das Abwickeln der Schleife mehrere Kopien dieses nicht-trivialen Codes, was zusätzliche Zeit zum Laden in den Cache benötigt, was die erste Iteration durch die entrollte Schleife erheblich verlangsamt. Gleichzeitig wird mehr Code aus dem Cache entfernt, der für die Ausführung des "Do-Zeugs" notwendig war, wenn er Funktionsaufrufe ausführt, die dann erneut in den Cache geladen werden müssten. Der Zweck zum Abwickeln von Schleifen war vor cache-losen Pipeline-Nicht-Verzweigungs-Vorhersage-Architekturen sehr sinnvoll, mit dem Ziel, den mit der Schleifenlogik verbundenen Overhead zu reduzieren. Heutzutage wird Ihre CPU bei cachebasierter Pipelined-Branch-Predictive-Hardware bis in die nächste Schleifeniteration pipelined und spekulativ den Schleifencode erneut ausführen, bis Sie die i == End-Exit-Bedingung erkennen, an welcher Stelle der Prozessor werfen wird aus dieser final spekulativ ausgeführten Reihe von Ergebnissen. In einer solchen Architektur macht Schleifen-Abrollung wenig Sinn. Es würde Code für praktisch keinen Vorteil aufblasen.

Einfache Antwort : Im Allgemeinen NEIN! Zumindest wenn es zum vollständigen Schleifen-Abrollvorgang kommt.

Lassen Sie uns das Schleifen auf dieser einfachen, schmutzigen (für Testzwecke) Struktur testen.

Zuerst nehmen wir die gezählte Schleife und kompilieren sie ohne irgendwelche Optimierungen.

Hier ist was gcc 4.9 produziert.

Wie erwartet, wurde die Schleife nicht ausgerollt, und da keine Optimierungen durchgeführt wurden, ist der Code im Allgemeinen sehr ausführlich. Jetzt schalten wir -O3 flag ein. Produziert Demontage:

Voila, Loop wurde diesmal abgerollt.

Sehen wir uns nun die iterierte Schleife an. Die Funktion, die die Schleife enthält, sieht so aus.

Immer noch mit dem -O3 -Flag, schauen wir uns die Disassembly an.

Code sieht besser aus als im ersten Fall, weil Optimierungen durchgeführt wurden, aber der Loop wurde dieses Mal nicht ausgerollt!

Was ist mit den Flags funroll-loops und funroll-all-loops ? Sie werden ein ähnliches Ergebnis produzieren.

Vergleichen Sie die Ergebnisse mit der abgerollten Schleife für die gezählte Schleife. Es ist eindeutig nicht das Gleiche. Was wir hier sehen, ist, dass gcc die Schleife in 8 Element-Chunks aufgeteilt hat. Dies kann in einigen Fällen die Leistung erhöhen, da die Loop-Exit-Bedingung einmal pro 8 normalen Schleifeniterationen überprüft wird. Mit zusätzlichen Flags konnte auch eine Vektorisierung durchgeführt werden. Aber es ist kein kompletter Schleifenabriß.

Iterierte Schleife wird jedoch ausgerollt, wenn Test object kein Funktionsargument ist.

Disassembly produziert mit nur -O3 flag:

Wie Sie sehen können, wurde loop entrollt. Dies liegt daran, dass der Compiler nun sicher annehmen kann, dass end einen festen Wert hat, während er dies für das Funktionsargument nicht vorhersagen konnte.

Test Struktur ist jedoch statisch zugeordnet. Die Dinge sind komplizierter mit dynamisch zugewiesenen Strukturen wie std::vector . Aus meinen Beobachtungen zur modifizierten Test -Struktur, so dass es dynamisch zugewiesenen Containern ähnelt, sieht es so aus, als ob gcc versucht, Schleifen am besten zu entrollen, aber in den meisten Fällen ist generierter Code nicht so einfach wie oben.

Wenn Sie nach anderen Compilern fragen, wird hier die Ausgabe von clang 3.4.1 ( -O3 flag)

Intels icc 13.01 ( -O3 flag)

Um Missverständnisse zu vermeiden. Wenn die Bedingung für die gezählte Schleife von einem externen Parameter wie diesem abhängt,

Eine solche Schleife wird auch nicht abgerollt.