ejecucion - aplicaciones que dañan el celular

¿Por qué el piso() es tan lento?

Question

Recientemente escribí algunos códigos (ISO / ANSI C) y me sorprendió el bajo rendimiento que logró. Para resumir, resultó que el culpable era la función floor() . No solo fue lento, sino que no vectorizó (con el compilador Intel, también conocido como ICL).

Aquí hay algunos puntos de referencia para realizar piso para todas las celdas en una matriz 2D:

VC:  0.10
ICL: 0.20

Compara eso con un simple elenco:

VC:  0.04
ICL: 0.04

¿Cómo puede floor() ser mucho más lento que un simple elenco? Hace esencialmente lo mismo (aparte de los números negativos). 2da pregunta: ¿Alguien sabe de una implementación súper rápida de floor() ?

PD: Aquí está el ciclo que yo estaba evaluando:

void Floor(float *matA, int *intA, const int height, const int width, const int width_aligned)
{
    float *rowA=NULL;
    int   *intRowA=NULL;
    int   row, col;

    for(row=0 ; row<height ; ++row){
        rowA = matA + row*width_aligned;
        intRowA = intA + row*width_aligned;
#pragma ivdep
        for(col=0 ; col<width; ++col){
            /*intRowA[col] = floor(rowA[col]);*/
            intRowA[col] = (int)(rowA[col]);
        }
    }
}

Answer 1

1. Ellos no hacen lo mismo. floor () es una función. Por lo tanto, al utilizarlo se genera una llamada a la función, se asigna un marco de pila, se copian los parámetros y se recupera el resultado. Casting no es una llamada de función, por lo que utiliza mecanismos más rápidos (creo que puede usar registros para procesar los valores).
2. Probablemente piso () ya está optimizado.
3. ¿Puedes sacar más rendimiento de tu algoritmo? Tal vez cambiar las filas y columnas puede ayudar? ¿Puedes almacenar en caché los valores comunes? ¿Están todas las optimizaciones del compilador activadas? ¿Puedes cambiar un sistema operativo? un compilador? Programación Perlas de Jon Bentley tiene una gran revisión de posibles optimizaciones.

Answer 2

Piso y techo sin ramificaciones (mejor utilizar la pipilina) sin verificación de errores

int f(double x)
{
    return (int) x - (x < (int) x); // as dgobbi above, needs less than for floor
}

int c(double x)
{
    return (int) x + (x > (int) x);
}

o usando piso

int c(double x)
{
    return -(f(-x));
}

Answer 3

Sí, floor() es extremadamente lento en todas las plataformas, ya que tiene que implementar un gran comportamiento a partir de la especificación IEEE fp. Realmente no puedes usarlo en los bucles internos.

Algunas veces uso una macro para aproximarme al piso ():

#define PSEUDO_FLOOR( V ) ((V) >= 0 ? (int)(V) : (int)((V) - 1))

No se comporta exactamente como floor() : por ejemplo, floor(-1) == -1 pero PSEUDO_FLOOR(-1) == -2 , pero está lo suficientemente cerca para la mayoría de los usos.

Answer 4

Si va a convertir el resultado de la operación floor() en un int, y si no le preocupa el desbordamiento, entonces el siguiente código es mucho más rápido que (int)floor(x) :

inline int int_floor(double x)
{
  int i = (int)x; /* truncate */
  return i - ( i > x ); /* convert trunc to floor */
}

Answer 5

Un par de cosas hacen que el suelo sea más lento que un yeso y evitan la vectorización.

El más importante:

el piso puede modificar el estado global. Si pasa un valor que es demasiado grande para representarse como un entero en formato flotante, la variable errno se establece en EDOM . También se hace un manejo especial para NaNs. Todo este comportamiento es para aplicaciones que desean detectar el caso de desbordamiento y manejar la situación de alguna manera (no me pregunten cómo).

La detección de estas condiciones problemáticas no es simple y representa más del 90% del tiempo de ejecución del piso. El redondeo real es barato y podría estar en línea / vectorizado. También es una gran cantidad de código, por lo que al poner en línea toda la función de piso haría que tu programa funcione más despacio.

Algunos compiladores tienen indicadores de compilación especiales que permiten al compilador optimizar algunas de las reglas c-estándar raramente utilizadas. Por ejemplo, a GCC se le puede decir que no le interesa errno en absoluto. Para hacerlo, pase -fno-math-errno o -ffast-math . ICC y VC pueden tener indicadores de compilación similares.

Por cierto: puedes rodar tu propia función de piso usando moldes simples. Solo tienes que manejar los casos negativos y positivos de manera diferente. Eso puede ser mucho más rápido si no necesita el manejo especial de desbordamientos y NaN.

Answer 6

Doble vuelta rápida

double round(double x)
{
    return double((x>=0.5)?(int(x)+1):int(x));
}

Registro de terminal

prueba personalizada_1 8.3837

prueba native_1 18.4989

prueba personalizada_2 8.36333

prueba native_2 18.5001

prueba personalizada_3 8.37316

prueba native_3 18.5012

Prueba

void test(char* name, double (*f)(double))
{
    int it = std::numeric_limits<int>::max();

    clock_t begin = clock();

    for(int i=0; i<it; i++)
    {
        f(double(i)/1000.0);
    }
    clock_t end = clock();

    cout << "test " << name << " " << double(end - begin) / CLOCKS_PER_SEC << endl;

}

int main(int argc, char **argv)
{

    test("custom_1",round);
    test("native_1",std::round);
    test("custom_2",round);
    test("native_2",std::round);
    test("custom_3",round);
    test("native_3",std::round);
    return 0;
}

Resultado

Escribir y usar tu cerebro es ~ 3 veces más rápido que usar funciones nativas.