2012-06-15 4 views
6

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).Ottimizzazione modulo ripetuto all'interno di un loop

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

+0

Sai niente di 'size'? – Mysticial

+0

Ho modificato la domanda per chiarire alcune cose come richiesto –

+1

Esistono metodi là fuori che rendono ripetute divisioni/modulo sullo stesso numero molto efficienti. Ma non è banale. – Mysticial

risposta

4

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

+1 In realtà è possibile rimuovere completamente il modulo nel tuo primo approccio se puoi provare che 'k_hash [i-1] + h_two' non eccederà mai il numero intero. Ma visto che è un hash, assumerò che i numeri siano piuttosto casuali. – Mysticial

+0

@Mysticial 'size' era un int però, e il resto è uint_64, quindi non dovrebbero overflow (h_two può ovviamente essere pre-ridotto) – harold

+2

@harold, sembra che abbiamo una soluzione. Precarica 'h_two% size' e inizia con 'h_one% size'. Quindi ad ogni iterazione, aggiungilo a un accumulatore. Quindi usa un'istruzione if per verificare se è maggiore di 'size' e sottrarre se necessario. – Mysticial

0

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) 
+0

rendere 'size' una potenza di 2 è troppo da chiedere ma possiamo averlo come un ottimo quindi puoi suggerire qualcosa in quel caso –