Rendimiento del elenco de size_t al doble

Question

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

Tengo algunos problemas de rendimiento que no entiendo del todo. 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-tratamiento de I generan un histograma frame->histo que es de uint32_t y tiene thismaxval = 2^16 elementos, básicamente I Flirteo con todos los valores de intensidad. El uso de este histograma puedo calcular 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]; 
} 

perfilar el código con el perfil Me lo siguiente (muestras, porcentaje, el código):

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

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

Hice algunos benchmarking y parece ser el tipo de datos/el molde 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 ~ 10 veces 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é es el código original de manera lenta y fácilmente aceleró?
2. ¿Por qué esto varía tanto por plataforma?

Actualización:

He compilado el código anterior con

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

Update2:

que corrieron 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 del tipo size_t.

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

2) los tipos de datos y la materia de fundición como sigue:

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?

Update4:

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

Para testd 0 - 2 en el código en cuestión es

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

con sumsquared un doble, y loop_tsize_t, uint_fast32_t y int para las pruebas de 0, 1 y 2.

Para las pruebas 3-- 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 de nuevo size_t, uint_fast32_t y int para las pruebas 3, 4 y 5.

Los compiladores I utilizado son 4.2.1 gcc, gcc 4.4.7, 4.6.3 gcc gcc y 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:

Sobre la base de esto, parece que la fundición es costoso, no importa qué tipo entero que uso.

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

Para sus preguntas originales:

1. El código es lento, ya que implica la conversión de número entero a tipos de datos float. Es por eso que se acelera fácilmente cuando también usa 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 capaz una plataforma de realizar una conversión int-> float. Además, esta conversión también podría dañar las optimizaciones internas del procesador en el programa motor de flujo y predicción, cachés, ... y también las características de paralelización internas de los procesadores pueden tener una gran influencia en tales cálculos.

Para las preguntas adicionales:

• "Sorprendentemente int es más rápido que uint_fast32_t"? ¿Cuál es el tamaño de sizeof (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 le puede dar errores de cálculo de , sino que también incluye una penalización de 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égate a los tipos enteros para lograr el máximo rendimiento.

Answer 2

en x86, la conversión de uint64_t de punto flotante es más lento porque sólo hay instrucciones para convertir int64_t, int32_t y int16_t. int16_t y en el modo de 32 bits int64_t solo se pueden convertir utilizando instrucciones x87, no SSE.

Al convertir uint64_t a punto flotante, GCC 4.2.1 primero convierte el valor como si fuera un int64_t y luego añade 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).

Se amplió primero a uint32_t a int64_t.

Al convertir 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).