resta - ¿Cómo puedo fortalecer la división por 2 ^ n+1?
divisiones por dos cifras m16 (2)
Necesito realizar algunas divisiones de enteros en la ruta activa de mi código. Ya he determinado a través del perfilado y el recuento de ciclos que las divisiones de enteros me están costando. Espero que haya algo que pueda hacer para reducir las divisiones en algo más barato.
En este camino, estoy dividiendo por 2 ^ n + 1, donde n es variable. Esencialmente quiero optimizar esta función para eliminar 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, simplemente reemplazaría el div por un turno a la derecha por n. Si estuviera dividiendo por una constante, permitiría que la fuerza del compilador redujera esa división específica, probablemente convirtiéndola en una multiplicación y algunos cambios.
¿Existe una optimización similar que se aplique a 2 ^ n + 1?
Edición: aquí puede ser un entero arbitrario de 64 bits. n toma solo unos pocos valores entre 10 y, digamos, 25. Ciertamente puedo calcular algunos valores para cada n, pero no para a.
Puede reemplazar la división de enteros por una constante, por multiplicación (tamaño de las palabras en módulo) con un número mágico y un desplazamiento.
Los números mágicos se pueden calcular previamente para las constantes conocidas.
Dado que n no puede tomar muchos valores, por ejemplo, 0..31, es "fácil" pre-calcular estos números mágicos para todos los n y almacenarlo en una tabla con 32 elementos.
Página de Javascript para calcular los números mágicos.
Un buen compilador puede calcular los números mágicos y reemplazar la división entera por multiplicación y cambio si el divisor es constante en el momento de la compilación. Dependiendo de cómo esté estructurado el resto del código en torno al código crítico de rendimiento, podría usar trucos macro o 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 interruptor) , pero pondría más código en la región constante, de lo contrario, podría ser un intercambio que no valga la pena (la ramificación también puede costarle el rendimiento )
La descripción detallada junto con el código para calcular los números mágicos se pueden incluir en el libro "Hackers Delight" de Henry S. Warren, Jr. (¡ altamente recomendado debe tener libro! ) Pp. 180ff.
Enlace a Google Books para el capítulo correspondiente:
Ya que solo puedes cambiar un int tantos lugares, puedes poner todos esos casos en una elección de una de 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, que los compiladores normalmente reducirán a una serie de instrucciones de multiplicación / cambio / adición (como se mencionó en la pregunta). Consulte ¿El compilador de ac / c ++ optimiza las divisiones constantes por el poder de dos valores en turnos? para los diestros.