Evitar llamadas a floor()

Question

Estoy trabajando en un fragmento de código donde tengo que tratar con uvs (coordenadas de textura 2D) que no están necesariamente en el rango de 0 a 1. Como ejemplo, a veces obtendré un uv con un componente u que es 1.2. Para manejar esto yo estoy poniendo en práctica un envoltorio que hace que el embaldosado de la siguiente manera:

u -= floor(u) 
v -= floor(v) 

Hacer esto provoca 1,2 a 0,2, que es convertido en el resultado deseado. También maneja casos negativos, como -0.4 convirtiéndose en 0.6.

Sin embargo, estas llamadas al piso son bastante lentas. He perfilado mi aplicación con Intel VTune y estoy gastando una gran cantidad de ciclos simplemente haciendo esta operación en el piso.

Después de haber leído algunos antecedentes sobre el tema, se me ocurrió la siguiente función, que es un poco más rápida pero aún deja mucho que desear (todavía estoy incurriendo en penalizaciones por conversión de tipo, etc.).

int inline fasterfloor(const float x) { return x > 0 ? (int) x : (int) x - 1; } 

he visto algunos trucos que se realizan con ensamblador en línea, pero nada de lo que parece funcionar exactamente correcto o tiene alguna mejora significativa de velocidad.

¿Alguien sabe algún truco para manejar este tipo de situaciones?

Answer 1

¿Cuál es el rango máximo de entrada de sus valores u, v? Si se trata de un rango bastante pequeño, p. -5.0 a +5.0, entonces será más rápido agregar/restar 1.0 repetidamente hasta que esté dentro del rango, en lugar de llamar a funciones costosas como el piso.

Answer 2

Si el rango de valores que puede aparecer es suficientemente pequeño, quizás pueda buscar binariamente el valor mínimo. Por ejemplo, si los valores de -2 < = x 2 < pueden ocurrir ...

if (u < 0.0) 
{ 
    if (u < 1.0) 
    { 
    // floor is 0 
    } 
    else 
    { 
    // floor is 1 
    } 
} 
else 
{ 
    if (u < -1.0) 
    { 
    // floor is -2 
    } 
    else 
    { 
    // floor is -1 
    } 
} 

que no ofrecen ninguna garantía sobre esto - no sé cómo la eficiencia de las comparaciones se compara con el piso - pero puede valer la pena molesto.

Answer 3

Otra tonta idea de que podría funcionar si el rango es pequeño ...

Extracto del exponente del flotador mediante operaciones bit a bit, entonces utilizar una tabla de búsqueda para encontrar una máscara que elimina los bits no deseados de la mantisa. Use esto para encontrar el piso (limpie los bits debajo del punto) para evitar problemas de renormalización.

EDIT Lo eliminé como "demasiado tonto, más con un problema + ve vs. -ve". Dado que se subió de todos modos, no se borró y dejaré que otros decidan qué tonto es.

Answer 4

Si está usando Visual C++, verifique la configuración del compilador "Habilitar funciones intrínsecas". Si está habilitado, debería hacer que la mayoría de las funciones matemáticas sean más rápidas (incluido el piso). Lo malo es que el manejo de casos extremos (como NaN) podría ser incorrecto, pero para un juego, es posible que no te importe.

Answer 5

la operación que desea se puede expresar mediante la función HOQF (fmodf de flotadores en lugar de dobles):

#include <math.h> 
u = fmodf(u, 1.0f); 

Lo más probable es razonablemente bueno que su compilador hacer esto de la manera más eficiente que trabaja.

De manera alternativa, ¿qué tan preocupado está con respecto a la precisión de último minuto?¿Puedes poner un límite inferior en tus valores negativos, como algo sabiendo que nunca están por debajo de -16.0? Si es así, algo como esto le ahorrará un condicional, que es bastante probable que sea útil si no es algo que pueda ser fiable ramificar-predijo con sus datos:

u = (u + 16.0); // Does not affect fractional part aside from roundoff errors. 
u -= (int)u;  // Recovers fractional part if positive. 

(Para el caso, en función de lo que su se parece a los datos y al procesador que está utilizando, si una gran parte de ellos son negativos pero una fracción muy pequeña está por debajo de 16.0, puede encontrar que agregar 16.0f antes de realizar su conversión condicional interna le da una aceleración porque hace que su condicional predecible. O su compilador puede estar haciendo eso con algo distinto de una rama condicional en cuyo caso no es útil; es difícil de decir sin probar y mirando ensamblado generado.)

Answer 6

S o quieres una conversión float-> int realmente rápida? La conversión AFAIK int-> float es rápida, pero al menos en MSVC++ una conversión float-> int invoca una pequeña función auxiliar, ftol(), que hace algunas cosas complicadas para asegurar que se realice una conversión compatible con los estándares. Si no necesita una conversión tan estricta, puede realizar hackers de ensamblaje, suponiendo que está en una CPU compatible con x86.

Aquí es una función para un int flotador-a-rápido que se redondea hacia abajo, usando MSVC sintaxis de ensamblador en línea ++ (que debe darle la idea correcta de todos modos):

inline int ftoi_fast(float f) 
{ 
    int i; 

    __asm 
    { 
     fld f 
     fistp i 
    } 

    return i; 
} 

En MSVC++ de 64 bits se le necesita un archivo .asm externo ya que el compilador de 64 bits rechaza el ensamblaje en línea. Esa función básicamente utiliza las instrucciones de FPU en bruto x87 para flotación de carga (fld) y luego almacena float como entero (fistp). (Nota de advertencia: puede cambiar el modo de redondeo utilizado aquí ajustando directamente los registros en la CPU, pero no haga eso, romperá muchas cosas, incluida la implementación de MSVC de sin y cos!)

Si se puede suponer soporte SSE en la CPU (o hay una manera fácil de hacer un código base SSE-apoyo) también puede probar:

#include <emmintrin.h> 

inline int ftoi_sse1(float f) 
{ 
    return _mm_cvtt_ss2si(_mm_load_ss(&f));  // SSE1 instructions for float->int 
} 

... que es básicamente el mismo (float carga luego almacena como entero) pero usando instrucciones SSE, que son un poco más rápidas.

Uno de ellos debe cubrir el costoso caso de float a int, y cualquier conversión int-to-float aún debería ser barata. Lamento ser específico de Microsoft aquí, pero aquí es donde he hecho un trabajo de rendimiento similar y obtuve grandes ganancias de esta manera. Si la portabilidad/otros compiladores son un problema, tendrá que buscar otra cosa, pero estas funciones compilan tal vez dos instrucciones que toman < 5 relojes, a diferencia de una función auxiliar que toma más de 100 relojes.

Answer 7

éste no resuelve el coste de lanzamiento, pero debe ser matemáticamente correcta:

int inline fasterfloor(const float x) { return x < 0 ? (int) x == x ? (int) x : (int) x -1 : (int) x; } 

Answer 8

Si se recorre y el uso de u y v como coordenadas de índice, en lugar de suelo que un flotador para obtener las coordenadas, mantener tanto un flotante como int del mismo valor e incrementándolos juntos. Esto le dará un número entero correspondiente para usar cuando sea necesario.

Answer 9

Pregunta anterior, pero me encontré con ella y me hizo convulsionar ligeramente que no se ha respondido satisfactoriamente.

TL; DR: * ¡No ** utilice el ensamblaje en línea, intrínsecos ni ninguna de las soluciones dadas para esto! En su lugar, compile con optimizaciones matemáticas rápidas/inseguras ("-ffast-math -funsafe-math-optimizations -fno-math-errno" en g ++).El motivo por el que floor() es tan lento es porque cambia el estado global si el molde se desborda (FLT_MAX no cabe en un tipo entero escalar de cualquier tamaño), lo que también hace imposible vectorizar a menos que deshabilite la compatibilidad estricta IEEE-754 , de lo cual probablemente no deberías depender. La compilación con estos indicadores desactiva el comportamiento problemático.

Algunas observaciones:

1. ensamblado en línea con los registros escalares no es vectorizable, que inhibe drásticamente el rendimiento al compilar con optimizaciones. También requiere que cualquier valor relevante actualmente almacenado en los registros vectoriales se derrame en la pila y se vuelva a cargar en los registros escalares, lo que frustra el propósito de la optimización manual.

2. El ensamblaje en línea utilizando el cvttss2si SSE con el método que ha descrito es realmente más lento en mi máquina que un simple ciclo con optimizaciones del compilador. Esto es probable porque su compilador asignará registros y evitará paradas de canalización mejor si permite que vectorice bloques enteros de código juntos. Para un código corto como este con pocas cadenas dependientes internas y casi ninguna posibilidad de derrame de registros, tiene muy pocas posibilidades de hacerlo peor que el código optimizado a mano rodeado de asm().

3. El ensamblaje en línea no es compatible, no es compatible con las versiones de Visual Studio de 64 bits y es increíblemente difícil de leer. Los intrínsecos sufren las mismas advertencias y las mencionadas anteriormente.

4. Todas las otras formas enumeradas son simplemente incorrectas, lo cual es posiblemente peor que la lentitud, y dan en cada caso una mejora de rendimiento tan marginal que no justifica la aspereza del enfoque. (int) (x + 16.0) -16.0 es tan malo que ni siquiera lo tocaré, pero tu método también es incorrecto porque da el piso (-1) como -2. También es una muy mala idea incluir ramas en el código de matemáticas cuando es tan crítico para el rendimiento que la biblioteca estándar no hará el trabajo por usted. Por lo tanto, su forma (incorrecta) debería parecerse más a ((int) x) - (x < 0.0), quizás con un intermedio, por lo que no tiene que realizar el movimiento fpu dos veces. Las sucursales pueden causar una falta de caché, lo que negará por completo cualquier aumento en el rendimiento; Además, si math errno está deshabilitado, fundir en int es el mayor cuello de botella restante de cualquier implementación de floor(). Si realmente/no te importa obtener valores correctos para enteros negativos, puede ser una aproximación razonable, pero no me arriesgaría a menos que conozcas muy bien tu caso de uso.

5. Intenté utilizar la conversión y el redondeo bit a bit, como lo que hace la implementación newlib de SUN en fmodf, pero tardó mucho tiempo en hacerlo bien y fue varias veces más lenta en mi máquina, incluso sin el compilador relevante banderas de optimización. Muy probablemente, escribieron ese código para alguna antigua CPU donde las operaciones de coma flotante eran comparativamente muy caras y no había extensiones de vectores, y mucho menos operaciones de conversión de vectores; esto ya no es el caso en cualquier arquitectura común AFAIK. SUN es también el lugar de nacimiento de la rutina inversa rápida sqrt() utilizada por Quake 3; ahora hay una instrucción para eso en la mayoría de las arquitecturas. Una de las mayores trampas de las micro-optimizaciones es que se vuelven obsoletas rápidamente.