C++ podpisane i unsigned long long int vs prędkości

Question

Dziś zauważyłem, że prędkość z kilku prostych operacji arytmetycznych bitowe i różni się znacznie pomiędzy int, unsigned, long long i unsigned long long na moim 64-bitowym komputerze.

W szczególności następująca pętla jest około dwa razy szybsza dla unsigned niż dla long long, czego się nie spodziewałem.

int k = 15; 
int N = 30; 
int mask = (1 << k) - 1; 
while (!(mask & 1 << N)) { 
    int lo = mask & ~(mask - 1); 
    int lz = (mask + lo) & ~mask; 
    mask |= lz; 
    mask &= ~(lz - 1); 
    mask |= (lz/lo/2) - 1; 
} 

(pełny kod here)

Oto czasy (w sekundach) (dla g++ -O, -O2 i -O3):

1.834207723 (int) 
3.054731598 (long long) 
1.584846237 (unsigned) 
2.201142018 (unsigned long long) 

Te czasy są bardzo zgodne (to znaczy 1% margines). Bez flagi -O każda z nich jest wolniejsza o jedną sekundę, ale prędkości względne są takie same.

Czy istnieje ku temu wyraźny powód? Wektoryzacja może być dla typów 32-bitowych, ale nie widzę, skąd pochodzi ogromna różnica między long long i unsigned long long. Czy niektóre operacje są znacznie wolniejsze w przypadku niektórych typów niż w przypadku innych, lub czy ogólnie rzecz biorąc, typy 64-bitowe są wolniejsze (nawet w architekturach 64-bitowych)?

Dla zainteresowanych ta pętla wykonuje pętle nad wszystkimi podzbiorami {1,2,...,30} z dokładnie 15 elementami. Odbywa się to poprzez zapętlenie (w kolejności) wszystkich liczb całkowitych mniejszych niż 1<<30 z dokładnie 15 bitami ustawionymi. Dla bieżącego przypadku jest to iteracja 155117520. Nie znam już źródła tego fragmentu, ale wpis this wyjaśnia więcej.

Edit

Wydaje się od kodu montażowej, że podział może być wykonane szybciej, gdy typ jest niepodpisany. Myślę, że ma to sens, ponieważ nie musimy uwzględniać bitu znaku.

Ponadto operacje 32-bitowe użyciu movl i inne xxxl instrukcji, podczas operacji 64-bitowych używa movq i xxxq.

Edycja 2

Po przeczytaniu postu połączonego, postanowiłem skorzystać z wzoru podanego tam:

T k = 15; 
T N = 30; 
T mask = (1 << k) - 1; 
while (!(mask & 1 << N)) { 
    T t = mask | (mask - 1); 
    mask = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(mask) + 1)); 
} 

To działa w około jednej trzeciej czasu kodu zamieszczonych powyżej, używa tego samego czasu dla wszystkich czterech typów.

Answer 1

Najwolniejszym operacja w kodzie jest

mask |= (lz/lo/2) - 1 

32-bitowy podział jest znacznie szybciej niż 64-bitowy podział. Na przykład na Ivy Bridge 32-bitowy IDIV zajmuje 19-26 zegarów, podczas gdy 64-bitowy IDIV wymaga 28-103 taktowania.

Niepodpisana wersja jest również szybsza niż podpisana, ponieważ dzielenie przez 2 to proste przesunięcie bitowe w niepodpisanym przypadku i nie ma wywołań rozszerzenia rozmiaru (CDQ, CQO).

w unsigned przypadku jest prosty bit shift natomiast w podpisanej

[1] http://www.agner.org/optimize/instruction_tables.pdf