Rendimiento del cast de size_t al doble

performance casting

Question

TL; DR : ¿Por qué los datos de multiplicación / fundición en size_t lentos y por qué esto varía según la plataforma?

Tengo algunos problemas de rendimiento que no entiendo completamente. El contexto es un capturador de fotogramas de la cámara donde se lee y postprocesa una imagen de 128x128 uint16_t a una velocidad de varios 100 Hz.

En el post-procesamiento genero un uint32_t de histograma- frame->histo que es de uint32_t y tiene thismaxval = 2 ^ 16 elementos, básicamente hago un recuento de todos los valores de intensidad. Usando este histograma, calculo la suma y la suma al cuadrado:

double sum=0, sumsquared=0;
size_t thismaxval = 1 << 16;

for(size_t i = 0; i < thismaxval; i++) {
    sum += (double)i * frame->histo[i];
    sumsquared += (double)(i * i) * frame->histo[i];
}

Perfilando el código con el perfil obtuve lo siguiente (muestras, porcentaje, código):

 58228 32.1263 :  sum += (double)i * frame->histo[i];
116760 64.4204 :  sumsquared += (double)(i * i) * frame->histo[i];

o bien, la primera línea ocupa el 32% del tiempo de CPU, la segunda línea el 64%.

Hice algunos benchmarking y parece ser el tipo de datos / casting que es problemático. Cuando cambio el código a

uint_fast64_t isum=0, isumsquared=0;

for(uint_fast32_t i = 0; i < thismaxval; i++) {
    isum += i * frame->histo[i];
    isumsquared += (i * i) * frame->histo[i];
}

funciona ~ 10x más rápido. Sin embargo, este impacto en el rendimiento también varía según la plataforma. En la estación de trabajo, una CPU Core i7 950 @ 3.07GHz el código es 10 veces más rápido. En mi Macbook8,1, que tiene un Intel Core i7 Sandy Bridge 2.7 GHz (2620M), el código es solo 2 veces más rápido.

Ahora me pregunto:

1. ¿Por qué el código original es tan lento y se acelera fácilmente?
2. ¿Por qué esto varía tanto por plataforma?

Actualizar:

Recopilé el código anterior con

g++ -O3  -Wall cast_test.cc -o cast_test

Actualización2:

Ejecuté los códigos optimizados a través de un generador de perfiles ( Instruments en Mac, como Shark ) y encontré dos cosas:

1) El bucle en sí lleva una cantidad considerable de tiempo en algunos casos. thismaxval es de tipo size_t .

1. for(size_t i = 0; i < thismaxval; i++) toma el 17% de mi tiempo de ejecución total
2. for(uint_fast32_t i = 0; i < thismaxval; i++) toma 3.5%
3. for(int i = 0; i < thismaxval; i++) no aparece en el generador de perfiles, supongo que es menos de 0.1%

2) Los tipos de datos y el casting son los siguientes:

1. sumsquared += (double)(i * i) * histo[i]; 15% (con size_t i )
2. sumsquared += (double)(i * i) * histo[i]; 36% (con uint_fast32_t i )
3. isumsquared += (i * i) * histo[i]; 13% (con uint_fast32_t i , uint_fast64_t isumsquared )
4. isumsquared += (i * i) * histo[i]; 11% (con int i , uint_fast64_t isumsquared )

Sorprendentemente, int es más rápido que uint_fast32_t ?

Actualización4:

Ejecuté algunas pruebas más con diferentes tipos de datos y diferentes compiladores, en una máquina. Los resultados son los siguientes.

Para testd 0 - 2 el código relevante es

    for(loop_t i = 0; i < thismaxval; i++)
        sumsquared += (double)(i * i) * histo[i];

con sumsquared un doble, y loop_t size_t , uint_fast32_t e int para las pruebas 0, 1 y 2.

Para las pruebas 3 a 5, el código es

    for(loop_t i = 0; i < thismaxval; i++)
        isumsquared += (i * i) * histo[i];

con isumsquared de tipo uint_fast64_t y loop_t otra vez size_t , uint_fast32_t e int para las pruebas 3, 4 y 5.

Los compiladores que utilicé son gcc 4.2.1, gcc 4.4.7, gcc 4.6.3 y gcc 4.7.0. Los tiempos son en porcentajes del tiempo de CPU total del código, por lo que muestran un rendimiento relativo, no absoluto (aunque el tiempo de ejecución fue bastante constante en 21 s). El tiempo de CPU es para ambas líneas, porque no estoy seguro de si el generador de perfiles separa correctamente las dos líneas de código.

gcc: 4.2.1 4.4.7 4.6.3 4.7.0 ---------------------------------- test 0: 21.85 25.15 22.05 21.85 test 1: 21.9 25.05 22 22 test 2: 26.35 25.1 21.95 19.2 test 3: 7.15 8.35 18.55 19.95 test 4: 11.1 8.45 7.35 7.1 test 5: 7.1 7.8 6.9 7.05

o:

En base a esto, parece que el casting es costoso, independientemente del tipo de entero que use.

Además, parece que gcc 4.6 y 4.7 no pueden optimizar el bucle 3 (size_t y uint_fast64_t) correctamente.

Answer 1

En x86, la conversión de uint64_t a coma flotante es más lenta porque solo hay instrucciones para convertir int64_t , int32_t e int16_t . int16_t y en el modo de 32 bits int64_t solo se puede convertir usando instrucciones x87, no SSE.

Al convertir uint64_t a coma flotante, GCC 4.2.1 primero convierte el valor como si fuera un int64_t y luego agrega 2 ⁶⁴ si era negativo para compensar. (Cuando usa x87, en Windows y * BSD o si cambió el control de precisión, tenga en cuenta que la conversión ignora el control de precisión pero la adición lo respeta).

Un uint32_t primero se extiende a int64_t .

Al convertir números enteros de 64 bits en el modo de 32 bits en procesadores con ciertas capacidades de 64 bits, un problema de reenvío de almacenar a la carga puede causar bloqueos. El entero de 64 bits se escribe como dos valores de 32 bits y se lee de nuevo como un valor de 64 bits. Esto puede ser muy malo si la conversión es parte de una larga cadena de dependencia (no en este caso).

Answer 2

Para sus preguntas originales:

1. El código es lento porque implica la conversión de tipos de datos enteros a flotantes. Es por eso que se acelera fácilmente cuando usa también un tipo de datos entero para las variables de suma porque ya no requiere una conversión flotante.
2. La diferencia es el resultado de varios factores. Por ejemplo, depende de qué tan eficiente sea la plataforma para realizar una conversión int-> float. Además, esta conversión también podría ensuciar las optimizaciones internas del procesador en el flujo de programa y el motor de predicción, las memorias caché, ... y también las características internas de paralelización de los procesadores que pueden tener una gran influencia en dichos cálculos.

Para las preguntas adicionales:

• "¿Sorprendentemente int es más rápido que uint_fast32_t"? ¿Cuál es el tamaño de (size_t) y sizeof (int) en su plataforma? Una conjetura que puedo hacer es que ambos son probablemente de 64 bits y, por lo tanto, un lanzamiento a 32 bits no solo puede dar errores de cálculo, sino que también incluye una penalización de lanzamiento de tamaño diferente.

En general, trate de evitar los moldes visibles y ocultos lo mejor posible si estos no son realmente necesarios. Por ejemplo, intente descubrir qué tipo de datos real está oculto detrás de "size_t" en su entorno (gcc) y use ese para la variable de bucle. En su ejemplo, el cuadrado de uint no puede ser un tipo de datos flotante, por lo que no tiene sentido utilizar el doble aquí. Apéguese a los tipos enteros para lograr el máximo rendimiento.