División eficaz de un doble con una potencia de 2

Implemento una función de ruido coherente, y me sorprendió descubrir que usar ruido de gradiente (es decir, ruido de Perlin) es en realidad un poco más rápido que el ruido de valor. Profiling muestra que la razón de esto es la división necesaria para convertir el valor int azar en un doble de la gama de -1.0 a 1.0:División eficaz de un doble con una potencia de 2

static double noiseValueDouble(int seed, int x, int y, int z) { 
    return 1.0 - ((double)noiseValueInt(seed, x, y, z)/1073741824.0); 
}

ruido Gradiente requiere unos pocos multiplica más, pero debido a los usos de la tabla de gradiente precomputed el noiseValueInt directamente para calcular un índice en la tabla, y no requiere ninguna división. Entonces mi pregunta es, ¿cómo podría hacer que la división anterior sea más eficiente, considerando que la división es por un poder de 2 (2^30).

En teoría todo lo que tendría que hacer es restar 30 del exponente del doble, pero hacerlo por la fuerza bruta (es decir, la manipulación de bits) daría lugar a todo tipo de casos de esquina (INF, NAN, desbordamiento exponente, etc.) Una solución de ensamblaje x86 estaría bien.

Fuente

2012-01-19 zennehoy

¿Estás seguro de que importa tanto? El uso de manipulación de bits específica de la máquina no es portátil, e incluso puede afectar el rendimiento debido a problemas de almacenamiento en caché o programación ... –

@BasileStarynkevitch Eso es lo que quise decir con mi último párrafo. No quiero hacer la manipulación de bits asumiendo IEEE 754, pero estaría bien con una solución de ensamblaje específica para x86. – zennehoy

No me molestaré sobre eso. No ganarás mucho y podrías perder algo de rendimiento. –

Declarar una variable (o constante) con el valor inverso y multiplicar por ella, cambiando efectivamente la división de una multiplicación:

static const double div_2_pow_30 = 1.0/1073741824.0;

Otra forma (utilizando la propiedad de que el número es una potencia de 2) es modificar el exponente con operaciones de bits. Hacer eso hará que el código dependa de los dobles que se almacenen utilizando el estándar IEEE, que puede ser menos portátil.

Fuente

2012-01-19 13:28:49

Creo que el compilador ya hace esa optimización. –

Iba a decir que el compilador puede resolverlo, pero en realidad no, [podría conducir a diferentes resultados numéricos] (http://ridiculousfish.com/blog/posts/will-it-optimize.html) (a menos que use por ejemplo -ffast-math para gcc). – spraff

@spraff: en el caso de que el divisor tenga una potencia exacta de dos, y su recíproco no se desborde o desborde, el resultado siempre es el mismo. La mayoría de los compiladores son conscientes de esto y hacen esta optimización. –

No estoy seguro de que pueda confiar en los perfiles aquí. Para funciones más pequeñas y más rápidas, el efecto del propio código de perfil comienza a sesgar los resultados.

Run noiseValueDouble y la alternativa correspondiente en un bucle para obtener mejores números.

Un ensamblador x86 solución es una solución bit-jugueteando, es posible que también lo haga el bit de tocar el violín en C. Instrucciones rápida división de potencia de dos (desplazamientos de bit) sólo existen para los enteros.

Si realmente desea utilizar instrucciones especiales, MMX hacia arriba o algo así.

Fuente

2012-01-19 13:27:28 spraff

Sí, hice esto también. El efecto, mientras menos, todavía está allí. Para el ruido de gradiente, la llamada es 'grad (noiseValueInt (seed, x0, y0), x, y)', para ruido de valor, 'noiseValueDouble (seed, x0, y0)'. Aparte de eso, los dos algoritmos son idénticos. – zennehoy

he intentado compilar esta con gcc:

double divide(int i) { 
    return 1.0 - (double)i/1073741824.0; 
}

con -O3 se codifica como un FMULS -Manual, con -O3 -mfpmath=sse -march=core2 que utiliza el juego de instrucciones SSE-y lo codifica como MULSD. No tengo idea de cuál es el más rápido, pero la llamada a la función en sí misma es, probablemente, órdenes de magnitud más lenta que la división real.

Fuente

2012-01-19 14:04:03

puede modificar el exponente utilizar directamente las funciones frexp y ldexp. No estoy seguro si esto sería más rápido sin embargo.

Fuente

2012-01-19 15:08:13

División eficaz de un doble con una potencia de 2

Respuesta

Cuestiones relacionadas