fundición duplica a números enteros con el fin de ganar velocidad

Question

en Redis (http://code.google.com/p/redis) hay puntuaciones asociadas a los elementos, con el fin de tomar estos elementos ordenados. Estos puntajes son dobles, incluso si muchos usuarios realmente clasifican por enteros (por ejemplo, tiempos unix).

Cuando se guarda la base de datos, necesitamos escribir este disco de doble autorización. Esto es lo que se utiliza actualmente: condiciones

snprintf((char*)buf+1,sizeof(buf)-1,"%.17g",val); 

Además infinito y no-A-Number se comprueban con el fin de representar también presente en el archivo de base de datos final.

Desafortunadamente la conversión de un doble en la representación de cadena es bastante lenta. Si bien tenemos una función en Redis que convierte un entero en una representación de cadena de una manera mucho más rápida. Así que mi idea era verificar si un doble se puede convertir en un entero sin pérdida de datos, y luego usar la función para convertir el entero en una cadena si esto es cierto.

Para que esto proporcione una buena aceleración, por supuesto, la prueba para la "equivalencia" entera debe ser rápida. Así que utilicé un truco que probablemente sea un comportamiento indefinido, pero que funcionó muy bien en la práctica. Algo así:

double x = ... some value ... 
if (x == (double)((long long)x)) 
    use_the_fast_integer_function((long long)x); 
else 
    use_the_slow_snprintf(x); 

En mi razonamiento el doble de fundición superior convierte el doble en un tiempo, y luego de nuevo en un entero. Si el rango se ajusta, y no hay parte decimal, el número sobrevivirá a la conversión y será exactamente el mismo que el número inicial.

Como quería asegurarme de que esto no rompería las cosas en algún sistema, me uní a #c en freenode y recibí muchos insultos;) Así que ahora estoy intentando aquí.

¿Existe una forma estándar de hacer lo que estoy tratando de hacer sin salir de ANSI C? De lo contrario, ¿se supone que el código anterior funciona en todos los sistemas Posix a los que actualmente apunta Redis? Es decir, archs donde Linux/Mac OS X/* BSD/Solaris se están ejecutando nowaday?

Lo que puedo agregar para hacer que el código sea más correcto es una verificación explícita del rango del doble antes de probar el molde.

Gracias por cualquier ayuda.

Answer 1

Quizás alguna matemática de punto fijo a la antigua pueda ayudarlo. Si convertiste tu doble en un valor de punto fijo, aún obtendrás precisión decimal y convertirla en una cadena es tan fácil como con ints con la adición de una función de cambio único.

Otra idea sería rodar su propia función snprintf(). Hacer la conversión de doble a int es soportado de forma nativa por muchas unidades de FPU, por lo que debería ser muy rápido. Convertir eso en una cadena también es simple.

Solo algunas ideas aleatorias para usted.

Answer 2

No veo ningún problema con los moldes, siempre que x esté dentro del rango de largo. Tal vez deberías verificar la función modf() que separa un doble en su parte integral y fraccionaria. Luego puede agregar cheques contra (doble) LLONG_MIN y (doble) LLONG_MAX para la parte integral para asegurarse. Aunque puede haber dificultades con la precisión del doble.

Pero antes de hacer algo de esto, ¿se ha asegurado de que realmente es un cuello de botella midiendo su rendimiento? ¿Y el porcentaje de valores enteros es lo suficientemente alto como para marcar la diferencia?

Answer 3

El problema al hacer eso es que las comparaciones no funcionarán de la manera esperada. El hecho de que un valor de coma flotante sea menor que otro no significa que su representación como un número entero sea menor que la del otro. Además, veo que comparas uno de los (antiguos) valores dobles para la igualdad. Debido a errores de redondeo y representación en los bits de orden inferior, casi nunca desea hacer eso.

Si solo está buscando algún tipo de clave para hacer algo así como hash, probablemente funcione bien. Si realmente te importa qué valores realmente tienen mayor o menor valor, es una mala idea.

Answer 4

Su prueba está perfectamente bien (suponiendo que ya ha manejado por separado infinitos y NAN por este punto) - y es probablemente una de las pocas ocasiones anteriores cuando realmente no desea comparar los flotadores por la igualdad. No invoca un comportamiento indefinido: incluso si x está fuera del rango de long long, obtendrá un "resultado definido por la implementación", que está bien aquí.

El solo vuela en la sopa es que el cero negativo terminará como cero positivo (porque el cero negativo se compara con el cero positivo).