¿Cómo puedo fuerza reducir la división en 2^n + 1?

Necesito realizar algunas divisiones enteras en la ruta caliente de mi código. Ya he determinado a través de perfiles y recuento cíclico que las divisiones enteras me están costando. Espero que haya algo que pueda hacer para reducir las divisiones en algo más económico.¿Cómo puedo fuerza reducir la división en 2^n + 1?

En esta ruta, estoy dividiendo por 2^n + 1, donde n es variable. Esencialmente Quiero optimizar esta función para quitar el operador de división:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    return a/((1 << n) + 1); 
}

Si estuviera dividiendo por 2^n, me basta con sustituir el div con un desplazamiento a la derecha por n. Si me estuviera dividiendo por una constante, dejaría que la fuerza del compilador reduzca esa división específica, probablemente convirtiéndola en una multiplicación y algunos cambios.

¿Hay una optimización similar que se aplique a 2^n + 1?

Editar: aquí puede ser un entero arbitrario de 64 bits. n toma solo unos pocos valores entre 10 y, digamos, 25. Ciertamente puedo calcular previamente algunos valores para cada n, pero no para a.

Fuente

2010-10-25 J.S.

¿Hay algunas restricciones en los valores de a y n? –

¿Cuál es el contexto en el que llamas a la función? – GManNickG

'return a/lookup [n];' –

Dado que sólo puede cambiar un int tantos lugares, puede poner todos los casos en una elección de una de las varias divisiones por una constante:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    // assuming a 32-bit architecture (making this work for 64-bits 
    // is left as an exercise for the reader): 
    switch (n) { 
     case 0: return a/((1 << 0) + 1); 
     case 1: return a/((1 << 1) + 1); 
     case 2: return a/((1 << 2) + 1); 

      // cases 3 through 30... 

     case 31: return a/((1 << 31) + 1); 
    } 
}

Así que ahora cada división es por una constante, lo cual los compiladores generalmente reducen a una serie de instrucciones de multiplicar/cambiar/agregar (como la pregunta mencionada). Ver Does a c/c++ compiler optimize constant divisions by power-of-two value into shifts? para deatils.

Fuente

2010-10-25 17:39:10

Interesante idea. Quizás pueda escribir este código, luego extraer los parámetros de reducción de resistencia en una tabla. –

Vale la pena intentarlo, pero estás intercambiando un salto impredecible contra la diferencia entre las instrucciones de cambio + división y la división equivalente de fuerza reducida. ¿Alguna idea cuando esa es una buena solución de compromiso? –

+ 1, tiene sentido; aunque es probable que desee comparar esto para confirmar que la indirección y/o las ramas condicionales necesarias para implementar 'switch()' son realmente más rápidas que la división entera ... –

Puede reemplazar la división de enteros por una constante, multiplicando (modulo wordsize) con un número mágico y un shift.

Los números mágicos se pueden calcular previamente para las constantes conocidas.

Dado que n no puede tomar muchos valores, p. 0..31 es "fácil" precalcular estos números mágicos para todo ny almacenarlos en una tabla con 32 elementos.

Javascript Page for calculating the magic numbers

Un buen compilador puede calcular los números mágicos y reemplazar la división entera por multiplicación y cambiar si el divisor es constante en tiempo de compilación. Dependiendo de cómo el resto del código esté estructurado en torno al código de rendimiento crítico, puede usar macro o trucos en línea para desenrollar todos los valores posibles de n y dejar que el compilador haga el trabajo de encontrar los números mágicos (similar a la respuesta con el cambiar, pero pondría más código en la región constante de lo contrario podría ser un tradeof no vale la pena - la ramificación puede costar el rendimiento también)

Descripción detallada junto con el código para calcular los números mágicos puede ser fondo en el Libro "Hackers Delight" por Henry S. Warren, Jr. (muy recomendable debe tener el libro!) pp. 180ff.

Enlace a Google Books en el mismo capítulo:

Chapter 10-9 Unsigned Division by Divisors >= 1

Fuente

2010-10-25 18:16:31

¿Cómo puedo fuerza reducir la división en 2^n + 1?

Respuesta

Cuestiones relacionadas