Zastąpienie 32-bitowego licznika pętli 64-bitowym wprowadza szalone odchylenia wydajności od _mm_popcnt_u64 na procesorach Intel

1424

Szukałem najszybszego sposobu na popcountduże tablice danych. Spotkałem bardzo dziwny efekt: zmiana zmiennej pętli z unsignedna uint64_tsprawiła, że ​​wydajność spadła o 50% na moim komputerze.

Benchmark

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with unsigned
            for (unsigned i=0; i<size/8; i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }
    {
        startP = chrono::system_clock::now();
        count=0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with uint64_t
            for (uint64_t i=0;i<size/8;i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

Jak widać, tworzymy bufor losowych danych, których rozmiar to xmegabajty, gdzie xsą odczytywane z wiersza poleceń. Następnie popcountiterujemy bufor i używamy rozwiniętej wersji wewnętrznej x86, aby wykonać popcount. Aby uzyskać dokładniejszy wynik, robimy to 10 000 razy. Mierzymy czasy dla popcount. W górnej części zmienną pętli wewnętrznej jest unsigned, w małym przypadku zmienną pętli wewnętrznej jest uint64_t. Myślałem, że to nie powinno mieć znaczenia, ale jest odwrotnie.

(Absolutnie szalone) wyniki

Kompiluję to w ten sposób (wersja g ++: Ubuntu 4.8.2-19ubuntu1):

g++ -O3 -march=native -std=c++11 test.cpp -o test

Oto wyniki na moim Haswell Core i7-4770K CPU @ 3,50 GHz, działającym test 1(więc 1 MB danych losowych):

  • bez znaku 41959360000 0,401554 sec 26,133 GB / s
  • uint64_t 41959360000 0,759822 s 13,8003 GB / s

Jak widać, przepustowość uint64_twersji jest tylko o połowę mniejsza od unsignedwersji! Problem polega na tym, że generowany jest inny zestaw, ale dlaczego? Najpierw pomyślałem o błędzie kompilatora, więc spróbowałem clang++(Ubuntu Clang wersja 3.4-1ubuntu3):

clang++ -O3 -march=native -std=c++11 teest.cpp -o test

Wynik: test 1

  • bez znaku 41959360000 0,398293 s 26,26267 GB / s
  • uint64_t 41959360000 0,680954 s 15,3986 GB / s

Jest to więc prawie taki sam wynik i nadal jest dziwny. Ale teraz robi się bardzo dziwnie. Rozmiar bufora odczytanego z danych wejściowych zastępuję stałą 1, więc zmieniam:

uint64_t size = atol(argv[1]) << 20;

do

uint64_t size = 1 << 20;

Dlatego kompilator zna teraz rozmiar bufora w czasie kompilacji. Może może dodać kilka optymalizacji! Oto liczby dla g++:

  • bez znaku 41959360000 0,509156 s 20,5944 GB / s
  • uint64_t 41959360000 0,508673 s 20,6139 GB / s

Teraz obie wersje są równie szybkie. Jednak unsigned stało się jeszcze wolniejsze ! Spadał od 26do 20 GB/s, zastępując w ten sposób zmienną stałą wartością, co prowadzi do deoptimizacji . Poważnie, nie mam pojęcia, co się tutaj dzieje! Ale teraz do clang++nowej wersji:

  • bez znaku 41959360000 0,677009 s 15,4884 GB / s
  • uint64_t 41959360000 0,676909 s 15,4906 GB / s

Czekaj, co? Teraz obie wersje spadły do wolnej liczby 15 GB / s. Tak więc zastąpienie zmiennej niestałej stałą wartością prowadzi nawet do spowolnienia kodu w obu przypadkach dla Clanga!

Poprosiłem kolegę z procesorem Ivy Bridge o opracowanie mojego testu porównawczego. Otrzymał podobne wyniki, więc nie wygląda na Haswella. Ponieważ dwa kompilatory dają tutaj dziwne wyniki, nie wydaje się, aby był to błąd kompilatora. Nie mamy tutaj procesora AMD, więc mogliśmy testować tylko z Intelem.

Więcej szaleństwa, proszę!

Weź pierwszy przykład (ten z atol(argv[1])) i umieść staticprzed zmienną, tj .:

static uint64_t size=atol(argv[1])<<20;

Oto moje wyniki w g ++:

  • bez znaku 41959360000 0.396728 sec 26,4306 GB / s
  • uint64_t 41959360000 0,509484 s 20,5811 GB / s

Tak, jeszcze jedna alternatywa . Nadal mamy szybkie 26 GB / s u32, ale udało nam się uzyskać u64co najmniej z 13 GB / s do wersji 20 GB / s! Na komputerze mojego kolegi u64wersja stała się jeszcze szybsza niż u32wersja, dając najszybszy wynik ze wszystkich. Niestety, to działa tylko na g++, clang++nie wydaje się, aby się tym przejmować static.

Moje pytanie

Czy możesz wyjaśnić te wyniki? Szczególnie:

  • Jak może istnieć taka różnica między u32i u64?
  • Jak zastąpienie zmiennej niestałej stałym rozmiarem bufora może powodować mniej optymalny kod ?
  • W jaki sposób wstawienie staticsłowa kluczowego może u64przyspieszyć pętlę? Nawet szybciej niż oryginalny kod na komputerze mojego kolegi!

Wiem, że optymalizacja to podchwytliwe terytorium, jednak nigdy nie myślałem, że tak małe zmiany mogą prowadzić do 100% różnicy w czasie wykonywania i że małe czynniki, takie jak stały rozmiar bufora, mogą znów całkowicie wymieszać wyniki. Oczywiście zawsze chcę mieć wersję, która jest w stanie obsłużyć 26 GB / s. Jedyny niezawodny sposób, jaki mogę wymyślić, to skopiować i wkleić zestaw dla tego przypadku i użyć zestawu wbudowanego. To jedyny sposób, aby pozbyć się kompilatorów, które wydają się szaleć z powodu drobnych zmian. Co myślisz? Czy istnieje inny sposób na niezawodne uzyskanie kodu o największej wydajności?

Demontaż

Oto demontaż różnych wyników:

Wersja 26 GB / s od g ++ / u32 / non-const bufsize :

0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af8

Wersja 13 GB / s od g ++ / u64 / non-const bufsize :

0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c00

Wersja 15 GB / s z clang ++ / u64 / non-const bufsize :

0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e50

Wersja 20 GB / s od g ++ / u32 i u64 / const bufsize :

0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a68

Wersja 15 GB / s z clang ++ / u32 & u64 / const bufsize :

0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0

Co ciekawe, najszybsza wersja (26 GB / s) jest również najdłuższa! Wydaje się, że jest to jedyne rozwiązanie, które wykorzystuje lea. Niektóre wersje używają jbdo skakania, inne używają jne. Ale poza tym wszystkie wersje wydają się porównywalne. Nie wiem, skąd mogłaby pochodzić 100% różnica w wydajności, ale nie jestem zbyt biegła w odszyfrowywaniu zestawu. Najwolniejsza wersja (13 GB / s) wygląda nawet bardzo krótko i dobrze. Czy ktoś może to wyjaśnić?

Zdobyta wiedza

Bez względu na to, jaka będzie odpowiedź na to pytanie; Dowiedziałem się, że w naprawdę gorących pętlach każdy szczegół może mieć znaczenie, nawet szczegóły, które nie wydają się mieć żadnego związku z gorącym kodem . Nigdy nie zastanawiałem się, jakiego typu użyć dla zmiennej pętli, ale jak widzisz, tak niewielka zmiana może mieć 100% różnicę! Nawet typ przechowywania bufora może mieć ogromną różnicę, jak widzieliśmy po wstawieniu staticsłowa kluczowego przed zmienną size! W przyszłości zawsze będę testować różne alternatywy dla różnych kompilatorów, pisząc naprawdę ciasne i gorące pętle, które są kluczowe dla wydajności systemu.

Ciekawe jest również to, że różnica w wydajności jest wciąż tak wysoka, chociaż już czterokrotnie rozwinąłem pętlę. Więc nawet po rozwinięciu możesz nadal zostać dotknięty poważnymi odchyleniami wydajności. Dość ciekawe.

lekobójczy
źródło
8
TAK WIELE KOMENTARZY! Możesz je wyświetlić na czacie, a nawet zostawić własne, jeśli chcesz, ale nie dodawaj więcej tutaj!
Shog9
3
Zobacz także GCC Issue 62011, False Data Dependency w instrukcji popcnt . Ktoś inny to zapewnił, ale wydaje się, że zaginął podczas porządków.
jww
Nie mogę powiedzieć, ale czy jest to jeden z deasemblacji wersji ze statycznym? Jeśli nie, czy możesz edytować post i dodać go?
Kelly S. French

Odpowiedzi:

1552

Culprit: fałszywa zależność danych (a kompilator nawet o tym nie wie)

W przypadku procesorów Sandy / Ivy Bridge i Haswell instrukcja:

popcnt  src, dest

wydaje się mieć fałszywą zależność od rejestru docelowego dest. Mimo że instrukcja tylko do niej zapisuje, destprzed wykonaniem będzie czekać, aż będzie gotowa. Ta fałszywa zależność jest (obecnie) udokumentowana przez firmę Intel jako erratum HSD146 (Haswell) i SKL029 (Skylake)

Skylake naprawił to dla lzcntitzcnt .
Naprawiono to w Cannon Lake (i Ice Lake) popcnt.
bsf/ bsrmają prawdziwą zależność wyjściową: wyjście niezmodyfikowane dla wejścia = 0. (Ale nie ma sposobu, aby skorzystać z tego w przypadku wewnętrznych rozwiązań - tylko AMD to dokumentuje, a kompilatory tego nie ujawniają.)

(Tak, te instrukcje działają na tej samej jednostce wykonawczej ).


Ta zależność nie tylko utrzymuje 4 popcnts od iteracji pojedynczej pętli. Może przenosić iteracje pętli, co uniemożliwia procesorowi równoległe wykonywanie różnych iteracji pętli.

unsignedVs. uint64_ti innych poprawek nie wpływają bezpośrednio na problem. Ale wpływają na alokator rejestru, który przypisuje rejestry do zmiennych.

W twoim przypadku prędkości są bezpośrednim wynikiem tego, co utknęło w (fałszywym) łańcuchu zależności w zależności od tego, co postanowił zrobić alokator rejestru.

  • 13 GB / s ma łańcuch: popcnt- add- popcnt- popcnt→ następna iteracja
  • 15 GB / s ma łańcuch: popcnt- add- popcnt-add → następna iteracja
  • 20 GB / s ma łańcuch: popcnt-popcnt → następna iteracja
  • 26 GB / s ma łańcuch: popcnt- popcnt→ następna iteracja

Różnica między 20 GB / si 26 GB / s wydaje się być niewielkim artefaktem adresowania pośredniego. Tak czy inaczej, procesor zaczyna napotykać inne wąskie gardła, gdy osiągniesz tę prędkość.


Aby to przetestować, użyłem zestawu wbudowanego, aby ominąć kompilator i uzyskać dokładnie taki zestaw, jaki chcę. Podzieliłem również countzmienną, aby przełamać wszystkie inne zależności, które mogą zepsuć się z testami porównawczymi.

Oto wyniki:

Sandy Bridge Xeon @ 3,5 GHz: (pełny kod testu można znaleźć na dole)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • Ubuntu 12

Różne rejestry: 18,6195 GB / s

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

Ten sam rejestr: 8,49272 GB / s

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

Ten sam rejestr z zerwanym łańcuchem: 17,8869 GB / s

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

Co poszło nie tak z kompilatorem?

Wygląda na to, że ani GCC, ani Visual Studio nie zdają sobie z tego sprawy popcnt tak fałszywej zależności. Niemniej jednak te fałszywe zależności nie są rzadkie. To tylko kwestia tego, czy kompilator jest tego świadomy.

popcntnie jest najczęściej używaną instrukcją. Nic więc dziwnego, że główny kompilator może przeoczyć coś takiego. Wydaje się również, że nigdzie nie ma dokumentacji, która wspomniałaby o tym problemie. Jeśli Intel tego nie ujawni, nikt na zewnątrz nie będzie wiedział, dopóki ktoś nie wpadnie na to przypadkiem.

( Aktualizacja: Począwszy od wersji 4.9.2 , GCC jest świadomy tej fałszywej zależności i generuje kod, aby zrekompensować ją, gdy włączone są optymalizacje. Główne kompilatory innych dostawców, w tym Clang, MSVC, a nawet ICC Intela nie są jeszcze świadomi ten mikroarchitekturalny erratum i nie będzie emitował kodu, który go kompensuje).

Dlaczego CPU ma tak fałszywą zależność?

Możemy spekulować: działa na tej samej jednostce wykonawczej jako bsf/ bsr, które zrobić mają zależność sygnału wyjściowego. (W jaki sposób POPCNT jest implementowany sprzętowo? ). W przypadku tych instrukcji Intel dokumentuje wynik liczb całkowitych dla input = 0 jako „niezdefiniowany” (przy ZF = 1), ale sprzęt Intel daje silniejszą gwarancję, aby uniknąć uszkodzenia starego oprogramowania: wyjście niezmodyfikowane. AMD dokumentuje to zachowanie.

Przypuszczalnie w pewien sposób niewygodne było uzależnienie niektórych poprawek dla tej jednostki wykonawczej od wyników, a inne nie.

Wydaje się, że procesory AMD nie mają tej fałszywej zależności.


Pełny kod testu znajduje się poniżej w celach informacyjnych:

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

Równie interesujący test porównawczy można znaleźć tutaj: http://pastebin.com/kbzgL8si
Ten test porównawczy różni liczbę popcnts, które znajdują się w (fałszywym) łańcuchu zależności.

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s
Tajemniczy
źródło
3
Cześć ludzie! Wiele poprzednich komentarzy tutaj; przed opuszczeniem nowego przejrzyj archiwum .
Shog9
1
@ JustinL.it wygląda na to, że ten konkretny problem został rozwiązany w Clang w wersji 7.0
Dan M.
@PeterCordes Nie sądzę, że jest to jednostka wykonawcza tak bardzo jak harmonogram. Jest to harmonogram, który śledzi zależności. Aby to zrobić, instrukcje są pogrupowane w szereg „klas instrukcji”, z których każda jest traktowana identycznie przez program planujący. Zatem wszystkie 3-cyklowe instrukcje „slow-int” zostały wrzucone do tej samej „klasy” w celu planowania instrukcji.
Mysticial
@Mysticial: Nadal tak myślisz? Jest to prawdopodobne, ale imul dst, src, immnie ma zależności wyjściowej i nie spowalnia lea. Nie robi tego pdep, ale jest to zakodowane w VEX za pomocą 2 argumentów wejściowych. Uzgodniliśmy, że to nie jest to jednostka wykonawcza sam , który powoduje fałszywe dep; to zależy od RAT i wydania / zmiany nazwy, ponieważ zmienia nazwy operandów rejestru architektonicznego na rejestry fizyczne. Przypuszczalnie potrzebuje tabeli uop-code -> wzorca zależności i wyborów portów, a grupowanie wszystkich uopsów dla tej samej jednostki wykonawczej razem upraszcza tę tabelę. Właśnie to miałem na myśli bardziej szczegółowo.
Peter Cordes
Daj mi znać, jeśli chcesz, żebym to zmienił w twojej odpowiedzi, lub jeśli chcesz przywrócić to do powiedzenia czegoś takiego, co pierwotnie powiedziałeś o harmonogramie. Fakt, że SKL porzucił false dep dla lzcnt / tzcnt, ale nie popcnt, powinien nam coś powiedzieć, ale IDK co. Innym możliwym znakiem, że jest to związane ze zmianą nazwy / RAT, jest to, że SKL odlaminuje indeksowany tryb adresowania jako źródło pamięci dla lzcnt / tzcnt, ale nie popcnt. Oczywiście jednostka zmiany nazwy musi tworzyć elementy, które może reprezentować back-end.
Peter Cordes
50

Zakodowałem równoważny program C do eksperymentu i mogę potwierdzić to dziwne zachowanie. Co więcej, gccuważa , że 64-bitowa liczba całkowita (która prawdopodobnie i size_ttak powinna być ...) jest lepsza, ponieważ użycie uint_fast32_tpowoduje, że gcc używa 64-bitowego uinta.

Zrobiłem trochę zabawy z montażem: po
prostu weź 32-bitową wersję, zamień wszystkie 32-bitowe instrukcje / rejestry na 64-bitową wersję w wewnętrznej pętli popcount programu. Uwaga: kod jest tak samo szybki jak wersja 32-bitowa!

To oczywiście hack, ponieważ rozmiar zmiennej nie jest tak naprawdę 64-bitowy, ponieważ inne części programu nadal używają wersji 32-bitowej, ale dopóki wewnętrzna pętla popcount dominuje w wydajności, jest to dobry początek .

Następnie skopiowałem kod wewnętrznej pętli z 32-bitowej wersji programu, zhakowałem go do wersji 64-bitowej, majstrowałem przy rejestrach, aby zastąpić wewnętrzną pętlę wersji 64-bitowej. Ten kod działa również tak szybko, jak wersja 32-bitowa.

Doszedłem do wniosku, że jest to zły harmonogram kompilowania instrukcji przez kompilator, a nie faktyczna przewaga szybkości / opóźnienia w przypadku instrukcji 32-bitowych.

(Uwaga: zhakowałem zgromadzenie, mogłem coś zepsuć bez zauważenia. Nie sądzę.)

EOF
źródło
1
„Co więcej, gcc uważa, że ​​64-bitowa liczba całkowita […] jest lepsza, ponieważ użycie uint_fast32_t powoduje, że gcc używa 64-bitowego uint.” Niestety, i żałuję, nie ma magii i głębokiej introspekcji kodu za tymi typami. Nie widziałem jeszcze, aby były udostępniane w inny sposób niż jako pojedyncze typy dla każdego możliwego miejsca i każdego programu na całej platformie. Prawdopodobnie zastanawiano się nad dokładnym wyborem typów, ale jedna definicja dla każdego z nich nie pasuje do każdej aplikacji, jaka kiedykolwiek będzie. Dalsze informacje: stackoverflow.com/q/4116297 .
Keno
2
@Keno To dlatego, że sizeof(uint_fast32_t)musi zostać zdefiniowane. Jeśli na to nie pozwalasz, możesz to zrobić, ale można to zrobić tylko przy pomocy rozszerzenia kompilatora.
wizzwizz4,
25

To nie jest odpowiedź, ale trudno jest przeczytać, jeśli umieszczę wyniki w komentarzu.

Otrzymuję te wyniki z komputerem Mac Pro ( Westmere 6-rdzeniowy Xeon 3,33 GHz). Skompilowałem to z clang -O3 -msse4 -lstdc++ a.cpp -o a(-O2 uzyskać ten sam wynik).

brzęknąć z uint64_t size=atol(argv[1])<<20;

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

brzęknąć z uint64_t size=1<<20;

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

Próbowałem także:

  1. Odwróć kolejność testu, wynik jest taki sam, więc wyklucza współczynnik pamięci podręcznej.
  2. Mieć foroświadczenie w odwrotnej kolejności: for (uint64_t i=size/8;i>0;i-=4). Daje to ten sam wynik i dowodzi, że kompilacja jest wystarczająco inteligentna, aby nie dzielić wielkości przez 8 podczas każdej iteracji (zgodnie z oczekiwaniami).

Oto moje dzikie przypuszczenie:

Współczynnik prędkości składa się z trzech części:

  • pamięć podręczna kodu: uint64_twersja ma większy rozmiar kodu, ale nie ma to wpływu na mój procesor Xeon. To powoduje, że wersja 64-bitowa działa wolniej.

  • Zastosowane instrukcje. Należy zwrócić uwagę nie tylko na liczbę pętli, ale dostęp do bufora można uzyskać za pomocą indeksu 32-bitowego i 64-bitowego w obu wersjach. Dostęp do wskaźnika z 64-bitowym przesunięciem wymaga dedykowanego 64-bitowego rejestru i adresowania, podczas gdy można użyć natychmiastowego dla 32-bitowego przesunięcia. Może to przyspieszyć wersję 32-bitową.

  • Instrukcje są emitowane tylko na kompilacji 64-bitowej (to znaczy, pobranie wstępne). To sprawia, że ​​64-bit jest szybszy.

Te trzy czynniki pasują do obserwowanych pozornie sprzecznych wyników.

Przerwanie niemaskowalne
źródło
4
Ciekawe, czy możesz dodać wersję kompilatora i flagi kompilatora? Najlepsze jest to, że na twoim komputerze wyniki są odwrócone, tzn. Użycie u64 jest szybsze . Do tej pory nigdy nie zastanawiałem się, jaki typ ma moja zmienna pętli, ale wydaje się, że następnym razem muszę pomyśleć dwa razy :).
gicicide
2
@gexicide: Nie nazwałbym skoku z 16.8201 do 16.8126, co czyni go „szybszym”.
user541686,
2
@Mehrdad: Skok mam na myśli, że jest to skok między, 12.9a 16.8więc unsignedtutaj jest szybszy. W moim unsigneduint64_t
teście sytuacja
@gexicide Czy zauważyłeś różnicę w adresowaniu bufora [i]?
Przerwanie niemaskowalne
@ Calvin: Nie, co masz na myśli?
gicicide
10

Nie mogę udzielić wiarygodnej odpowiedzi, ale przedstawiam przegląd prawdopodobnej przyczyny. To odniesienie pokazuje dość wyraźnie, że dla instrukcji w ciele pętli istnieje stosunek 3: 1 między opóźnieniem a przepustowością. Pokazuje także skutki wielokrotnej wysyłki. Ponieważ w nowoczesnych procesorach x86 istnieją (dają lub biorą) trzy jednostki całkowite, generalnie możliwe jest wysłanie trzech instrukcji na cykl.

Tak więc między szczytową wydajnością potoku a wydajnością wielu wysyłek i awarią tych mechanizmów mamy sześciokrotnie wyższą wydajność. Powszechnie wiadomo, że złożoność zestawu instrukcji x86 sprawia, że ​​dość dziwne jest pękanie. Powyższy dokument ma świetny przykład:

Wydajność Pentium 4 dla 64-bitowych prawych zmian jest naprawdę słaba. 64-bitowe przesunięcie w lewo, a także wszystkie 32-bitowe przesunięcia mają akceptowalną wydajność. Wygląda na to, że ścieżka danych od górnych 32 bitów do dolnych 32 bitów ALU nie jest dobrze zaprojektowana.

Osobiście wpadłem na dziwny przypadek, w którym gorąca pętla działała znacznie wolniej na konkretnym rdzeniu czterordzeniowego układu scalonego (AMD, o ile pamiętam). W rzeczywistości uzyskaliśmy lepszą wydajność w obliczeniach zmniejszania mapy poprzez wyłączenie tego rdzenia.

Zgaduję tutaj, że rywalizuję o jednostki całkowite: popcntliczniki pętli i obliczenia adresu mogą ledwo działać z pełną prędkością z licznikiem szerokim na 32 bity, ale licznik 64-bitowy powoduje rywalizację i utknięcie w potoku. Ponieważ w sumie jest tylko około 12 cykli, potencjalnie 4 cykle z wielokrotną wysyłką, na wykonanie korpusu pętli, pojedyncze przeciągnięcie może w rozsądny sposób wpłynąć na czas pracy 2 razy.

Zmiana wywołana przez użycie zmiennej statycznej, którą, jak sądzę, powoduje jedynie niewielkie zmiany kolejności instrukcji, to kolejna wskazówka, że ​​32-bitowy kod jest w punkcie krytycznym dla niezgody.

Wiem, że to nie jest rygorystyczna analiza, ale jest to wiarygodne wytłumaczenie.

Gen
źródło
2
Niestety od tego czasu (Core 2?) Praktycznie nie ma różnic w wydajności między 32-bitowymi i 64-bitowymi liczbami całkowitymi, z wyjątkiem mnożenia / dzielenia - które nie występują w tym kodzie.
Mysticial
@Gene: Pamiętaj, że wszystkie wersje przechowują rozmiar w rejestrze i nigdy nie odczytują go ze stosu w pętli. W związku z tym obliczanie adresu nie może odbywać się w miksie, a przynajmniej nie w pętli.
gicicide
@Gene: Rzeczywiście interesujące wyjaśnienie! Ale to nie wyjaśnia głównych punktów WTF: To, że 64-bitowy jest wolniejszy niż 32-bitowy z powodu przeciągnięć rurociągu, to jedno. Ale jeśli tak jest, czy wersja 64-bitowa nie powinna być niezawodnie wolniejsza od wersji 32-bitowej? Zamiast tego trzy różne kompilatory emitują wolny kod nawet dla wersji 32-bitowej, gdy używa się bufora o stałej długości kompilacji; zmiana rozmiaru bufora na statyczny ponownie całkowicie zmienia rzeczy. Był nawet przypadek na komputerze moich kolegów (i w odpowiedzi Calvina), w którym wersja 64-bitowa jest znacznie szybsza! Wydaje się to absolutnie nieprzewidywalne ..
zabójstwo
@Mysticial To moja uwaga. Nie ma szczytowej różnicy w wydajności, gdy występuje zerowa rywalizacja o IU, czas magistrali itp. Odnośnik wyraźnie to pokazuje. Spór sprawia, że ​​wszystko jest inne. Oto przykład z literatury Intel Core: „Jedną z nowych technologii zawartych w projekcie jest Macro-Ops Fusion, która łączy dwie instrukcje x86 w jedną mikrooperację. Na przykład wspólna sekwencja kodu, taka jak porównanie, po której następuje skok warunkowy stałby się pojedynczą mikrooperacją. Niestety ta technologia nie działa w trybie 64-bitowym. ” Mamy więc współczynnik wykonania 2: 1.
Gene
@gexicide Rozumiem, co mówisz, ale wnioskujesz więcej, niż miałem na myśli. Mówię, że kod, który działa najszybciej, utrzymuje pełny przepływ potoku i kolejki wysyłki. Ten stan jest kruchy. Niewielkie zmiany, takie jak dodanie 32 bitów do całkowitego przepływu danych i zmiana kolejności instrukcji są wystarczające, aby je przerwać. Krótko mówiąc, twierdzenie PO, że jedyne wyjście jest błahostki i testowanie, jest słuszne.
Gene
10

Próbowałem tego w programie Visual Studio 2013 Express , używając wskaźnika zamiast indeksu, co nieco przyspieszyło proces. Podejrzewam, że dzieje się tak, ponieważ adresowanie to offset + rejestr zamiast offset + rejestr + (rejestr << 3). Kod C ++.

   uint64_t* bfrend = buffer+(size/8);
   uint64_t* bfrptr;

// ...

   {
      startP = chrono::system_clock::now();
      count = 0;
      for (unsigned k = 0; k < 10000; k++){
         // Tight unrolled loop with uint64_t
         for (bfrptr = buffer; bfrptr < bfrend;){
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
         }
      }
      endP = chrono::system_clock::now();
      duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
           << (10000.0*size)/(duration) << " GB/s" << endl;
   }

kod zestawu: r10 = bfrptr, r15 = bfrend, rsi = liczba, rdi = bufor, r13 = k:

$LL5@main:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT $LN4@main
        npad    4
$LL2@main:
        mov     rax, QWORD PTR [r10+24]
        mov     rcx, QWORD PTR [r10+16]
        mov     r8, QWORD PTR [r10+8]
        mov     r9, QWORD PTR [r10]
        popcnt  rdx, rax
        popcnt  rax, rcx
        add     rdx, rax
        popcnt  rax, r8
        add     r10, 32
        add     rdx, rax
        popcnt  rax, r9
        add     rsi, rax
        add     rsi, rdx
        cmp     r10, r15
        jb      SHORT $LL2@main
$LN4@main:
        dec     r13
        jne     SHORT $LL5@main
rcgldr
źródło
9

Czy próbowałeś przejść? -funroll-loops -fprefetch-loop-arrays do GCC?

Otrzymuję następujące wyniki z tymi dodatkowymi optymalizacjami:

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s
Dangelov
źródło
3
Ale nadal twoje wyniki są całkowicie dziwne (najpierw szybciej podpisane, potem uint64_t szybciej), ponieważ rozwijanie nie rozwiązuje głównego problemu fałszywej zależności.
gicicide
7

Czy próbowałeś przenieść krok redukcji poza pętlę? W tej chwili masz zależność danych, która tak naprawdę nie jest potrzebna.

Próbować:

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];

Prowadzisz również dziwne aliasing, który nie jestem pewien, czy jest zgodny z surowymi zasadami aliasingu.

Ben Voigt
źródło
2
To była pierwsza rzecz, którą zrobiłem po przeczytaniu pytania. Przerwij łańcuch zależności. Jak się okazało różnica w wydajności się nie zmienia (przynajmniej na moim komputerze - Intel Haswell z GCC 4.7.3).
Nils Pipenbrinck
1
@BenVoigt: Jest zgodny z rygorystycznym aliasingiem. void*i char*są to dwa typy, które można aliasować, ponieważ są one zasadniczo uważane za „wskaźniki do jakiejś części pamięci”! Twój pomysł dotyczący usuwania zależności danych jest dobry do optymalizacji, ale nie odpowiada na pytanie. I, jak mówi @NilsPipenbrinck, wydaje się, że nic to nie zmienia.
gicicide
@gexicide: ścisła zasada aliasingu nie jest symetryczna. Możesz użyć, char*aby uzyskać dostęp do T[]. Nie możesz bezpiecznie użyć a, T*aby uzyskać dostęp do char[], a twój kod wydaje się robić to drugie.
Ben Voigt
@BenVoigt: W takim razie nigdy nie mógłbyś ocalić mallocniczego, ponieważ malloc powraca void*i interpretujesz to jako T[]. I jestem tego całkiem pewien void*i char*miałem taką samą semantykę dotyczącą ścisłego aliasingu. Wydaje mi się jednak, że jest to dość nie na temat :)
gexicide
1
Osobiście uważam, że właściwą drogą jestuint64_t* buffer = new uint64_t[size/8]; /* type is clearly uint64_t[] */ char* charbuffer=reinterpret_cast<char*>(buffer); /* aliasing a uint64_t[] with char* is safe */
Ben Voigt
6

TL; DR: __builtinZamiast tego użyj funkcji wewnętrznych; może zdarzyć się, że pomogą.

Byłem w stanie zmusić gcc4.8.4 (a nawet 4.7.3 na gcc.godbolt.org) do wygenerowania optymalnego kodu w tym celu, używając __builtin_popcountlltej samej instrukcji asemblera, ale mam szczęście i zdarza się, że tworzy kod, który nie ma nieoczekiwanie długa zależność od pętli z powodu błędu fałszywej zależności.

Nie jestem w 100% pewien swojego kodu porównawczego, ale objdumpwydaje się, że wyniki dzielą moje poglądy. Używam innych sztuczek ( ++ivs i++), aby kompilator rozwinął dla mnie pętlę bez żadnych movlinstrukcji (dziwne zachowanie, muszę powiedzieć).

Wyniki:

Count: 20318230000  Elapsed: 0.411156 seconds   Speed: 25.503118 GB/s

Kod porównawczy:

#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len){
  uint64_t cnt = 0;
  for(size_t i = 0; i < len; ++i){
    cnt += __builtin_popcountll(buf[i]);
  }
  return cnt;
}

int main(int argc, char** argv){
  if(argc != 2){
    printf("Usage: %s <buffer size in MB>\n", argv[0]);
    return -1;
  }
  uint64_t size = atol(argv[1]) << 20;
  uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer));

  // Spoil copy-on-write memory allocation on *nix
  for (size_t i = 0; i < (size / 8); i++) {
    buffer[i] = random();
  }
  uint64_t count = 0;
  clock_t tic = clock();
  for(size_t i = 0; i < 10000; ++i){
    count += builtin_popcnt(buffer, size/8);
  }
  clock_t toc = clock();
  printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC)));
  return 0;
}

Opcje kompilacji:

gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

Wersja GCC:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Wersja jądra Linux:

3.19.0-58-generic

Informacje o procesorze:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 70
model name  : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz
stepping    : 1
microcode   : 0xf
cpu MHz     : 2494.226
cache size  : 6144 KB
physical id : 0
siblings    : 1
core id     : 0
cpu cores   : 1
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt
bugs        :
bogomips    : 4988.45
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:
assp1r1n3
źródło
3
To szczęście, że -funroll-loopszdarza się tworzyć kod, który nie powoduje wąskiego gardła w łańcuchu zależności przenoszonym przez pętlę, utworzonym przez popcntfałszywe dep. Korzystanie ze starej wersji kompilatora, która nie wie o fałszywej zależności, stanowi ryzyko. Bez -funroll-loopstego pętla gcc 4.8.5 spowoduje wąskie gardło opóźnień popcnt zamiast przepustowości, ponieważ się liczyrdx . Ten sam kod, skompilowany przez gcc 4.9.3, dodaje xor edx,edxprzerwanie łańcucha zależności.
Peter Cordes
3
W przypadku starych kompilatorów kod nadal byłby podatny na dokładnie taką samą zmienność wydajności, jakiej doświadczył OP: pozornie trywialne zmiany mogą spowolnić działanie gcc, ponieważ nie miałoby pojęcia, że ​​spowoduje problem. Znalezienie czegoś, co dzieje się w jednym przypadku na starym kompilatorze, nie jest pytaniem.
Peter Cordes
2
Dla przypomnienia, x86intrin.h„s _mm_popcnt_*funkcje na GCC są przymusowo inlined obwoluty wokół__builtin_popcount* ; inlining powinien sprawić, że jeden będzie dokładnie taki sam jak drugi. Bardzo wątpię, czy zobaczysz jakąkolwiek różnicę, która mogłaby być spowodowana przełączaniem się między nimi.
ShadowRanger
-2

Przede wszystkim spróbuj oszacować szczytową wydajność - sprawdź https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf , w szczególności dodatek C.

W twoim przypadku jest to tabela C-10, która pokazuje, że instrukcja POPCNT ma opóźnienie = 3 zegary i przepustowość = 1 zegar. Przepustowość pokazuje maksymalną prędkość w zegarach (pomnóż przez częstotliwość rdzenia i 8 bajtów w przypadku popcnt64, aby uzyskać najlepszą możliwą liczbę pasm).

Teraz sprawdź, co zrobił kompilator i zsumuj przepustowości wszystkich innych instrukcji w pętli. To da najlepsze możliwe oszacowanie wygenerowanego kodu.

Na koniec spójrz na zależności danych między instrukcjami w pętli, ponieważ wymuszą duże opóźnienie zamiast przepustowości - więc podziel instrukcje pojedynczej iteracji w łańcuchach przepływu danych i oblicz opóźnienie na nich, a następnie naiwnie wybierz maksimum z nich. da przybliżone oszacowanie, biorąc pod uwagę zależności przepływu danych.

Jednak w twoim przypadku pisanie kodu we właściwy sposób wyeliminowałoby wszystkie te złożoności. Zamiast kumulować się do tej samej zmiennej zliczającej, po prostu kumuluj do różnych (takich jak count0, count1, ... count8) i zsumuj je na końcu. Lub nawet stwórz tablicę zliczeń [8] i kumuluj do jej elementów - być może nawet zostanie wektoryzowana i uzyskasz znacznie lepszą przepustowość.

PS i nigdy nie uruchamiaj testu przez sekundę, najpierw rozgrzej rdzeń, a następnie uruchom pętlę przez co najmniej 10 sekund lub lepiej 100 sekund. w przeciwnym razie przetestujesz sprzętowo oprogramowanie do zarządzania energią i implementację DVFS sprzętowo :)

PPS Słyszałem niekończące się debaty na temat tego, ile czasu naprawdę powinien potrwać test porównawczy. Większość najmądrzejszych ludzi pyta nawet, dlaczego 10 sekund a nie 11 lub 12. Muszę przyznać, że jest to śmieszne w teorii. W praktyce wystarczy przejść i uruchomić test porównawczy sto razy z rzędu i zapisać odchylenia. To jest zabawne. Większość ludzi zmienia źródło i biegnie po tym dokładnie RAZ, aby zdobyć nowy rekord wydajności. Rób właściwe rzeczy we właściwy sposób.

Nie jesteś jeszcze przekonany? Wystarczy użyć powyższej wersji testu porównawczego C autorstwa assp1r1n3 ( https://stackoverflow.com/a/37026212/9706746 ) i wypróbować 100 zamiast 10000 w pętli ponownych prób.

Moje programy 7960X z RETRY = 100:

Liczba: 203182300 Upłynęło: 0,008385 sekund Prędkość: 12,505379 GB / s

Liczba: 203182300 Upłynęło: 0,011063 sekundy Prędkość: 9,478225 GB / s

Liczba: 203182300 Upłynęło: 0,011188 sekund Prędkość: 9,372327 GB / s

Liczba: 203182300 Upłynęło: 0,010393 sekundy Prędkość: 10,089252 GB / s

Liczba: 203182300 Upłynęło: 0,009076 sekund Prędkość: 11,553283 GB / s

z RETRY = 10000:

Liczba: 20318230000 Upłynęło: 0,661791 sekund Prędkość: 15,844519 GB / s

Liczba: 20318230000 Upłynęło: 0,665422 sekundy Prędkość: 15,758060 GB / s

Liczba: 20318230000 Upłynęło: 0,660983 sekundy Prędkość: 15,863888 GB / s

Liczba: 20318230000 Upłynęło: 0,665337 sekund Prędkość: 15,760073 GB / s

Liczba: 20318230000 Upłynęło: 0,662138 sekund Prędkość: 15,836215 GB / s

PPPS Wreszcie na temat „zaakceptowanej odpowiedzi” i innych zagadek ;-)

Użyjmy odpowiedzi assp1r1n3 - ma on rdzeń 2,5 GHz. POPCNT ma 1 zegar, jego kod używa 64-bitowego popcnt. Tak więc matematyka to 2,5 GHz * 1 zegar * 8 bajtów = 20 GB / s dla jego konfiguracji. Widzi 25 Gb / s, być może z powodu zwiększenia turbo do około 3 GHz.

Przejdź zatem do ark.intel.com i poszukaj i7-4870HQ: https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70 -GHz-? Q = i7-4870HQ

Ten rdzeń może pracować do 3,7 Ghz, a rzeczywista maksymalna szybkość dla jego sprzętu wynosi 29,6 GB / s. Więc gdzie są kolejne 4 GB / s? Być może jest wydawany na logikę pętli i inny otaczający kod w każdej iteracji.

Teraz gdzie jest ta fałszywa zależność? sprzęt działa prawie w szczytowym tempie. Może moja matematyka jest zła, czasem się zdarza :)

PPPPPS Wciąż ludzie sugerujący erratę HW są winni, więc podążam za sugestią i stworzyłem przykładowy asm, patrz poniżej.

W moim 7960X pierwsza wersja (z pojedynczym wyjściem do cnt0) działa z prędkością 11 MB / s, druga wersja (z wyjściem do cnt0, cnt1, cnt2 i cnt3) działa z prędkością 33 MB / s. I można powiedzieć - voila! to zależność wyjściowa.

OK, może chodziło mi o to, że pisanie takiego kodu nie ma sensu i nie jest to problem zależności wyjściowej, ale generowanie głupiego kodu. Nie testujemy sprzętu, piszemy kod, aby uwolnić maksymalną wydajność. Można się spodziewać, że HW OOO zmieni nazwę i ukryje te „zależności wyjściowe”, ale, rany, po prostu rób właściwe rzeczy we właściwy sposób i nigdy nie spotkasz się z żadną tajemnicą.

uint64_t builtin_popcnt1a(const uint64_t* buf, size_t len) 
{
    uint64_t cnt0, cnt1, cnt2, cnt3;
    cnt0 = cnt1 = cnt2 = cnt3 = 0;
    uint64_t val = buf[0];
    #if 0
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0)
        : "q" (val)
        :
        );
    #else
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %5, %1\n\t"
            "popcnt %5, %2\n\t"
            "popcnt %5, %3\n\t"
            "popcnt %5, %4\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0), "=q" (cnt1), "=q" (cnt2), "=q" (cnt3)
        : "q" (val)
        :
        );
    #endif
    return cnt0;
}
Kovalex
źródło
Jeśli mierzysz czas w taktach rdzenia (zamiast sekund), 1 sekunda to dużo czasu na małą pętlę związaną z procesorem. Nawet 100 ms jest w porządku do znajdowania poważnych różnic lub sprawdzania liczników perf dla liczników dodatnich. Zwłaszcza na Skylake, gdzie sprzętowe zarządzanie stanem P pozwala na zwiększenie maksymalnej prędkości zegara w mikrosekundach po rozpoczęciu ładowania.
Peter Cordes
clang może automatycznie wektoryzować się __builtin_popcountlw AVX2 vpshufbi nie potrzebuje do tego wielu akumulatorów w źródle C. Nie jestem pewien _mm_popcnt_u64; który może automatycznie się wektoryzować tylko za pomocą AVX512-VPOPCNT. (Zobacz Liczenie 1 bitów (liczba populacji) na dużych danych przy użyciu AVX-512 lub AVX-2 /)
Peter Cordes
Ale tak czy inaczej, przeglądanie instrukcji optymalizacji Intela nie pomoże: jak pokazuje zaakceptowana odpowiedź, problemem jest nieoczekiwana zależność wyjściowa popcnt. Jest to udokumentowane w erracie Intela dla niektórych z ich ostatnich mikroarchitektur, ale myślę, że wtedy nie było. Twoja analiza łańcucha nie powiedzie się, jeśli wystąpią nieoczekiwane fałszywe zależności, więc ta odpowiedź jest dobrą ogólną radą, ale nie ma tutaj zastosowania.
Peter Cordes
1
Czy ty żartujesz? Nie muszę „wierzyć” w rzeczy, które mogę eksperymentalnie zmierzyć za pomocą liczników wydajności w ręcznie napisanej pętli asm. To tylko fakty. Przetestowałem i Skylake naprawił fałszywą zależność dla lzcnt/ tzcnt, ale nie dla popcnt. Zobacz Erratum SKL029 Intela w intel.com/content/dam/www/public/us/en/documents/... . Ponadto gcc.gnu.org/bugzilla/show_bug.cgi?id=62011 jest „rozwiązany naprawiony”, a nie „nieprawidłowy”. Nie ma podstaw do twierdzenia, że ​​w HW nie ma zależności wyjściowej.
Peter Cordes
1
Jeśli utworzysz prostą pętlę, taką jak popcnt eax, edx/ dec ecx / jnz, możesz oczekiwać, że będzie ona działać z prędkością 1 na zegar, z wąskim gardłem w zakresie przepustowości popcnt i przepustowości przejętej gałęzi. Ale tak naprawdę działa tylko z częstotliwością 1 na 3 zegary z wąskim gardłem w popcntprzypadku wielokrotnego nadpisywania EAX, nawet jeśli można oczekiwać, że będzie to tylko do zapisu. Masz Skylake, więc możesz spróbować sam.
Peter Cordes
-3

Ok, chcę udzielić krótkiej odpowiedzi na jedno z pytań cząstkowych zadanych przez PO, które wydają się nie zostać uwzględnione w istniejących pytaniach. Zastrzegam sobie, że nie przeprowadzałem żadnych testów ani generowania kodu ani dezasemblacji, chciałem tylko podzielić się przemyśleniami, które inni mogliby wyjaśnić.

Dlaczego staticzmiana wydajności?

Linia, o której mowa: uint64_t size = atol(argv[1])<<20;

Krótka odpowiedź

Chciałbym spojrzeć na zestaw wygenerowany dla uzyskania dostępu sizei sprawdzić, czy dla wersji niestatycznej występują dodatkowe etapy pośredniego wskaźnika.

Długa odpowiedź

Ponieważ istnieje tylko jedna kopia zmiennej, bez względu na to, czy została zadeklarowana, staticczy nie, a rozmiar się nie zmienia, teoretyzuję, że różnicą jest lokalizacja pamięci użytej do utworzenia kopii zmiennej wraz z miejscem jej użycia w kodzie na dół.

Ok, aby zacząć od oczywistości, pamiętaj, że wszystkie zmienne lokalne (wraz z parametrami) funkcji mają zapewnione miejsce na stosie do wykorzystania jako pamięć. Oczywiście rama stosu dla main () nigdy nie czyści się i jest generowana tylko raz. Ok, a co z tym zrobić static? Cóż, w takim przypadku kompilator wie, aby zarezerwować miejsce w globalnej przestrzeni danych procesu, więc lokalizacji nie można wyczyścić przez usunięcie ramki stosu. Ale wciąż mamy tylko jedną lokalizację, więc jaka jest różnica? Podejrzewam, że ma to związek ze sposobem odwoływania się do lokalizacji pamięci na stosie.

Gdy kompilator generuje tablicę symboli, po prostu wprowadza etykietę wraz z odpowiednimi atrybutami, takimi jak rozmiar itp. Wie, że musi zarezerwować odpowiednią przestrzeń w pamięci, ale w rzeczywistości nie wybiera tej lokalizacji, dopóki nie później proces po przeprowadzeniu analizy żywotności i ewentualnym przypisaniu rejestru. Skąd zatem linker wie, jaki adres podać w kodzie maszynowym dla kodu końcowego zestawu? Zna ostateczną lokalizację lub wie, jak do niej dotrzeć. W przypadku stosu odniesienie do jednego z dwóch elementów, wskaźnika do ramki stosu, a następnie przesunięcia w ramce jest dość proste. Jest to w zasadzie spowodowane tym, że linker nie może znać położenia ramki stosu przed uruchomieniem.

Kelly S. French
źródło
2
Wydaje mi się znacznie bardziej prawdopodobne, że użycie staticzmieniło przydział rejestru dla funkcji w sposób, który wpłynął na fałszywą zależność wyjściową popcntprocesorów Intel, na których testował OP, z kompilatorem, który nie wiedział, jak ich uniknąć. (Ponieważ ta dziura w wydajności procesorów Intela nie została jeszcze odkryta.) Kompilator może przechowywać staticzmienną lokalną w rejestrze, podobnie jak zmienna pamięci automatycznej, ale jeśli nie zoptymalizują założenia, że maindziała tylko raz, wpłynie to na code-gen (ponieważ wartość jest ustawiana tylko przez pierwsze wywołanie).
Peter Cordes
1
W każdym razie różnica wydajności między trybami adresowania [RIP + rel32]i ich [rsp + 42]adresowania jest w większości przypadków znikoma. cmp dword [RIP+rel32], immediatenie mogę mikro-połączyć w jedno obciążenie + cmp uop, ale nie sądzę, że to będzie czynnik. Jak powiedziałem, wewnątrz pętli i tak prawdopodobnie pozostaje w rejestrze, ale poprawienie C ++ może oznaczać różne wybory kompilatora.
Peter Cordes