Schleifenentrollen & Optimierung

Question

den Code Gegeben:

for (int i = 0; i < n; ++i) 
{ 
    A(i) ; 
    B(i) ; 
    C(i) ; 
} 

und die Optimierung Version:

for (int i = 0; i < (n - 2); i+=3) 
{ 
    A(i) 
    A(i+1) 
    A(i+2) 
    B(i) 
    B(i+1) 
    B(i+2) 
    C(i) 
    C(i+1) 
    C(i+2) 
} 

Etwas ist mir nicht klar: was ist besser? Ich kann nichts sehen, das mit der anderen Version schneller funktioniert. Fehle ich hier etwas?

Alles, was ich sehe, ist, dass jeder Befehl auf der vorherige Instruktion abhängig, was bedeutete, dass ich, dass der vorherige Befehl würde, um warten müssen, beendet die einen nach dem Start ...

Dank

Answer 1

In der High-Level-Ansicht einer Sprache sehen Sie nicht die Optimierung. Die Geschwindigkeitsverbesserung kommt von dem, was der Compiler mit dem tut, was Sie haben.

Im ersten Fall ist es so etwas wie:

LOCATION_FLAG; 
DO_SOMETHING; 
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false 

In der zweiten ist es so etwas wie:

LOCATION_FLAG; 
DO_SOMETHING; 
DO_SOMETHING; 
DO_SOMETHING; 
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false 

Sie im letzteren Fall sehen können, der Aufwand für Tests und Springen nur 1 Anweisung pro 3. In der ersten ist es 1 Anweisung pro 1; so passiert es viel öfter. Wenn Sie Invarianten haben, auf die Sie sich verlassen können (ein Array von Mod 3, um Ihr Beispiel zu verwenden), ist es effizienter Loops abzuwickeln, da die zugrunde liegende Assembly direkter geschrieben wird.

Answer 2

Nun, ob dieser Code "besser" oder "schlechter" ist, hängt vollständig von den Implementierungen A, B und C ab, welche Werte von n Sie erwarten, welchen Compiler Sie verwenden und auf welcher Hardware Sie laufen.

Der Vorteil des Schleifenabrollens liegt in der Regel darin, dass der Aufwand für das Ausführen der Schleife (dh das Erhöhen i und das Vergleichen mit n) reduziert wird. In diesem Fall könnte um den Faktor 3 reduziert werden.

Answer 3

Loop-Abrollung wird verwendet, um die Anzahl der Sprung- & Verzweigungsbefehle zu reduzieren, die möglicherweise die Schleife schneller machen, aber die Größe der Binärdatei erhöhen. Je nach Implementierung und Plattform könnte beides schneller sein.

Answer 4

Solange die Funktionen A(), B() und C() nicht die gleichen Datensätze modifizieren, bietet die zweite Version mehr Parallelisierungsoptionen.

In der ersten Version können die drei Funktionen gleichzeitig ausgeführt werden, unter der Annahme, dass keine Abhängigkeiten bestehen. In der zweiten Version könnten alle drei Funktionen mit allen drei Datensätzen gleichzeitig ausgeführt werden, vorausgesetzt, Sie hatten genug Ausführungseinheiten, um dies zu tun, und wieder keine Abhängigkeiten.

Answer 5

Im Allgemeinen ist es keine gute Idee, Optimierungen zu "erfinden", es sei denn, Sie haben einen klaren Beweis dafür, dass Sie einen Anstieg erzielen, weil Sie oft eine Verschlechterung verursachen. In der Regel ist der beste Weg, um solche Beweise zu erhalten, mit einem guten Profiler. Ich würde beide Versionen dieses Codes mit einem Profiler testen, um den Unterschied zu sehen.

Auch Abrollen oft Schleife ist nicht sehr protable, wie bereits erwähnt, es hängt stark von der Plattform, Compiler usw.

Sie können zusätzlich mit den Compiler-Optionen spielen. Eine interessante Option ist gcc "-floop-optimize", dass Sie automatisch mit "-O, -O2, O3, und -Os" get

EDIT Zusätzlich Blick auf die "-funroll-Schleifen" Compiler Möglichkeit.