Kiedy, jeśli w ogóle, rozwijanie pętli jest nadal przydatne?

Próbowałem zoptymalizować jakiś niezwykle krytyczny dla wydajności kod (algorytm szybkiego sortowania, który jest nazywany milionami razy w symulacji Monte Carlo) przez rozwijanie pętli. Oto wewnętrzna pętla, którą próbuję przyspieszyć:

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

Próbowałem rozwinąć się do czegoś takiego:

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
}

Nie miało to absolutnie żadnego znaczenia, więc zmieniłem go z powrotem na bardziej czytelną formę. Miałem podobne doświadczenia, kiedy próbowałem rozwinąć pętlę. Biorąc pod uwagę jakość predyktorów gałęzi na nowoczesnym sprzęcie, czy rozwijanie pętli jest nadal użyteczną optymalizacją, jeśli w ogóle?

Rozwijanie pętli ma sens, jeśli możesz zerwać łańcuchy zależności. Daje to niesprawnemu lub superskalarnemu procesorowi możliwość lepszego planowania rzeczy, a tym samym szybszego działania.

Prosty przykład:

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

Tutaj łańcuch zależności argumentów jest bardzo krótki. Jeśli pojawi się blokada, ponieważ masz brak pamięci podręcznej w tablicy danych, procesor nie może nic zrobić, tylko czekać.

Z drugiej strony ten kod:

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;

mógł działać szybciej. Jeśli w jednym obliczeniu otrzymasz chybienie w pamięci podręcznej lub inne przeciągnięcie, nadal istnieją trzy inne łańcuchy zależności, które nie zależą od przeciągnięcia. Niedziałający procesor CPU może je wykonywać.

Nie zrobiłoby to żadnej różnicy, ponieważ robisz taką samą liczbę porównań. Oto lepszy przykład. Zamiast:

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

pisać:

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

Nawet wtedy prawie na pewno nie będzie to miało znaczenia, ale teraz wykonujesz 50 porównań zamiast 200 (wyobraź sobie, że porównanie jest bardziej złożone).

Ogólnie rzecz biorąc, ręczne rozwijanie pętli jest w dużej mierze artefaktem historii. To kolejna z rosnącej listy rzeczy, które dobry kompilator zrobi za Ciebie, gdy będzie to miało znaczenie. Na przykład większość ludzi nie zawraca sobie głowy pisaniem x <<= 1lub x += xzamiast tego x *= 2. Po prostu piszx *= 2 a kompilator zoptymalizuje go pod kątem najlepszego.

Zasadniczo coraz mniej jest potrzeby odgadywania kompilatora.

Niezależnie od przewidywania gałęzi na nowoczesnym sprzęcie, większość kompilatorów i tak wykonuje dla ciebie rozwijanie pętli.

Warto byłoby dowiedzieć się, ile optymalizacji robi dla Ciebie Twój kompilator.

Znalazłem prezentacja Felix von Leitner za bardzo oświecania na ten temat. Polecam ci to przeczytać. Podsumowanie: Nowoczesne kompilatory są BARDZO sprytne, więc optymalizacje rąk prawie nigdy nie są skuteczne.

O ile rozumiem, nowoczesne kompilatory już rozwijają pętle tam, gdzie jest to właściwe - na przykład gcc, jeśli przeszedł optymalizację, oznacza to, że instrukcja mówi, że:

Rozwiń pętle, których liczbę iteracji można określić w czasie kompilacji lub przy wejściu do pętli.

Zatem w praktyce jest prawdopodobne, że Twój kompilator zrobi za Ciebie trywialne przypadki. Dlatego to od Ciebie zależy, czy kompilator będzie mógł łatwo określić, ile iteracji będzie potrzebnych, jak najwięcej pętli.

Rozwijanie pętli, niezależnie od tego, czy jest to rozwijanie ręczne, czy rozwijanie kompilatora, często może przynosić skutki odwrotne do zamierzonych, szczególnie w przypadku nowszych procesorów x86 (Core 2, Core i7). Podsumowując: testuj swój kod z rozwijaniem pętli i bez niego na dowolnych procesorach, na których planujesz wdrożyć ten kod.

Próbowanie bez wiedzy nie jest sposobem na to.
Czy ten rodzaj zajmuje dużo czasu?

Wszystko, co robi rozwijanie pętli, to zmniejszenie narzutu pętli na zwiększanie / zmniejszanie, porównywanie warunku zatrzymania i przeskakiwanie. Jeśli to, co robisz w pętli, zajmuje więcej cykli instrukcji niż sama narzut pętli, nie zobaczysz znacznej poprawy procentowej.

Oto przykład, jak uzyskać maksymalną wydajność.

W określonych przypadkach pomocne może być rozwijanie pętli. Jedyny zysk to nie pominięcie niektórych testów!

Może na przykład pozwolić na zamianę skalarną, wydajne wstawianie wstępnego pobierania oprogramowania ... Zdziwiłbyś się, jak bardzo może to być przydatne (możesz łatwo uzyskać 10% przyspieszenie na większości pętli, nawet przy -O3), agresywnie rozwijając.

Jak już wcześniej powiedziano, zależy to w dużej mierze od pętli, a kompilator i eksperyment są konieczne. Trudno jest stworzyć regułę (lub heurystyka kompilatora dla rozwijania byłaby idealna)

Rozwinięcie pętli całkowicie zależy od rozmiaru problemu. Jest to całkowicie zależne od tego, czy twój algorytm jest w stanie zmniejszyć rozmiar do mniejszych grup prac. To, co zrobiłeś powyżej, nie wygląda tak. Nie jestem pewien, czy można w ogóle rozwinąć symulację Monte Carlo.

Dobrym scenariuszem rozwijania pętli byłoby obracanie obrazu. Ponieważ można było zmieniać poszczególne grupy pracy. Aby to zadziałało, musiałbyś zmniejszyć liczbę iteracji.

Odwijanie pętli jest nadal przydatne, jeśli istnieje wiele zmiennych lokalnych zarówno w pętli, jak i z nią. Aby ponownie użyć tych rejestrów więcej, zamiast zapisywać jeden dla indeksu pętli.

W twoim przykładzie używasz niewielkiej ilości zmiennych lokalnych, nie nadużywając rejestrów.

Porównanie (do końca pętli) jest również główną wadą, jeśli porównanie jest ciężkie (tj. Nie jest testinstrukcją), zwłaszcza jeśli zależy od funkcji zewnętrznej.

Rozwijanie pętli pomaga również zwiększyć świadomość procesora w zakresie przewidywania gałęzi, ale i tak się to dzieje.