Frage Wann, wenn überhaupt, ist Loop Enrolling immer noch sinnvoll?


Ich habe versucht, extrem leistungskritischen Code (ein schneller Sortieralgorithmus, der millionenfach in einer Monte-Carlo-Simulation aufgerufen wird) durch Loop-Enrolling zu optimieren. Hier ist die innere Schleife, die ich versuche zu beschleunigen:

// Search for elements to swap.
while(myArray[++index1] < pivot) {}
while(pivot < myArray[--index2]) {}

Ich habe versucht, mich auf etwas wie:

while(true) {
    if(myArray[++index1] < pivot) break;
    if(myArray[++index1] < pivot) break;
    // More unrolling
}


while(true) {
    if(pivot < myArray[--index2]) break;
    if(pivot < myArray[--index2]) break;
    // More unrolling
}

Dies machte absolut keinen Unterschied, also änderte ich es wieder in die besser lesbare Form. Ich habe ähnliche Erfahrungen gemacht, wenn ich Loop Looping probiert habe. Angesichts der Qualität von Branch Prädiktoren auf moderner Hardware, wenn, wenn überhaupt, ist Loop Enrolling immer noch eine nützliche Optimierung?


75
2018-02-27 22:41


Ursprung


Antworten:


Schleifen-Abrollung ist sinnvoll, wenn Sie Abhängigkeitsketten auflösen können. Dies gibt einer außerbetrieblichen oder super-skalaren CPU die Möglichkeit, Dinge besser zu planen und somit schneller zu laufen.

Ein einfaches Beispiel:

for (int i=0; i<n; i++)
{
  sum += data[i];
}

Hier ist die Abhängigkeitskette der Argumente sehr kurz. Wenn Sie einen Block bekommen, weil Sie ein Cache-Miss auf dem Daten-Array haben, kann die CPU nichts anderes tun, als zu warten.

Auf der anderen Seite dieser Code:

for (int i=0; i<n; i+=4)
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;

könnte schneller laufen. Wenn Sie in einer Berechnung einen Cache-Fehltreffer oder eine andere Blockierung erhalten, gibt es noch drei weitere Abhängigkeitsketten, die nicht von der Blockierung abhängen. Eine nicht funktionierende CPU kann diese ausführen.


99
2018-02-27 22:54



Diese würden keinen Unterschied machen, weil Sie die gleiche Anzahl von Vergleichen machen. Hier ist ein besseres Beispiel. Anstatt von:

for (int i=0; i<200; i++) {
  doStuff();
}

schreiben:

for (int i=0; i<50; i++) {
  doStuff();
  doStuff();
  doStuff();
  doStuff();
}

Selbst dann ist es fast sicher egal, aber Sie machen jetzt 50 Vergleiche statt 200 (stellen Sie sich vor, der Vergleich ist komplexer).

Handbuch Regelmäßiges Loop Entrollen ist jedoch weitgehend ein Artefakt der Geschichte. Es ist eine weitere der wachsenden Liste von Dingen, die ein guter Compiler für Sie tun wird, wenn es darauf ankommt. Zum Beispiel schreiben die meisten Leute nicht zu schreiben x <<= 1 oder x += x Anstatt von x *= 2. Du schreibst einfach x *= 2 und der Compiler wird es für Sie optimieren, was immer das Beste ist.

Grundsätzlich ist es immer weniger notwendig, den Compiler zu hinterfragen.


19
2018-02-27 22:44



Unabhängig von der Verzweigungsprognose auf moderner Hardware machen die meisten Compiler das Loop-Abrolling trotzdem für Sie.

Es lohnt sich herauszufinden, wie viele Optimierungen Ihr Compiler für Sie tut.

ich fand Felix von Leitners Präsentation sehr aufschlussreich über das Thema. Ich empfehle Ihnen, es zu lesen. Zusammenfassung: Moderne Compiler sind SEHR clever, so dass Handoptimierungen fast nie effektiv sind.


13
2018-02-27 22:48



Soweit ich es verstehe, entschlüs- sen moderne Compiler bereits Schleifen, wo es angebracht ist - ein Beispiel ist gcc, wenn die Optimierungsflags übergeben werden, sagt das Handbuch:

Schleifen Sie Schleifen, deren Anzahl von   Iterationen können bei bestimmt werden   Kompilierzeit oder beim Eintritt in die   Schleife.

In der Praxis ist es wahrscheinlich, dass Ihr Compiler die Trivialfälle für Sie übernimmt. Es liegt daher an Ihnen, sicherzustellen, dass möglichst viele Ihrer Schleifen für den Compiler einfach sind, um zu bestimmen, wie viele Iterationen benötigt werden.


2
2018-02-27 22:50



Das Schleifen-Abrolling, sei es das Abrollen von Hand oder das Abrollen des Compilers, kann oft kontraproduktiv sein, insbesondere bei neueren x86-CPUs (Core 2, Core i7). Fazit: Vergleichen Sie Ihren Code mit und ohne Loop, der auf allen CPUs ausgeführt wird, für die Sie diesen Code bereitstellen möchten.


2
2018-02-27 23:40



Versuchen, ohne zu wissen, ist nicht der Weg, es zu tun.
Hat diese Art einen hohen Prozentsatz an Gesamtzeit?

Alle Loop-Abrollvorgänge reduzieren den Schleifen-Overhead von Inkrementieren / Dekrementieren, Vergleichen für die Stop-Bedingung und Springen. Wenn das, was Sie in der Schleife tun, mehr Befehlszyklen benötigt als der Schleifenoverhead selbst, werden Sie nicht viel Verbesserung prozentual sehen.

Hier ist ein Beispiel, wie Sie maximale Leistung erhalten.


1
2018-02-28 16:41



Schleifenabrollen kann in bestimmten Fällen hilfreich sein. Der einzige Vorteil ist, einige Tests nicht zu überspringen!

Es kann zum Beispiel skalaren Ersatz, effizientes Einfügen von Software-Prefetching ermöglichen ... Sie würden überrascht sein, wie nützlich es sein kann (Sie können leicht 10% Beschleunigung auf den meisten Schleifen sogar mit -O3) durch aggressives Abrollen erhalten.

Wie es vorher gesagt wurde, hängt es sehr von der Schleife ab und der Compiler und das Experiment sind notwendig. Es ist schwer eine Regel zu machen (oder die Compiler-Heuristik zum Abrollen wäre perfekt)


1
2018-03-01 20:38



Das Loop-Enrolling hängt vollständig von Ihrer Problemgröße ab. Es ist völlig abhängig von Ihrem Algorithmus in der Lage, die Größe in kleinere Gruppen von Arbeit zu reduzieren. Was du oben gemacht hast, sieht nicht so aus. Ich bin mir nicht sicher, ob eine Monte-Carlo-Simulation sogar abgerollt werden kann.

Ein gutes Szenario für das Loop-Enrolling wäre das Drehen eines Bildes. Da könntest du separate Arbeitsgruppen drehen. Um dies zu erreichen, müssten Sie die Anzahl der Iterationen reduzieren.


0
2018-02-27 22:45



Das Schleifenausrollen ist immer noch nützlich, wenn viele lokale Variablen in und mit der Schleife vorhanden sind. Um diese Register wiederzuverwenden, anstatt eines für den Schleifenindex zu speichern.

In Ihrem Beispiel verwenden Sie eine kleine Menge an lokalen Variablen, nicht über die Verwendung der Register.

Der Vergleich (zum Schleifenende) ist auch ein Hauptnachteil, wenn der Vergleich schwer ist (d. H.test Anweisung), insbesondere wenn es auf eine externe Funktion ankommt.

Das Schleifenausrollen hilft dabei, das CPU-Bewusstsein für die Verzweigungsvorhersage ebenfalls zu erhöhen, aber diese treten trotzdem auf.


0
2018-02-27 22:49