Optimizar el módulo repetido dentro de un bucle

Tengo esta declaración en mi programa c y quiero optimizarla. Por optimización, particularmente quiero referirme a operadores bit a bit (pero cualquier otra sugerencia también está bien).Optimizar el módulo repetido dentro de un bucle

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

Cualquier sugerencia será de gran ayuda.

Editar: A partir de ahora size puede haber ningún int pero no es un problema y podemos redondear hasta el próximo primer (pero puede no ser una potencia de dos que para valores más grandes del poder de 2 aumenta rápidamente y dará lugar a mucho desperdicio de memoria)

h_two es un 64 bit int (básicamente un plato de 64 bytes).

Fuente

2012-06-15 Aman Deep Gautam

¿Conoce usted algo de 'size'? – Mysticial

He editado la pregunta para aclarar algunas cosas, ya que exigió –

Existen métodos que hacen que las divisiones/módulos repetidos sobre el mismo número sean muy eficientes. Pero no es trivial. – Mysticial

tan esencialmente que estás haciendo

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

Dependiendo de desbordamiento problemas (que no deberían diferir del original si el tamaño es menor que la mitad de 2**64), esto podría ser más rápido (menos fácil de paralelizar):

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

Tenga en cuenta que existe la posibilidad de que su compilador ya haya llegado a este formulario, dependiendo de los indicadores de optimización que utilice.

Por supuesto, esto solo eliminó una multiplicación. Si desea eliminar o reducir el módulo, supongo que en base a h_two%size y h_1%size se puede predeterminar los pasos donde hay que llamar explícitamente %size, algo como esto:

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 No estoy seguro de la fórmula (no lo probó), es más una idea general. Esto dependería en gran medida de qué tan buena sea la predicción de sucursal (y de cuán grande sea el rendimiento: una predicción errónea). También es probable que ayude si el paso es grande.

edición: o más simple (y probablemente con el mismo rendimiento) -gracias a la mística:

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

Fuente

2012-06-15 20:17:26 KillianDS

+1 Es posible eliminar completamente el módulo en tu primer acercamiento si puedes probar que 'k_hash [i-1] + h_two' nunca desbordará el número entero. Pero viendo como es un hash, voy a suponer que los números son bastante aleatorios. – Mysticial

@Mysticial 'size' era un int y el resto son uint_64, por lo que no deberían desbordarse (h_two, por supuesto, puede prerreducirse) – harold

@harold, parece que tenemos una solución. Precompute 'h_two% size' y comience con' h_one% size'. Luego, en cada iteración, agréguela a un acumulador. Luego use una instrucción if para probar si es mayor que 'size' y reste si es necesario. – Mysticial

Si el tamaño es una potencia de dos, a continuación, aplicar una función Y al tamaño - 1 optimiza "tamaño%":

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

Fuente

2012-06-15 19:37:59

haciendo 'size' una potencia de 2 es demasiado pedir, pero podemos tenerlo como primo así que puedes sugerir algo en ese caso –

Optimizar el módulo repetido dentro de un bucle

Respuesta

Cuestiones relacionadas