Ottimizzazione modulo ripetuto all'interno di un loop

Question

Ho questa dichiarazione nel mio programma c e voglio ottimizzare. Con l'ottimizzazione, in particolare, mi riferisco agli operatori bit a bit (ma ogni altro suggerimento va bene).

uint64_t h_one = hash[0]; 
uint64_t h_two = hash[1]; 
for (int i=0; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (h_one + i * h_two) % size; //suggest some optimization for this line. 
} 

Qualsiasi suggerimento sarà di grande aiuto.

Edit: A partire da ora size può essere qualsiasi int ma non è un problema e siamo in grado di arrotondare fino al prossimo primo (ma potrebbe non essere una potenza di due, come per valori più grandi della potenza di 2 aumenta rapidamente e porterà a molti sprechi di memoria)

h_two è un int a 64 bit (fondamentalmente un mandrino di 64 byte).

Answer 1

così essenzialmente si sta facendo

k_0 = h_1 mod s 
k_1 = h_1 + h_2 mod s = k_0 + h_2 mod s 
k_2 = h_1 + h_2 + h_2 mod s = k_1 + h_2 mod s 
.. 
k_n = k_(n-1) + h_2 mod s 

A seconda di overflow problemi (che non dovrebbe differire da quello originale se la dimensione è meno della metà di 2**64), questo potrebbe essere più veloce (meno facile da parallelizzare però):

uint64_t h_one = hash[0]; 
uint64_t h_two = hash[1]; 
k_hash[0] = h_one % size; 
for (int i=1; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (k_hash[i-1] + h_two) % size; 
} 

Nota esiste la possibilità che il compilatore sia già arrivato in questo modulo, a seconda dei flag di ottimizzazione che si utilizzano.

Ovviamente questo ha eliminato solo una moltiplicazione. Se si vuole eliminare o ridurre il modulo, credo che sulla base di h_two%size e h_1%size è possibile predeterminare i passi in cui si deve chiamare esplicitamente %size, qualcosa di simile:

uint64_t h_one = hash[0]%size; 
uint64_t h_two = hash[1]%size; 
k_hash[0] = h_one; 
step = (size-(h_one))/(h_two)-1; 
for (int i=1; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (k_hash[i-1] + h_two); 
    if(i==step) 
    { 
     k_hash[i] %= size; 
    } 
} 

Nota Non sono sicuro del formula (non testarlo), è più un'idea generale. Ciò dipenderebbe in gran parte da quanto è buona la tua previsione di branca (e quanto è grande una prestazione - ha colpito una misprediction). Inoltre, è molto probabile che aiuti se il passo è grande.

edit: o più semplice (e probabilmente con le stesse prestazioni) -Grazie al mistico:

uint64_t h_one = hash[0]%size; 
uint64_t h_two = hash[1]%size; 
k_hash[0] = h_one; 
for (int i=1; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (k_hash[i-1] + h_two); 
    if(k_hash[i] > size) 
    { 
     k_hash[i] -= size; 
    } 
} 

Answer 2

Se la dimensione è una potenza di due, quindi l'applicazione di un bit a bit AND per dimensioni - 1 ottimizza "dimensione%":

(uint64_t *)k_hash[i] = (h_one + i * h_two) & (size - 1)