Jaka jest technika inwersji pętli?

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.

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.

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); 
}

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 .

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ść.