Bucle con llamada de función más rápido que un bucle vacío

performance assembly

Question

Enlacé un ensamblaje con algo de c para probar el costo de una llamada de función, con el siguiente ensamblado y fuente c (usando fasm y gcc respectivamente)

montaje:

format ELF
public no_call as "_no_call"
public normal_call as "_normal_call"
section ''.text'' executable
iter equ 100000000
no_call:
mov ecx, iter
@@:
push ecx
pop ecx
dec ecx
cmp ecx, 0
jne @b
ret
normal_function:
ret
normal_call:
mov ecx, iter
@@:
push ecx
call normal_function
pop ecx
dec ecx
cmp ecx, 0
jne @b
ret

c fuente:

#include <stdio.h>
#include <time.h>
extern int no_call();
extern int normal_call();
int main()
{
clock_t ct1, ct2;
ct1 = clock();
no_call();
ct2 = clock();
printf("/n/n%d/n", ct2 - ct1);
ct1 = clock();
normal_call();
ct2 = clock();
printf("%d/n", ct2 - ct1);
return 0;
}

Los resultados que obtuve fueron sorprendentes. En primer lugar, la velocidad dependía del orden en que me vinculaba. Si gcc intern.o extern.o como gcc intern.o extern.o , una salida típica es

162
181

Pero al vincular en el orden opuesto gcc extern.o intern.o , obtuve una salida más como:

162
130

Que sean diferentes fue muy sorprendente, pero no es la pregunta que hago. ( pregunta relevante aquí )

La pregunta que hago es cómo es que en la segunda ejecución el ciclo con la llamada a la función fue más rápido que el ciclo sin una, cómo fue el costo de llamar a una función aparentemente negativa.

Editar: Solo para mencionar algunas de las cosas intentadas en los comentarios:

• En el bytecode compilado, las llamadas a funciones no se optimizaron.
• Ajustar la alineación de las funciones y los bucles para que esté en todo, desde los límites de 4 a 64 bytes, no aceleró no_call, aunque algunas alineaciones ralentizaron normal_call
• Darle a la CPU / OS la oportunidad de calentarse llamando a las funciones varias veces en lugar de solo una vez no tuvo un efecto notable de la duración de los tiempos medidos, tampoco cambia el orden de las llamadas o se ejecuta por separado
• Correr por tiempos más largos no afecta la relación, por ejemplo, correr 1000 veces más. 162.168 y 131.578 segundos para mis tiempos de carrera.

Además, después de modificar el código de ensamblaje para alinear en bytes, probé dando al conjunto de funciones un desplazamiento adicional y llegué a algunas conclusiones más extrañas. Aquí está el código actualizado:

format ELF
public no_call as "_no_call"
public normal_call as "_normal_call"
section ''.text'' executable
iter equ 100000000
offset equ 23 ; this is the number I am changing
times offset nop
times 16 nop
no_call:
mov ecx, iter
no_call.loop_start:
push ecx
pop ecx
dec ecx
cmp ecx, 0
jne no_call.loop_start
ret
times 55 nop
normal_function:
ret
times 58 nop
normal_call:
mov ecx, iter
normal_call.loop_start:
push ecx
call normal_function
pop ecx
dec ecx
cmp ecx, 0
jne normal_call.loop_start
ret

Tuve que forzar manualmente (y no de forma portátil) la alineación de 64 bytes ya que FASM no admite la alineación de más de 4 bytes para la sección ejecutable, al menos en mi máquina. Desplazando el programa por bytes de offset , esto es lo que encontré.

if (20 <= offset mod 128 <= 31) then we get an output of (approximately):
162
131
else
162 (+/- 10)
162 (+/- 10)

No estoy seguro de qué hacer con eso, pero eso es lo que he descubierto hasta ahora

Edición 2:

Otra cosa que noté es que si elimina push ecx y pop ecx de ambas funciones, la salida se convierte en

30
125

lo que indica que esa es la parte más costosa. La alineación de la pila es la misma en ambas ocasiones, por lo que esa no es la razón de la discrepancia. Mi mejor conjetura es que de alguna manera el hardware está optimizado para esperar una llamada después de un impulso o algo similar, pero no sé nada de eso

Answer 1

Actualización: la latencia de almacenamiento / recarga de Skylake es tan baja como 3c , pero solo si el momento es el correcto . Las cargas consecutivas involucradas en una cadena de dependencia de reenvío de tiendas que están naturalmente separadas por 3 o más ciclos experimentarán una latencia más rápida (por ejemplo, con 4 imul eax,eax en el bucle, mov [rdi], eax / mov eax, [rdi] solo lleva el conteo del ciclo de 12 a 15 ciclos por iteración), pero cuando se permite que las cargas se ejecuten más densamente que eso, se sufre algún tipo de contención y obtienes aproximadamente 4.5 ciclos por iteración. El rendimiento promedio no entero también es una gran pista de que hay algo inusual.

Vi el mismo efecto para los vectores 32B (mejor caso 6.0c, 6.2 a 6.9c consecutivos), pero los vectores 128b siempre estuvieron alrededor de 5.0c. Ver detalles en el foro de Agner Fog .

Actualización 2: Agregar una asignación redundante acelera el código cuando se compila sin optimización y una publicación de blog de 2013 indica que este efecto está presente en todas las CPU de la familia Sandybridge .

La latencia de reenvío de tienda consecutiva (en el peor de los casos) en Skylake es 1 ciclo mejor que en uarches anteriores, pero la variabilidad cuando la carga no puede ejecutarse de inmediato es similar.

Con la alineación correcta (errónea), la call adicional en el bucle puede ayudar a Skylake a observar una latencia de reenvío de la tienda más baja de push a pop. Pude reproducir esto con contadores de perf stat -r4 (Linux perf stat -r4 ), usando YASM. (Escuché que es menos conveniente usar contadores de rendimiento en Windows, y de todos modos no tengo una máquina de desarrollo de Windows. Afortunadamente, el sistema operativo no es realmente relevante para la respuesta; cualquiera debería poder reproducir mis resultados de contador de rendimiento en Windows con VTune o algo así)

Vi los tiempos más rápidos en offset = 0..10, 37, 63-74, 101 y 127 después de align 128 en el lugar especificado en la pregunta. Las líneas de caché L1I son 64B, y el caché uop se preocupa por los límites de 32B. Parece que la alineación relativa a un límite de 64B es todo lo que importa.

El ciclo sin llamada es un ciclo constante de 5 ciclos siempre, pero el ciclo de call puede bajar a 4c por iteración de sus ciclos habituales de casi exactamente 5. Vi un rendimiento más lento de lo normal en offset = 38 (5.68 + - 8.3% ciclos por iteración). Hay pequeños problemas técnicos en otros puntos, como 5.17c + - 3.3%, según perf stat -r4 (que hace 4 carreras y promedia).

Parece ser una interacción entre el front-end que no está haciendo cola con tantos uops por delante, lo que hace que el back-end tenga una latencia más baja para el reenvío de la tienda de push a pop.

IDK si la reutilización de la misma dirección repetidamente para el reenvío de la tienda lo hace más lento (con múltiples uops de direcciones de la tienda ya ejecutados antes de los correspondientes uops de datos de la tienda), o qué.

Código de prueba: bash shell loop para construir y perfilar el asm con cada desplazamiento diferente :

(set -x; for off in {0..127};do
asm-link -m32 -d call-tight-loop.asm -DFUNC=normal_call -DOFFSET=$off &&
ocperf.py stat -etask-clock,context-switches,cpu-migrations,page-faults:u,cycles,instructions,uops_issued.any,uops_executed.thread,idq.mite_uops,dsb2mite_switches.penalty_cycles -r4 ./call-tight-loop;
done ) |& tee -a call-tight-loop.call.offset-log

(set -x) en una subshell es una forma práctica de registrar comandos junto con su salida al redirigir a un archivo de registro.

asm-link es un script que ejecuta yasm -felf32 -Worphan-labels -gdwarf2 call-tight-loop.asm "$@" && ld -melf_i386 -o call-tight-loop call-tight-loop.o , luego ejecuta objdumps -drwC -Mintel sobre el resultado.

Programa de prueba NASM / YASM Linux (se ensambla en un binario estático completo que ejecuta el bucle y luego sale, para que pueda perfilar todo el programa). Puerto directo de la fuente FASM del OP, sin optimizaciones para el asm.

CPU p6 ; YASM directive. For NASM, %use smartalign.
section .text
iter equ 100000000
%ifndef OFFSET
%define OFFSET 0
%endif
align 128
;;offset equ 23 ; this is the number I am changing
times OFFSET nop
times 16 nop
no_call:
mov ecx, iter
.loop:
push ecx
pop ecx
dec ecx
cmp ecx, 0
jne .loop
ret
times 55 nop
normal_function:
ret
times 58 nop
normal_call:
mov ecx, iter
.loop:
push ecx
call normal_function
pop ecx
dec ecx
cmp ecx, 0
jne .loop
ret
%ifndef FUNC
%define FUNC no_call
%endif
align 64
global _start
_start:
call FUNC
mov eax,1 ; __NR_exit from /usr/include/asm/unistd_32.h
xor ebx,ebx
int 0x80 ; sys_exit(0), 32-bit ABI

Salida de muestra de una ejecución de call rápida:

+ asm-link -m32 -d call-tight-loop.asm -DFUNC=normal_call -DOFFSET=3
...
080480d8 <normal_function>:
80480d8: c3 ret
...
08048113 <normal_call>:
8048113: b9 00 e1 f5 05 mov ecx,0x5f5e100
08048118 <normal_call.loop>:
8048118: 51 push ecx
8048119: e8 ba ff ff ff call 80480d8 <normal_function>
804811e: 59 pop ecx
804811f: 49 dec ecx
8048120: 83 f9 00 cmp ecx,0x0
8048123: 75 f3 jne 8048118 <normal_call.loop>
8048125: c3 ret
...
Performance counter stats for ''./call-tight-loop'' (4 runs):
100.646932 task-clock (msec) # 0.998 CPUs utilized ( +- 0.97% )
0 context-switches # 0.002 K/sec ( +-100.00% )
0 cpu-migrations # 0.000 K/sec
1 page-faults:u # 0.010 K/sec
414,143,323 cycles # 4.115 GHz ( +- 0.56% )
700,193,469 instructions # 1.69 insn per cycle ( +- 0.00% )
700,293,232 uops_issued_any # 6957.919 M/sec ( +- 0.00% )
1,000,299,201 uops_executed_thread # 9938.695 M/sec ( +- 0.00% )
83,212,779 idq_mite_uops # 826.779 M/sec ( +- 17.02% )
5,792 dsb2mite_switches_penalty_cycles # 0.058 M/sec ( +- 33.07% )
0.100805233 seconds time elapsed ( +- 0.96% )

Respuesta anterior antes de notar la latencia variable de reenvío de tienda

Usted empuja / revienta su contador de bucle, por lo que todo, excepto las instrucciones de call y ret (y el cmp / jcc ) son parte de la cadena de dependencia de ruta crítica que lleva el contador de bucle.

Es de esperar que pop tenga que esperar actualizaciones para el puntero de la pila por call / ret , pero el motor de pila maneja esas actualizaciones con latencia cero . (Intel desde Pentium-M, AMD desde K10, según el pdf de microarchivo de Agner Fog , por lo que supongo que su CPU tiene uno, a pesar de que no dijo nada sobre qué microarquitectura de CPU realizó sus pruebas).

La call / ret adicional aún necesita ejecutarse, pero la ejecución fuera de orden puede mantener las instrucciones de ruta críticas ejecutándose en su rendimiento máximo. Dado que esto incluye la latencia de un reenvío store-> load de push / pop + 1 ciclo para dec , esto no es un alto rendimiento en ninguna CPU, y es una sorpresa que el front-end pueda ser un cuello de botella con cualquier alineación.

push -> pop latencia pop es de 5 ciclos en Skylake, de acuerdo con Agner Fog, por lo que ese ciclo solo puede ejecutarse en el mejor de los casos una iteración por 6 ciclos. Este es tiempo suficiente para que la ejecución fuera de orden ejecute las instrucciones de call y ret . Agner enumera un rendimiento máximo para call de uno por cada 3 ciclos, y ret en uno por cada 1 ciclo. O en AMD Bulldozer, 2 y 2. Sus tablas no enumeran nada sobre el rendimiento de un par de call / ret , por lo tanto, IDK si pueden superponerse o no. En AMD Bulldozer, la latencia de almacenamiento / recarga con mov es de 8 ciclos. Supongo que es casi lo mismo con push / pop.

Parece que diferentes alineaciones para la parte superior del bucle (es decir, no_call.loop_start: están causando cuellos de botella en el front-end. La versión de call tiene 3 ramas por iteración: la llamada, la ret y la rama de bucle. Tenga en cuenta que el objetivo de la rama de ret es la instrucción justo después de la call . Cada uno de estos potencialmente interrumpe el front-end. Como está viendo una desaceleración real en la práctica, debemos estar viendo más de 1 ciclo de retraso por rama. O para la versión no_call, una sola burbuja de búsqueda / decodificación peor que aproximadamente 6 ciclos, lo que lleva a un ciclo perdido real al emitir uops en la parte fuera de servicio del núcleo. Eso es raro.

Es demasiado complicado adivinar cuáles son los detalles microarquitectónicos reales para cada posible uarch, así que díganos qué CPU probó.

Sin embargo, mencionaré que push / pop dentro de un bucle en Skylake evita que se emita desde el Loop Stream Detector, y tiene que volverse a buscar desde el caché uop cada vez. El manual de optimización de Intel dice que para Sandybridge, un push / pop no coincidente dentro de un bucle impide que use el LSD. Eso implica que puede usar el LSD para bucles con push / pop equilibrado. En mis pruebas, ese no es el caso en Skylake (usando el lsd.uops rendimiento lsd.uops ), pero no he visto ninguna mención de si eso fue un cambio, o si SnB también fue realmente así.

Además, las ramas incondicionales siempre terminan una línea uop-cache. Es posible que con normal_function: en el mismo trozo de código de máquina 32B alineado naturalmente que la call y jne , tal vez el bloque de código no encaje en la caché de uop. (Solo 3 líneas uop-cache pueden almacenar en caché uops decodificados para un solo fragmento de 32B de código x86). Pero eso no explicaría la posibilidad de problemas para el bucle no_call, por lo que probablemente no esté ejecutando una microarquitectura de la familia Intel SnB.

(Actualización, sí, el bucle a veces se ejecuta principalmente desde la decodificación heredada ( idq.mite_uops ), pero generalmente no exclusivamente. dsb2mite_switches.penalty_cycles suele ser ~ 8k, y probablemente solo ocurre en las interrupciones del temporizador. Las ejecuciones donde el bucle de call ejecuta más rápido parecen parecer correlacionarse con idq.mite_uops más idq.mite_uops , pero sigue siendo 34M + - 63% para el caso offset = 37 donde las iteraciones de 100M tomaron 401M ciclos).

Este es realmente uno de esos casos de "no hagas eso": funciones pequeñas en línea en lugar de llamarlas desde dentro de bucles muy ajustados.

Es posible que vea resultados diferentes si push / pop un registro que no sea su contador de bucles. Eso separaría el push / pop del contador de bucle, por lo que habría 2 cadenas de dependencia separadas. Debería acelerar las versiones call y no_call, pero tal vez no por igual. Podría hacer que un cuello de botella en el front-end sea más obvio.

Debería ver una gran aceleración si push edx pero pop eax , por lo que las instrucciones push / pop no forman una cadena de dependencia transportada en bucle. Entonces la call extra / ret definitivamente sería un cuello de botella.

Nota al dec ecx : dec ecx ya establece ZF de la manera que desea, por lo que podría haber usado dec ecx / jnz . Además, cmp ecx,0 es menos eficiente que test ecx,ecx (código de mayor tamaño y no se puede fusionar con macro en tantas CPU). De todos modos, totalmente irrelevante para la pregunta sobre el rendimiento relativo de sus dos bucles. (Su falta de una directiva ALIGN entre funciones significa que cambiar la primera habría cambiado la alineación de la rama del bucle en la segunda, pero ya ha explorado diferentes alineaciones).

Answer 2

La llamada a normal_function y el retorno de ella se predecirán correctamente cada vez, excepto la primera, por lo que no esperaría ver ninguna diferencia en el tiempo debido a la presencia de la llamada. Por lo tanto, todas las diferencias en el tiempo que ve (ya sea más rápido o más lento) se deben a otros efectos (como los mencionados en los comentarios) en lugar de la diferencia en el código que realmente está tratando de medir.