performance - Agregar una asignación redundante acelera el código cuando se compila sin optimización

assembly x86

Question

Encuentro un fenómeno interesante:

#include<stdio.h>
#include<time.h>
int main() {
int p, q;
clock_t s,e;
s=clock();
for(int i = 1; i < 1000; i++){
for(int j = 1; j < 1000; j++){
for(int k = 1; k < 1000; k++){
p = i + j * k;
q = p; //Removing this line can increase running time.
}
}
}
e = clock();
double t = (double)(e - s) / CLOCKS_PER_SEC;
printf("%lf/n", t);
return 0;
}

Utilizo GCC 7.3.0 en i5-5257U Mac OS para compilar el código sin ninguna optimización . Aquí está el tiempo de ejecución promedio más de 10 veces: También hay otras personas que prueban el caso en otras plataformas Intel y obtienen el mismo resultado.
Publico el ensamblado generado por GCC here . La única diferencia entre dos códigos de ensamblaje es que antes de addl $1, -12(%rbp) el más rápido tiene dos operaciones más:

movl -44(%rbp), %eax
movl %eax, -48(%rbp)

Entonces, ¿por qué el programa se ejecuta más rápido con tal asignación?

La respuesta de Peter es muy útil. Las pruebas en un AMD Phenom II X4 810 y un procesador ARMv7 (BCM2835) muestran un resultado opuesto que admite que la aceleración del reenvío de la tienda es específica para algunas CPU Intel.
Y el comentario y los consejos de BeeOnRope me llevan a reescribir la pregunta. :)
El núcleo de esta pregunta es el fenómeno interesante relacionado con la arquitectura y el ensamblaje del procesador. Así que creo que valdría la pena discutirlo.

Answer 1

Está comparando una compilación de depuración, que es básicamente inútil .

Pero, obviamente, hay una razón real para que la compilación de depuración de una versión se ejecute más lentamente que la compilación de depuración de la otra versión. (Suponiendo que midió correctamente y que no solo la variación de frecuencia de la CPU (turbo / ahorro de energía) condujo a una diferencia en el tiempo del reloj de pared).

Si desea entrar en los detalles del análisis de rendimiento x86, podemos tratar de explicar por qué el ASM funciona de la manera en que lo hace en primer lugar, y por qué el ASM de una instrucción C adicional (que con -O0 compila a instrucciones -O0 adicionales ) podría hacerlo más rápido en general. Esto nos dirá algo sobre los efectos de rendimiento de asm, pero nada útil sobre la optimización de C.

No ha mostrado todo el bucle interno, solo parte del cuerpo del bucle, pero gcc -O0 es bastante predecible. Cada declaración C se compila por separado de todas las demás, con todas las variables C derramadas / recargadas entre los bloques para cada declaración. Esto le permite cambiar las variables con un depurador mientras realiza un solo paso, o incluso saltar a una línea diferente en la función, y hacer que el código siga funcionando. El costo de rendimiento de compilar de esta manera es catastrófico. Por ejemplo, su ciclo no tiene efectos secundarios (no se utiliza ninguno de los resultados), por lo que todo el ciclo triple anidado puede compilarse a cero instrucciones en una compilación real, corriendo infinitamente más rápido.

El cuello de botella es probablemente la dependencia de k transportada por un bucle, con un almacenamiento / recarga y una add al incremento. La latencia de reenvío de tienda suele ser de unos 5 ciclos en la mayoría de las CPU . Y, por lo tanto, su bucle interno se limita a ejecutarse una vez cada ~ 6 ciclos, add la latencia del destino de memoria.

Si está en una CPU Intel, la latencia de almacenamiento / recarga puede ser menor (mejor) cuando la recarga no puede intentar ejecutarse de inmediato . Tener más cargas / tiendas independientes entre el par dependiente puede explicarlo en su caso. Vea Bucle con llamada de función más rápido que un bucle vacío .

Entonces, con más trabajo en el ciclo, esa addl $1, -12(%rbp) que puede mantener uno por rendimiento de 6 ciclos cuando se ejecuta de forma consecutiva podría crear un cuello de botella de una iteración por 4 o 5 ciclos.

Actualización : este efecto aparentemente ocurre en Sandybridge y Haswell, según las mediciones de una publicación de blog de 2013 , así que sí, esta es la explicación más probable en su Broadwell i5-5257U también. Parece que este efecto ocurre en todas las CPU de la familia Intel Sandybridge .

Sin más información sobre el hardware de prueba, la versión del compilador (o la fuente asm para el bucle interno) y los números de rendimiento absoluto y / o relativo para ambas versiones , esta es mi mejor suposición de bajo esfuerzo en una explicación. Benchmarking / gcc -O0 en mi sistema Skylake no es lo suficientemente interesante como para probarlo yo mismo. La próxima vez, incluya números de tiempo.

La latencia de las tiendas / recargas para todo el trabajo que no es parte de la cadena de dependencia transportada en bucle no importa, solo el rendimiento. La cola de la tienda en las CPU modernas fuera de orden proporciona efectivamente el cambio de nombre de la memoria, eliminando los riesgos de escritura después de escribir y escritura después de leer al reutilizar la misma memoria de pila para que p se escriba y luego se lea y escriba en otro lugar. (Consulte https://en.wikipedia.org/wiki/Memory_disambiguation#Avoiding_WAR_and_WAW_dependencies para obtener más información sobre los riesgos de memoria específicamente, y estas preguntas y respuestas para obtener más información sobre la latencia frente al rendimiento y la reutilización del mismo cambio de nombre de registro / registro)

Múltiples iteraciones del bucle interno pueden estar en vuelo a la vez, porque el búfer de orden de memoria realiza un seguimiento de qué almacén necesita cada carga para tomar datos, sin requerir un almacén anterior en la misma ubicación para comprometerse con L1D y salir del Tienda de cola. (Consulte el manual de optimización de Intel y el PDF de microarchivo de Agner Fog para obtener más información sobre los componentes internos de microarquitectura de la CPU).

¿Significa esto que agregar declaraciones inútiles acelerará los programas reales? (con optimización habilitada)

En general, no, no lo hace . Los compiladores mantienen variables de bucle en registros para los bucles más internos. Y las declaraciones inútiles en realidad se optimizarán con la optimización habilitada.

Ajustar su fuente para gcc -O0 es inútil. Mida con -O3 , o cualquier opción que utilicen los scripts de compilación predeterminados para su proyecto.

Además, esta aceleración de reenvío de tiendas es específica de la familia Intel Sandybridge, y no la verá en otras microarquitecturas como Ryzen, a menos que también tengan un efecto de latencia de reenvío de tiendas similar.

La latencia de reenvío de tienda puede ser un problema en la salida real (optimizada) del compilador , especialmente si no usó la optimización de tiempo de enlace (LTO) para dejar en línea las funciones pequeñas, especialmente las funciones que pasan o devuelven cualquier cosa por referencia (por lo que tiene ir a través de la memoria en lugar de registros). Mitigar el problema puede requerir hacks como volatile si realmente desea solucionarlo en las CPU Intel y quizás empeorar las cosas en algunas otras CPU. Ver discusión en comentarios