Flaga optymalizacji gcc -O3 sprawia, że ​​kod jest wolniejszy niż -O2

Question

Ten temat jest znany pod numerem Why is it faster to process a sorted array than an unsorted array?. I spróbuj uruchomić ten kod. I znajduję dziwne zachowanie. Jeśli skompiluję ten kod z flagą optymalizacji -O3, uruchomi się 2.98605 sec. Jeśli kompiluję się z -O2, zajmuje on 1.98093 sec. Próbuję uruchomić ten kod kilka razy (5 lub 6) na tym samym komputerze w tym samym środowisku, zamykam całe inne oprogramowanie (chrome, skype itp.).

gcc --version 
gcc (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2 
Copyright (C) 2014 Free Software Foundation, Inc. 
This is free software; see the source for copying conditions. There is NO 
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 

Proszę wyjaśnić mi, dlaczego tak się dzieje? Przeczytałem instrukcję gcc i widzę, że -O3 zawiera -O2. Dziękuje Ci za pomoc.

P.S. dodać kod

#include <algorithm> 
#include <ctime> 
#include <iostream> 

int main() 
{ 
    // Generate data 
    const unsigned arraySize = 32768; 
    int data[arraySize]; 

    for (unsigned c = 0; c < arraySize; ++c) 
     data[c] = std::rand() % 256; 

    // !!! With this, the next loop runs faster 
    std::sort(data, data + arraySize); 

    // Test 
    clock_t start = clock(); 
    long long sum = 0; 

    for (unsigned i = 0; i < 100000; ++i) 
    { 
     // Primary loop 
     for (unsigned c = 0; c < arraySize; ++c) 
     { 
      if (data[c] >= 128) 
       sum += data[c]; 
     } 
    } 

    double elapsedTime = static_cast<double>(clock() - start)/CLOCKS_PER_SEC; 

    std::cout << elapsedTime << std::endl; 
    std::cout << "sum = " << sum << std::endl; 
} 

Answer 1

gcc -O3 wykorzystuje cmov warunkowej, dzięki czemu wydłuża się łańcuch zależności pętli przenoszony do obejmują cmov (co 2 UOPs i 2 cykle opóźnienia na swojej Intel Sandy Bridge CPU według Agner Fog's instruction tables Zobacz także wiki tagów x86. To jest one of the cases where cmov sucks.

Jeśli dane były nawet umiarkowanie nieprzewidywalne, prawdopodobnie wygrałby cmov, więc jest to rozsądny wybór dla kompilatora. (Jednak, compilers may sometimes use branchless code too much.)

I put your code on the Godbolt compiler explorer, aby zobaczyć asm (z ładnym podświetlaniem i odfiltrowywaniem nieistotnych linii.) Nadal musisz przewinąć poza cały kod sortowania, aby dostać się do main(), chociaż).

.L82: # the inner loop from gcc -O3 
    movsx rcx, DWORD PTR [rdx] # sign-extending load of data[c] 
    mov  rsi, rcx 
    add  rcx, rbx  # rcx = sum+data[c] 
    cmp  esi, 127 
    cmovg rbx, rcx  # sum = data[c]>127 ? rcx : sum 
    add  rdx, 4   # pointer-increment 
    cmp  r12, rdx 
    jne  .L82 

gcc mógł zapisać MOV, używając LEA zamiast ADD.

Zatkania pętli na opóźnienie ADD-> CMOV (3 cykle), ponieważ jedna iteracja pętli zapisuje rbx z CMO, a następna iteracja odczytuje rbx z ADD.

Pętla zawiera tylko 8 zgrzewanych domen, więc może wydać jedną na 2 cykle. Nacisk na port roboczy nie jest tak poważnym wąskim gardłem, jak opóźnienie łańcucha dep, ale jest blisko (Sandybridge ma tylko 3 porty ALU, w przeciwieństwie do 4 Haswella).

BTW, zapisanie go jako sum += (data[c] >= 128 ? data[c] : 0); w celu odebrania cmov z łańcucha deportowanego jest potencjalnie przydatne. Ciągle dużo instrukcji, ale cmov w każdej iteracji jest niezależna. Ten compiles as expected in gcc6.3 -O2 and earlier, ale gcc7 de-optymalizuje do cmov na ścieżce krytycznej (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82666). (Automatycznie wektoryzuje się z wcześniejszymi wersjami gcc niż sposobem pisania if()).

Klang zabiera cmov z krytycznej ścieżki, nawet z oryginalnym źródłem.

---

gcc -O2 używa Branch (dla gcc5.x i starszych), który przewiduje, dobrze, bo dane są sortowane. Ponieważ współczesne procesory używają predykcji rozgałęzień do obsługi zależności kontrolnych, łańcuch zależny od pętli jest krótszy: tylko add (opóźnienie jednego cyklu).

Porównywanie i rozgałęzienie w każdej iteracji jest niezależne, dzięki prognozie rozgałęzienia + spekulatywnemu wykonaniu, które pozwala na kontynuowanie wykonywania, zanim znany będzie kierunek odgałęzienia.

.L83: # The inner loop from gcc -O2 
    movsx rcx, DWORD PTR [rdx] # load with sign-extension from int32 to int64 
    cmp  ecx, 127 
    jle  .L82  # conditional-jump over the next instruction 
    add  rbp, rcx # sum+=data[c] 
.L82: 
    add  rdx, 4 
    cmp  rbx, rdx 
    jne  .L83 

Istnieją dwa łańcuchy zależności: noszone w pętli: sum i licznik pętli. sum ma długość 0 lub 1 cyklu, a licznik pętli ma zawsze 1 cykl. Jednak pętla to 5 zgrupowanych domen-domen na Sandybridge, więc i tak nie można wykonać 1c na iterację, więc opóźnienie nie jest wąskim gardłem.

Prawdopodobnie działa w około jednej iteracji na 2 cykle (wąskie gardło w przypadku przekazywania instrukcji oddziału), w porównaniu z jednym na 3 cykle dla pętli -O3. Następnym wąskim gardłem będzie przepustowość ALU: 4 ALU ups (w nieużywanym przypadku), ale tylko 3 porty ALU. (ADD może działać na dowolnym porcie).

Ta prognoza analizy rurociągów pasuje dokładnie do czasu wynoszącego ~ 3 s dla -O3 vs. ~ 2 s dla -O2.

---

Haswell/Skylake może uruchomić nie odbieranego w jednym przypadku na 1,25 cykli, gdyż może to wykonać nie odbierane oddział w tym samym cyklu, jak zdjęcie wykonane gałęzi i posiada 4 porty el. (Lub nieco mniej od a 5 uop loop doesn't quite issue at 4 uops every cycle).

(tylko przetestowane.. Skylake @ 3.9GHz uruchamia wersję Branchy całego programu w 1.45s, lub branchless wersję w 1.68s Więc różnica jest znacznie mniejsza istnieje)

---

g + +6.3.1 używa cmov nawet przy -O2, ale g ++ 5.4 nadal zachowuje się jak 4.9.2.

Z obu g ++ 6.3.1 i g ++ 5.4, używając -fprofile-generate/-fprofile-use produkuje wersję Branchy nawet przy -O3 (z -fno-tree-vectorize).

Wersja CMOV pętli z nowszego gcc używa add ecx,-128/cmovge rbx,rdx zamiast CMP/CMOV. To trochę dziwne, ale prawdopodobnie nie zwalnia to. ADD zapisuje rejestr wyjściowy, a także flagi, więc tworzy większy nacisk na liczbę fizycznych rejestrów. Ale dopóki to nie jest wąskie gardło, powinno być prawie równe.

---

Nowszy gcc automatycznie wektoryzuje pętlę za pomocą -O3, co oznacza znaczne przyspieszenie nawet przy SSE2. (np. my i7-6700k Skylake uruchamia wektorową wersję w 0,74 s, czyli około dwa razy szybciej niż skalar, lub -O3 -march=native w 0.35s, używając wektorów AVX2 256b).

Wektoryzowana wersja wygląda jak wiele instrukcji, ale nie jest tak źle, a większość z nich nie jest częścią łańcucha prowadzonego przez pętlę dep. Wystarczy rozpakować do elementów 64-bitowych pod koniec. Jednak dwukrotnie robi to pcmpgtd, ponieważ nie zdaje sobie sprawy, że może ono po prostu zerować rozszerzenie zamiast przedłużenia znaku, gdy warunek wyzerował już wszystkie ujemne liczby całkowite.