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 testOto 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 testWynik: 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
u32iu64? - 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żeu64przyspieszyć 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 0x400af8Wersja 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 0x400c00Wersja 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 0x400e50Wersja 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 0x400a68Wersja 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 0x400dd0Co 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.