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

93

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?

dsimcha
źródło
1
Czy mogę zapytać, dlaczego nie używasz standardowych procedur szybkiego sortowania w bibliotece?
Peter Alexander
14
@Poita: Ponieważ moje mają kilka dodatkowych funkcji, których potrzebuję do obliczeń statystycznych, które wykonuję i są bardzo dobrze dostosowane do moich przypadków użycia, a zatem mniej ogólne, ale mierzalnie szybsze niż standardowa biblioteka. Używam języka programowania D, który ma stary, kiepski optymalizator, a dla dużych tablic losowych wartości zmiennoprzecinkowych nadal pokonuję C ++ STL w GCC o 10-20%.
dsimcha,

Odpowiedzi:

122

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

Nils Pipenbrinck
źródło
2
Dzięki. Próbowałem rozwinąć pętlę w tym stylu w kilku innych miejscach w bibliotece, w których obliczam sumy i takie tam, i tam działa cuda. Jestem prawie pewien, że powodem jest to, że zwiększa równoległość poziomu instrukcji, jak sugerujesz.
dsimcha
2
Ładna odpowiedź i pouczający przykład. Chociaż nie widzę, jak blokady związane z brakami pamięci podręcznej mogą wpłynąć na wydajność w tym konkretnym przykładzie . Przyszedłem, aby wyjaśnić sobie różnice w wydajności między dwoma fragmentami kodu (na moim komputerze drugi fragment kodu jest 2-3 razy szybszy), zauważając, że pierwszy wyłącza wszelkiego rodzaju paralelizm na poziomie instrukcji na ścieżkach zmiennoprzecinkowych. Drugi pozwoliłby superskalarnemu procesorowi na wykonanie do czterech operacji zmiennoprzecinkowych w tym samym czasie.
Toby Brull
2
Należy pamiętać, że wynik nie będzie numerycznie identyczny z oryginalną pętlą podczas obliczania sumy w ten sposób.
Barabas
Zależność przenoszona w pętli to jeden cykl , dodawanie. Rdzeń OoO wystarczy. Tutaj rozwijanie może pomóc w zmiennoprzecinkowym SIMD, ale nie chodzi o OoO.
Veedrac,
2
@Nils: Niezbyt dużo; główne procesory x86 OoO są nadal wystarczająco podobne do Core2 / Nehalem / K10. Nadrabianie zaległości po chybieniu w pamięci podręcznej było nadal dość niewielkie, a ukrywanie opóźnienia FP było nadal główną korzyścią. W 2010 roku procesory, które potrafiły wykonać 2 obciążenia na zegar, były jeszcze rzadsze (tylko AMD, ponieważ SnB nie został jeszcze wydany), więc wiele akumulatorów było zdecydowanie mniej wartościowych dla kodu całkowitego niż teraz (oczywiście jest to kod skalarny, który powinien automatycznie wektoryzować , więc kto wie, czy kompilatory zmieni wiele elementów wektorów do akumulatorów lub do wielu wektorów akumulatorów ...)
Peter Cordes
25

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.

cletus
źródło
1
@Mike Z pewnością wyłączanie optymalizacji, jeśli jest to dobry pomysł, gdy jesteś zdziwiony, ale warto przeczytać link, który opublikował Poita_. Kompilatorzy stają się boleśnie dobrzy w tym biznesie.
dmckee --- kociak ex-moderator
16
@Mike „Jestem w stanie zdecydować, kiedy i kiedy nie robić tych rzeczy”… Wątpię, chyba że jesteś nadczłowiekiem.
Mr. Boy
5
@John: Nie wiem, dlaczego to mówisz; ludzie wydają się myśleć, że optymalizacja jest rodzajem czarnej sztuki, tylko kompilatorzy i dobrzy zgadywacze wiedzą, jak to zrobić. Wszystko sprowadza się do instrukcji i cykli oraz powodów ich wykorzystania. Jak wiele razy wyjaśniałem w SO, łatwo jest powiedzieć, jak i dlaczego są one wydawane. Jeśli mam pętlę, która musi zużywać znaczny procent czasu i spędza zbyt wiele cykli w narzutu pętli w porównaniu z zawartością, mogę to zobaczyć i rozwinąć. To samo dotyczy podnoszenia kodu. To nie wymaga geniuszu.
Mike Dunlavey
3
Jestem pewien, że nie jest to takie trudne, ale nadal wątpię, czy możesz to zrobić tak szybko, jak robi to kompilator. Jaki jest problem z tym, że kompilator robi to za Ciebie? Jeśli ci się to nie podoba, po prostu wyłącz optymalizacje i spędź czas, jakby był rok 1990!
Mr. Boy
2
Wzrost wydajności wynikający z rozwijania pętli nie ma nic wspólnego z zapisywanymi porównaniami. Zupełnie nic.
bobbogo
14

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.

Peter Alexander
źródło
7
To dobra lektura, ale jedyną częścią, o której pomyślałem, że jest na liście, była ta, w której mówi o utrzymaniu prostej struktury danych. Reszta była dokładna, ale opiera się na gigantycznym, nieokreślonym założeniu - że to, co jest wykonywane, musi być. Podczas dostrajania, które wykonuję, ludzie martwią się o rejestry i błędy pamięci podręcznej, gdy ogromne ilości czasu spędzają w niepotrzebnych górach kodu abstrakcji.
Mike Dunlavey
4
„optymalizacje rąk prawie nigdy nie są skuteczne” → Być może prawda, jeśli zadanie jest dla Ciebie zupełnie nowe. Po prostu nie jest prawdą, inaczej.
Veedrac,
W 2019 roku nadal wykonywałem ręczne rozpakowywanie, uzyskując znaczne korzyści w porównaniu z automatycznymi próbami kompilatora ... więc nie jest tak niezawodne, aby kompilator zrobił to wszystko. Wydaje się, że nie rozwija się zbyt często. Przynajmniej c # nie mogę mówić w imieniu wszystkich języków.
WDUK
2

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.

Rich Bradshaw
źródło
W samą porę kompilatory zwykle nie rozwijają pętli, heurystyki są zbyt kosztowne. Kompilatory statyczne mogą poświęcić na to więcej czasu, ale różnica między dwoma dominującymi sposobami jest ważna.
Abel
2

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.

Paul R.
źródło
Dlaczego szczególnie w przypadku recet procesorów x86?
JohnTortugo,
7
@JohnTortugo: Nowoczesne procesory x86 mają pewne optymalizacje dla małych pętli - patrz np. Loop Stream Detector na architekturach Core i Nehalem - rozwinięcie pętli tak, że nie jest już wystarczająco mała, aby zmieścić się w pamięci podręcznej LSD, pokonuje tę optymalizację. Zobacz np. Tomshardware.com/reviews/Intel-i7-nehalem-cpu,2041-3.html
Paul R
1

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

Mike Dunlavey
źródło
1

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)

Kamczatka
źródło
0

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.

jwendl
źródło
Rozwijałem szybkie sortowanie, które jest wywoływane z wewnętrznej pętli mojej symulacji, a nie z głównej pętli symulacji.
dsimcha,
0

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.

LiraNuna
źródło