Was ist die Schleifeninversionstechnik?

89

Ich habe ein Dokument durchgearbeitet, in dem es um Just-in-Time-Compiler- Optimierungstechniken (JIT) für Java geht. Eine davon war "Loop Inversion". Und das Dokument sagt:

Sie ersetzen eine reguläre whileSchleife durch eine do-whileSchleife. Und die do-whileSchleife wird innerhalb einer ifKlausel gesetzt. Dieser Ersatz führt zu zwei Sprüngen weniger.

Wie funktioniert die Schleifeninversion und wie optimiert sie unseren Codepfad?

NB: Es wäre großartig, wenn jemand anhand eines Beispiels für Java-Code erklären könnte, wie JIT ihn für nativen Code optimiert und warum er in modernen Prozessoren optimal ist.

Ich versuche es
quelle
2
Das würden Sie Ihrem Quellcode nicht antun. Dies geschieht auf nativer Codeebene.
Marko Topolnik
2
@ MarkoTopolnik Ich weiß. Aber ich möchte wissen, wie JIT dies auf nativer Codeebene macht. Vielen Dank.
Versuch
1
oh cool, es gibt eine Wikipedia-Seite dazu mit vielen Beispielen en.wikipedia.org/wiki/Loop_inversion . Das C-Beispiel ist in Java genauso gültig.
Benjamin Gruenbaum
Vor einiger Zeit, inspiriert von einer der Fragen zu SO, habe ich eine kurze Untersuchung in dieser Angelegenheit durchgeführt. Vielleicht sind die Ergebnisse für Sie hilfreich: stackoverflow.com/questions/16205843/java-loop-efficiency/…
Adam Siemion
Ist dies dasselbe wie dort, wo die Schleifenbedingung normalerweise am Ende gesetzt wird (unabhängig davon, ob weniger Sprünge ausgeführt werden), nur damit weniger Sprunganweisungen vorhanden sind (1 gegen 2 pro Iteration)?
extremeaxe5

Antworten:

108
while (condition) { 
  ... 
}

Arbeitsablauf:

  1. Zustand prüfen;
  2. Wenn false, springen Sie zur Außenseite der Schleife.
  3. Führen Sie eine Iteration aus.
  4. nach oben springen.

if (condition) do {
  ...
} while (condition);

Arbeitsablauf:

  1. Zustand prüfen;
  2. Wenn false, springen Sie über die Schleife hinaus.
  3. Führen Sie eine Iteration aus.
  4. Zustand prüfen;
  5. Wenn dies zutrifft, fahren Sie mit Schritt 3 fort.

Wenn Sie diese beiden vergleichen, können Sie leicht erkennen, dass letztere möglicherweise überhaupt keine Sprünge ausführen, vorausgesetzt, es gibt genau einen Schritt durch die Schleife, und im Allgemeinen ist die Anzahl der Sprünge um eins geringer als die Anzahl der Iterationen. Ersterer muss zurückspringen, um die Bedingung zu überprüfen, und nur dann aus der Schleife springen, wenn die Bedingung falsch ist.

Sprünge auf modernen Pipeline-CPU-Architekturen können sehr teuer sein: Da die CPU die Ausführung der Überprüfungen vor dem Sprung beendet, befinden sich die Anweisungen über diesen Sprung hinaus bereits in der Mitte der Pipeline. Diese gesamte Verarbeitung muss verworfen werden, wenn die Verzweigungsvorhersage fehlschlägt. Die weitere Ausführung wird verzögert, während die Pipeline erneut gestartet wird.

Erläuterung der erwähnten Verzweigungsvorhersage : Für jede Art von bedingtem Sprung verfügt die CPU über zwei Anweisungen, die jeweils eine Wette auf das Ergebnis enthalten. Zum Beispiel würden Sie am Ende einer Schleife eine Anweisung mit der Aufschrift " Sprung, wenn nicht Null, Wetten auf Nicht Null " einfügen, da der Sprung bei allen Iterationen mit Ausnahme der letzten ausgeführt werden muss. Auf diese Weise beginnt die CPU, ihre Pipeline mit den Anweisungen zu pumpen, die dem Sprungziel folgen, anstatt denen, die der Sprunganweisung selbst folgen.

Wichtige Notiz

Bitte nehmen Sie dies nicht als Beispiel für die Optimierung auf Quellcode-Ebene. Das wäre völlig falsch, da der JIT-Compiler, wie bereits aus Ihrer Frage hervorgeht, die Umwandlung von der ersten in die zweite Form routinemäßig und völlig eigenständig durchführt.

Marko Topolnik
quelle
51
Diese Notiz am Ende ist in der Tat eine sehr, sehr wichtige Sache.
TJ Crowder
2
@AdamSiemion: Der für den angegebenen do-whileQuellcode generierte Bytecode ist irrelevant, da wir das eigentlich nicht schreiben. Wir schreiben die whileSchleife und lassen den Compiler und JIT verschwören, um sie für uns zu verbessern (über Schleifeninversion), falls / nach Bedarf.
TJ Crowder
1
@TJCrowder +1 für das oben Gesagte sowie der Hinweis an Adam: Berücksichtigen Sie niemals den Bytecode, wenn Sie über die Optimierungen des JIT-Compilers nachdenken. Bytecode ist dem Java-Quellcode viel näher als dem tatsächlich ausgeführten JIT-kompilierten Code. Tatsächlich besteht der Trend in modernen Sprachen darin, überhaupt keinen Bytecode als Teil der Sprachspezifikation zu haben.
Marko Topolnik
1
Wäre besonders informativ gewesen, wurde der Wichtige Hinweis etwas näher erläutert. Warum sollte es völlig falsch sein?
ArsaKasra
2
@arsaKasra Es ist falsch, weil im Allgemeinen Lesbarkeit und Stabilität Optimierungen im Quellcode übertrumpfen. Insbesondere mit der Offenbarung, dass die JIT dies für Sie erledigt, sollten Sie die (sehr mikro-) Optimierung nicht selbst versuchen.
Radiodef
24

Dies kann eine Schleife optimieren, die immer mindestens einmal ausgeführt wird.

Eine reguläre whileSchleife springt dann immer mindestens einmal zum Anfang und am Ende einmal zum Ende. Ein Beispiel für eine einfache Schleife, die einmal ausgeführt wird:

int i = 0;
while (i++ < 1) {
    //do something
}  

Eine do-whileSchleife hingegen überspringt den ersten und letzten Sprung. Hier ist eine äquivalente Schleife wie oben, die ohne Sprünge ausgeführt wird:

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}
Keppil
quelle
+1 für die Richtigkeit und zuerst sollten Sie ein Codebeispiel hinzufügen. So etwas genügen sollte. boolean b = true; while(b){ b = maybeTrue();}boolean b;do{ b = maybeTrue();}while(b);
Benjamin Gruenbaum
Keine Sorge. Es macht die Eröffnungszeile der Antwort irgendwie ungültig, fwiw. :-)
TJ Crowder
@TJ Nun, eine Schleife, die nicht eingegeben wurde, wird immer noch nicht optimiert. In beiden Fällen wird es einen Sprung geben.
Keppil
Ah ja. Entschuldigung, ich habe das gelesen, um zu bedeuten, dass Sie es nicht auf Schleifen anwenden konnten, die nicht mindestens einmal wiederholt wurden (anstatt dass es ihnen nicht hilft). Mit dir jetzt. :-)
TJ Crowder
@Keppil Sie sollten wahrscheinlich deutlich machen, dass wir in dem Fall, in dem wir eine große Anzahl von Iterationen X haben, nur einen einzigen Sprung unter den X-Iterationen speichern.
Manuel Selva
3

Lassen Sie uns durch sie gehen:

Die whileVersion:

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}
  1. Zuerst testen wir nund springen zu, done();wenn die Bedingung nicht erfüllt ist.
  2. Dann verwenden und erhöhen wir n.
  3. Jetzt kehren wir zum Zustand zurück.
  4. Spülen, wiederholen.
  5. Wenn die Bedingung nicht mehr erfüllt ist, springen wir zu done().

Die do-whileVersion:

(Denken Sie daran, dass wir dies im Quellcode nicht tun [was zu Wartungsproblemen führen würde], der Compiler / JIT erledigt dies für uns.)

void foo(int n) {
    if (n < 10) {
        do {
            use(n);
            ++n;
        }
        while (n < 10);
    }
    done();
}
  1. Zuerst testen wir nund springen zu, done();wenn die Bedingung nicht erfüllt ist.
  2. Dann verwenden und erhöhen wir n.
  3. Jetzt testen wir den Zustand und springen zurück, wenn er wahr ist.
  4. Spülen, wiederholen.
  5. Wenn die Bedingung nicht mehr erfüllt ist, fließen wir (nicht springen) zu done().

So zum Beispiel, wenn nbeginnt zu sein 9, wir überhaupt nicht in der Sprung - do-whileVersion, während in der whileVersion müssen wir an den Anfang zurückspringen, tun Sie den Test, und dann bis zum Ende springen zurück , wenn wir es sehen , ist nicht wahr .

TJ Crowder
quelle
3

Die Schleifeninversion ist eine Technik zur Leistungsoptimierung, die die Leistung verbessert, da der Prozessor mit weniger Anweisungen das gleiche Ergebnis erzielen kann. Dies sollte vor allem die Leistung unter Randbedingungen verbessern.

Dieser Link bietet ein weiteres Beispiel für die Schleifeninversion. In wenigen Architekturen, in denen Dekrementieren und Vergleichen als ein einziger Befehlssatz implementiert ist, ist es sinnvoll, eine for-Schleife mit Dekrementierungs- und Vergleichsoperation in eine Weile umzuwandeln.

Wikipedia hat ein sehr gutes Beispiel und ich erkläre es hier noch einmal.

 int i, a[100];
  i = 0;
  while (i < 100) {
    a[i] = 0;
    i++;
  }

wird vom Compiler in konvertiert

  int i, a[100];
  i = 0;
  if (i < 100) {
    do {
      a[i] = 0;
      i++;
    } while (i < 100);
  }

Wie übersetzt sich dies in Leistung? Wenn der Wert von i 99 ist, muss der Prozessor kein GOTO ausführen (was im ersten Fall erforderlich ist). Dies verbessert die Leistung.

Anirudhan J.
quelle