C++: Czy kompilator może zoptymalizować ten segment kodu?

Question

void foo(const int constant) 
{ 
    for(int i = 0; i < 1000000; i++) { 
     // do stuff 
     if(constant < 10) {    // Condition is tested million times :(
      // inner loop stuff 
     } 
    } 
} 

Dla każdego wykonania zewnętrznej pętli sprawdzana jest wartość "stała". Jednak ciągłe, niezmienne zmiany powodują zmarnowanie dużej ilości czasu procesora, aby przetestować stałą warunku < 10? w kółko. Człowiek zda sobie sprawę z tego, że po pierwszych kilku przejściach ta stała nigdy się nie zmienia i inteligentnie unika jej powtarzania. Czy kompilator to zauważy i inteligentnie ją zoptymalizuje, czy też powtarzająca się pętla jest nieunikniona?

Osobiście uważam, że problem jest nieunikniony. Nawet jeśli kompilator umieści porównanie przed zewnętrzną pętlą i ustawi jakąś zmienną boolean "skip_inner_stuff", ta zmienna będzie musiała być sprawdzona dla każdego przebiegu zewnętrznej pętli for.

Co myślisz o tej sprawie? Czy istnieje skuteczniejszy sposób napisania powyższego segmentu kodu, który pozwoliłby uniknąć problemu?

Answer 1

Dobry kompilator zoptymalizuje to (gdy włączone są optymalizacje).

przypadku korzystania GCC można

• skompilować z generowania kodu optymalizacji montażowej z

  gcc -Wall -O2 -fverbose-asm -S source.c 
  

  następnie szukać (z jakiegoś edytora lub pagera jak less) do wygenerowanego kodu montażowej source.s

• poprosić GCC o zrzucenie wielu (setek!) Plików pośrednich i spojrzenie wewnątrz pośredniej reprezentacji gimple w nim

  gcc -Wall -O2 -fdump-tree-all -c source.c 
  

• zastosowanie MELT i jego probe wyglądać interaktywnie wewnątrz gimple.

^{Take zwyczaj zawsze prosząc wszystkich ostrzeżeń z -Wall z gcc (lub g++ jeśli kompilacji kodu C++.}

BTW, w praktyce, taka optymalizacja ("pętla kod niezmienna podnoszenia" jak wyjaśnia druga odpowiedź), ponieważ taki pośredni kod zdarza się bardzo często, np. po włączeniu funkcji .... (wyobraź sobie, że kilka połączeń z foo zostało wstawionych ...)

Answer 2

Opisana optymalizacja jest również nazywana loop unswitching. Od wielu lat jest standardową częścią optymalizacji kompilatorów - ale jeśli chcesz się upewnić, że kompilator ją wykonuje, skompiluj swój przykładowy kod z pewnym poziomem optymalizacji (na przykład -O2 w gcc) i sprawdź wygenerowany kod.

Jednak w przypadkach, w których kompilator nie może udowodnić, że fragment kodu jest niezmienny w całej pętli - np. wywołanie funkcji zewnętrznej, która nie jest dostępna w czasie kompilacji - w takim przypadku ręczne podniesienie kodu poza pętlę może przynieść bardzo duży wzrost wydajności.

Answer 3

można zoptymalizować go ręcznie:

void foo(const int constant) 
{ 
    if (constant < 10) { 
     for(int i = 0; i < 1000000; i++) { 
      // do stuff 

      // inner loop stuff here 
     } 
    } else { 
     for(int i = 0; i < 1000000; i++) { 
      // do stuff 

      // NO inner loop stuff here 
     } 
    } 
} 

Nie wiem, czy większość kompilatorów byłoby zrobić coś takiego, ale nie wydaje się zbyt dużym odcinku.

Answer 4

Właściwie wszystkie nowoczesne kompilatory optymalizują i przestrzegają tej optymalizacji, jeśli myślisz, że kompilator nie powinien wykonywać tej optymalizacji, powinieneś ustawić zmienną jako "lotną".

Answer 5

Kompilator może zoptymalizować kod, ale nie można oczekiwać, że zrobi magiczne sztuczki na kodzie.

Optymalizacja zależy w dużym stopniu od kodu i użycia kodu. Na przykład, jeśli używasz foo tak:

foo(12345); 

kompilator może zoptymalizować kod bardzo dużo. Nawet on może obliczyć wynik w czasie kompilacji.

Ale jeśli używasz go tak:

int k; 
cin >> k; 
foo(k); 

W tym przypadku nie może pozbyć wewnętrzna if (wartość jest w run-time).

pisałem przykładowy kod z MinGW/gcc-4.8.0:

void foo(const int constant) 
{ 
    int x = 0; 
    for (int i = 0; i < 1000000; i++) 
    { 
     x++; 
     if (constant < 10) 
     { 
      x--; 
     } 
    } 
    cout << x << endl; 
} 

int main() 
{ 
    int k; 
    cin >> k; 
    foo(k); 
} 

Zobaczmy wygenerować kod montaż:

004015E1 MOV EAX,0F4240     // i = 1000000 
004015E6 MOV EBP,ESP 
004015E8 XOR EDX,EDX 
004015EA PUSH ESI 
004015EB PUSH EBX 
004015EC SUB ESP,10 
004015EF MOV EBX,DWORD PTR SS:[EBP+8] 
004015F2 XOR ECX,ECX     // set ECX to 0 
004015F4 CMP EBX,0A      // if constant < 10 
      ^^^^^^^^^^ 
004015F7 SETGE CL      // then set ECX to 1 
004015FA ADD EDX,ECX     // add ECX to i 
004015FC SUB EAX,1      // i-- 
004015FF JNE SHORT 004015F2    // loop if i is not zero 

Jak widać wewnętrzna if istnieje w kodzie . Zobacz CMP EBX,0A.

Powtarzam jeszcze raz, mocno zależy to od linii z pętlami.

Answer 6

Inne dotyczyły odpowiednich optymalizacji kompilatora: wyłączenie pętli, co przenosi test poza pętlę i zapewnia dwa oddzielne korpusy pętli; oraz kodowanie, które w niektórych przypadkach zapewni kompilatorowi faktyczną wartość constant, aby mógł on usunąć test i albo wykonać "wewnętrzną pętlę" bezwarunkowo, albo całkowicie ją usunąć.

Należy również pamiętać, że niezależnie od tego, co robi kompilator, współczesne projekty procesorów faktycznie robią coś podobnego do "Człowiek zrozumie, że po pierwszych kilku przejściach ta stała nigdy się nie zmieni". Nazywa się to prognozą dynamicznego rozgałęzienia.

Najważniejsze jest to, że sprawdzenie liczby całkowitej jest niezwykle tanie, a nawet przyjęcie oddziału może być bardzo tanie. To, co potencjalnie drogie, to błędnie przewidywane gałęzie. Współczesne procesory używają różnych strategii, aby odgadnąć, w którą stronę pójdzie gałąź, ale wszystkie te strategie szybko zaczną poprawnie przewidywać gałąź, która idzie tak samo milion razy z rzędu.

Nie wiem, czy współczesne procesory są na tyle sprytne, aby wykryć, że constant jest niezmienną pętlą i czy nie przerywa pełnej pętli w mikrokodzie. Zakładając jednak prawidłowe przewidywanie rozgałęzień, niepoprawna pętla jest prawdopodobnie niewielką optymalizacją.Im bardziej konkretna rodzina procesorów jest kierowana przez kompilator, tym bardziej wie o jakości swojego predyktora gałęzi, a tym bardziej prawdopodobne jest, że kompilator może określić, czy dodatkowa korzyść w postaci nieprzekazywania pętli jest warta nadpisania kodu.

Oczywiście wciąż istnieją minimalne procesory, w których kompilator musi zapewnić całą sprytność. Procesor na twoim komputerze nie jest jednym z nich.

Answer 7

Dobry kompilator może zoptymalizować go.

Kompilatory optymalizują na podstawie analizy kosztów. Dobry kompilator powinien zatem oszacować koszt każdej alternatywy (z podnoszeniem i bez podnoszenia) i wybrać tę, która jest tańsza.

Oznacza to, że jeśli kod w wewnętrznej części jest duży, może nie być warty optymalizacji, ponieważ może to prowadzić do kasowania podręcznej instrukcji. Z drugiej strony, jeśli jest tani, można go podnieść.

Jeśli pojawia się w profilerze, ponieważ nie został zoptymalizowany, kompilator zawiedli.