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

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.

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

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ę.)

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.

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.

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

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

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.

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:

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;
}

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.