Agregar una asignación redundante acelera el código cuando se comstack sin optimización

Encuentro un fenómeno interesante:

#include #include 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; } 

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

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

Entonces, ¿por qué el progtwig se ejecuta más rápido con dicha tarea?


La respuesta de Peter es muy útil. Las pruebas en un procesador AMD Phenom II X4 810 y un procesador ARMv7 (BCM2835) muestran un resultado opuesto que admite que la velocidad de reenvío de almacenamiento es específica de alguna CPU Intel.
Y los comentarios y consejos de BeeOnRope me llevan a reescribir la pregunta. 🙂
El núcleo de esta pregunta es el fenómeno interesante que está relacionado con la architecture y el ensamblaje del procesador. Entonces creo que valdría la pena ser discutido.

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


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

Si quiere entrar en los detalles del análisis del rendimiento x86, podemos tratar de explicar por qué el asm funciona de la manera que lo hace en primer lugar, y por qué el asm de una statement extra de C (que con -O0 comstack a las instrucciones extra asm ) podría hacerlo más rápido en general. Esto nos dirá algo acerca de los efectos de rendimiento de asm, pero nada útil para optimizar C.

No ha mostrado todo el bucle interno, solo parte del cuerpo del bucle, pero gcc -O0 es bastante predecible. Cada sentencia C se comstack separadamente de todas las demás, con todas las variables C dertwigdas / recargadas entre los bloques para cada instrucción. Esto le permite cambiar variables con un depurador al paso único, 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 comstackr de esta manera es catastrófico. Por ejemplo, su bucle no tiene efectos secundarios (ninguno de los resultados se usa), por lo que todo el bucle de triple anidación puede y se comstackría a cero instrucciones en una construcción real, que se ejecuta infinitamente más rápido.


El cuello de botella es probablemente la dependencia transportada por bucle en k , con una tienda / recarga y un incremento para incrementar. La latencia de reexpedición de la tienda suele ser de alrededor de 5 ciclos en la mayoría de las CPU . Y, por lo tanto, su bucle interno está limitado a ejecutarse una vez cada ~ 6 ciclos, la latencia de la memoria-destino add .

Si tiene una CPU Intel, la latencia de almacenamiento / recarga en realidad 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. Ver Loop con llamada de función más rápido que un bucle vacío .

Entonces, con más trabajo en el ciclo, ese addl $1, -12(%rbp) que puede mantener un rendimiento de cada 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, de acuerdo con 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 comstackdor (o fuente ASM para el bucle interno) y los números de rendimiento absoluto y / o relativo para ambas versiones , esta es mi mejor estimación de bajo esfuerzo en una explicación. Benchmarking / perfil gcc -O0 en mi sistema Skylake no es lo suficientemente interesante como para probarlo yo mismo. La próxima vez, incluye los números de sincronización.


La latencia de las tiendas / recargas para todo el trabajo que no es parte de la cadena de dependencia transportada por bucle no importa, solo el rendimiento. La cola de la tienda en las CPU modernas fuera de servicio efectivamente proporciona el cambio de nombre de la memoria, eliminando los riesgos de escritura después de escritura y escritura después de leer al reutilizar la misma memoria de stack para escribir y luego leer y escribir en otro lugar. (Consulte https://en.wikipedia.org/wiki/Memory_disambiguation#Avoiding_WAR_and_WAW_dependencies para obtener más información acerca de los riesgos de la memoria en particular, y este Q & A para obtener más información sobre la latencia en comparación con el rendimiento y la reutilización del mismo registro / registro de nombres)

Varias iteraciones del bucle interno pueden estar en vuelo a la vez, porque el búfer de orden de memoria realiza un seguimiento de qué tienda necesita tomar datos de cada carga, sin requerir que un almacenamiento previo en la misma ubicación se comprometa con L1D y salga del cola de la tienda (Consulte el manual de optimización de Intel y el PDF de microarquitección de Agner Fog para obtener más información sobre la microarchitecture interna de la CPU).


¿Esto significa que agregar declaraciones inútiles acelerará los progtwigs reales? (con la optimización habilitada)

En general, no, no es así . Los comstackdores mantienen variables de bucle en los registros de los bucles más internos. Y las declaraciones inútiles en realidad se optimizarán lejos con la optimización habilitada.

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

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


La latencia de reexpedición de la tienda puede ser un problema en la salida real (optimizada) del comstackdor , especialmente si no usó la optimización de tiempo de enlace (LTO) para permitir funciones diminutas en línea, especialmente funciones que pasan o devuelven cualquier cosa por referencia (por lo que pasar por la memoria en lugar de registros). Mitigar el problema puede requerir ataques como volatile si realmente quiere solucionar problemas en las CPU de Intel y quizás empeorar las cosas en algunas otras CPU. Ver discusión en comentarios