Jaka jest technika inwersji pętli?

89

Przeglądałem dokument, który mówi o technikach optymalizacji kompilatora just -in-time (JIT) dla Javy. Jednym z nich była „inwersja pętli”. A dokument mówi:

Zastępujesz zwykłą whilepętlę do-whilepętlą. A do-whilepętla jest ustawiona w ramach ifklauzuli. Ta wymiana prowadzi do dwóch mniej skoków.

Jak działa inwersja pętli i jak optymalizuje naszą ścieżkę kodu?

NB: Byłoby wspaniale, gdyby ktoś mógł wyjaśnić na przykładzie kodu Java i jak JIT optymalizuje go do kodu natywnego i dlaczego jest optymalny w nowoczesnych procesorach.

Próbować
źródło
2
To nie jest coś, co zrobiłbyś ze swoim kodem źródłowym. Dzieje się to na poziomie kodu natywnego.
Marko Topolnik
2
@MarkoTopolnik Wiem. Ale chcę wiedzieć, jak robi to JIT na poziomie kodu natywnego. Dzięki.
Próba
1
och fajnie, jest na ten temat strona wikipedii z wieloma przykładami en.wikipedia.org/wiki/Loop_inversion . Przykład w C jest tak samo ważny w Javie.
Benjamin Gruenbaum
Jakiś czas temu zainspirowany jednym z pytań dotyczących SO przeprowadziłem krótkie badanie w tej sprawie, być może wyniki będą dla Ciebie pomocne: stackoverflow.com/questions/16205843/java-loop-efficiency/…
Adam Siemion
Czy jest to to samo, co sytuacja, w której warunek pętli jest zwykle umieszczany na końcu (niezależnie od tego, czy będzie mniej skoków), tylko po to, aby było mniej instrukcji skoku (1 vs 2 na iterację)?
extremeaxe5

Odpowiedzi:

108
while (condition) { 
  ... 
}

Przepływ pracy:

  1. sprawdzić stan;
  2. jeśli fałsz, przeskocz na zewnątrz pętli;
  3. uruchom jedną iterację;
  4. wskocz na górę.

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

Przepływ pracy:

  1. sprawdzić stan;
  2. jeśli fałsz, przeskocz poza pętlę;
  3. uruchom jedną iterację;
  4. sprawdzić stan;
  5. jeśli prawda, przejdź do kroku 3.

Porównując te dwa, można łatwo zauważyć, że ten ostatni może w ogóle nie wykonywać żadnych skoków, pod warunkiem, że w pętli jest dokładnie jeden krok i ogólnie liczba skoków będzie o jeden mniejsza niż liczba iteracji. Ten pierwszy będzie musiał skoczyć z powrotem, aby sprawdzić warunek, tylko po to, aby wyskoczyć z pętli, gdy warunek jest fałszywy.

Skoki na nowoczesnych architekturach procesorów potokowych mogą być dość kosztowne: ponieważ procesor kończy wykonywanie sprawdzeń przed skokiem, instrukcje poza tym skokiem są już w połowie potoku. Całe to przetwarzanie musi zostać odrzucone, jeśli przewidywanie gałęzi nie powiedzie się. Dalsze wykonanie jest opóźnione podczas ponownego przygotowania potoku.

Wyjaśnienie wspomnianej prognozy rozgałęzienia : dla każdego rodzaju skoku warunkowego procesor ma dwie instrukcje, z których każda zawiera zakład na wynik. Na przykład, umieściłbyś instrukcję mówiącą „ skok, jeśli nie zero, obstawianie niezerowe ” na końcu pętli, ponieważ skok będzie musiał zostać wykonany we wszystkich iteracjach z wyjątkiem ostatniej. W ten sposób CPU zaczyna pompować swój potok z instrukcjami podążającymi za celem skoku zamiast tymi, które następują po samej instrukcji skoku.

Ważna uwaga

Proszę nie nie wziąć to jako przykład, jak zoptymalizować na poziomie kodu źródłowego. Byłoby to całkowicie błędne, ponieważ, jak już jasno wynika z twojego pytania, transformacja z pierwszej formy do drugiej jest czymś, co kompilator JIT robi rutynowo, całkowicie samodzielnie.

Marko Topolnik
źródło
51
Ta notatka na końcu jest naprawdę bardzo, bardzo ważna.
TJ Crowder
2
@AdamSiemion: Kod bajtowy wygenerowany dla danego do-whilekodu źródłowego jest nieistotny, ponieważ tak naprawdę tego nie piszemy. Piszemy whilepętlę i pozwalamy kompilatorowi i JIT współpracować, aby ulepszyć ją za nas (poprzez inwersję pętli), jeśli / w razie potrzeby.
TJ Crowder
1
@TJCrowder +1 za powyższe, plus uwaga do Adama: nigdy nie bierz pod uwagę kodu bajtowego, myśląc o optymalizacjach kompilatora JIT. Kod bajtowy jest znacznie bliższy kodowi źródłowemu Java niż faktycznemu wykonywanemu kodowi skompilowanemu w JIT. W rzeczywistości we współczesnych językach w ogóle nie ma kodu bajtowego jako części specyfikacji języka.
Marko Topolnik
1
Byłoby bardziej pouczające, że Ważna uwaga została wyjaśniona nieco więcej. Dlaczego miałoby to być całkowicie błędne?
arsaKasra
2
@arsaKasra To błąd, ponieważ ogólnie czytelność i stabilność przewyższają optymalizacje w kodzie źródłowym. Zwłaszcza po odkryciu, że JIT robi to za Ciebie, nie powinieneś podejmować samodzielnych prób (bardzo mikro) optymalizacji.
Radiodef
24

Może to zoptymalizować pętlę, która jest zawsze wykonywana przynajmniej raz.

Zwykła whilepętla zawsze przeskakuje z powrotem na początek przynajmniej raz i przeskakuje na koniec raz na końcu. Przykład prostej pętli działającej raz:

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

Z do-whiledrugiej strony pętla pominie pierwszy i ostatni skok. Oto analogiczna pętla do powyższej, która będzie działać bez skoków:

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}
Keppil
źródło
+1 za poprawność i najpierw rozważ dodanie przykładowego kodu. Coś podobnego boolean b = true; while(b){ b = maybeTrue();}do boolean b;do{ b = maybeTrue();}while(b);powinno wystarczyć.
Benjamin Gruenbaum
Bez obaw. To w pewnym sensie unieważnia pierwszą linię odpowiedzi, fwiw. :-)
TJ Crowder
@TJ Cóż, nadal nie zoptymalizuje pętli, która nie została wprowadzona, w obu przypadkach będzie jeden skok.
Keppil
O tak. Przepraszam, czytałem to, aby oznaczać, że nie można go zastosować do pętli, które nie zapętliły się co najmniej raz (a nie, że im to nie pomaga). Z Tobą teraz. :-)
TJ Crowder
@Keppil Prawdopodobnie powinieneś wyraźnie zaznaczyć, że w przypadku, gdy mamy dużą liczbę iteracji X, wtedy zapiszemy tylko jeden skok spośród X.
Manuel Selva
3

Przejdźmy przez nie:

whileWersja:

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}
  1. Najpierw testujemy ni przechodzimy do, done();jeśli warunek nie jest prawdziwy.
  2. Następnie używamy i zwiększamy n.
  3. Teraz wracamy do stanu.
  4. Spłucz, powtórz.
  5. Gdy warunek nie jest już spełniony, przechodzimy do done().

do-whileWersja:

(Pamiętaj, że tak naprawdę nie robimy tego w kodzie źródłowym [który wprowadziłby problemy z konserwacją], kompilator / JIT robi to za nas.)

void foo(int n) {
    if (n < 10) {
        do {
            use(n);
            ++n;
        }
        while (n < 10);
    }
    done();
}
  1. Najpierw testujemy ni przechodzimy do, done();jeśli warunek nie jest prawdziwy.
  2. Następnie używamy i zwiększamy n.
  3. Teraz sprawdzamy warunek i cofamy się, jeśli jest prawdziwy.
  4. Spłucz, powtórz.
  5. Kiedy warunek nie jest już prawdziwy, płyniemy (nie skaczemy) do done().

Na przykład, jeśli nzaczynamy być 9, nigdy w ogóle nie skaczemy w do-whilewersji, podczas gdy w whilewersji musimy skoczyć z powrotem na początek, zrobić test, a następnie skoczyć z powrotem do końca, gdy widzimy, że to nieprawda .

TJ Crowder
źródło
3

Odwrócenie pętli to technika optymalizacji wydajności, która poprawia wydajność, ponieważ procesor może osiągnąć ten sam wynik przy mniejszej liczbie instrukcji. Powinno to przede wszystkim poprawić wydajność w warunkach brzegowych.

To łącze zawiera kolejny przykład odwrócenia pętli. W kilku architekturach, w których dekrementacja i porównanie są implementowane jako pojedynczy zestaw instrukcji, sensowne jest przekonwertowanie pętli for na chwilę z dekrementacją i porównaniem operacji.

Wikipedia ma bardzo dobry przykład i jeszcze raz to wyjaśniam.

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

zostanie przekonwertowany przez kompilator do

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

Jak to się przekłada na wydajność? Gdy wartość i wynosi 99, procesor nie musi wykonywać GOTO (co jest wymagane w pierwszym przypadku). Poprawia to wydajność.

Anirudhan J
źródło