C++ firmato e unsigned int vs lunga velocità lungo

Question

Oggi, ho notato che la velocità delle diverse operazioni semplici bit a bit e aritmetiche differisce in maniera significativa tra int, unsigned, long long e unsigned long long sul mio pc a 64 bit.

In particolare, il seguente ciclo è circa il doppio più veloce per unsigned come per long long, che non mi aspettavo.

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

(codice completo here)

Questi sono i tempi (in secondi) (per g++ -O, -O2 e -O3):

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

Questi tempi sono molto costanti (cioè un 1% margine). Senza il flag -O, ognuno ha un ritardo di circa un secondo, ma le velocità relative sono le stesse.

C'è una ragione chiara per questo? La vettorizzazione potrebbe essere per i tipi a 32 bit, ma non riesco a vedere da dove proviene l'enorme differenza tra long long e unsigned long long. Alcune operazioni sono molto più lente su alcuni tipi che su altri, o è solo una cosa generale che i tipi a 64 bit sono più lenti (anche su architetture a 64 bit)?

Per chi è interessato, questo loop scorre su tutti i sottoinsiemi di {1,2,...,30} con esattamente 15 elementi. Questo viene fatto eseguendo il ciclo (in ordine) su tutti gli interi inferiori a 1<<30 con esattamente 15 bit impostati. Per il caso corrente, sono le iterazioni 155117520. Non conosco più la fonte di questo frammento, ma il post this spiega ancora.

Modifica

Sembra dal codice assembly che la divisione può essere fatta più velocemente quando il tipo non è firmato. Penso che abbia senso, perché non dobbiamo rendere conto del bit del segno.

Inoltre, le operazioni a 32 bit utilizzano movl e altri xxxl istruzioni, mentre le operazioni a 64 bit utilizzano movq e xxxq.

Edit 2

Dopo aver letto il post che ho linkato, ho deciso di usare la formula laggiù:

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

Questo viene eseguito in circa un terzo del tempo del codice postato sopra, e usa lo stesso tempo per tutti e quattro i tipi.

Answer 1

Il più lento operazione nel codice è

divisione

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

32-bit è significativamente più veloce di divisione a 64 bit. Ad esempio, su Ivy Bridge, l'IDIV a 32 bit impiega 19-26 clock mentre l'IDIV a 64 bit richiede una latenza di 28-103 clock.

La versione senza firma è anche più veloce di firmata poiché la divisione per 2 è un semplice spostamento di bit nel caso senza segno e non vi sono chiamate di espansione delle dimensioni (CDQ, CQO).

nel caso non firmato è semplice spostamento po 'mentre nel firmato

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