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

Ligé algunos ensambles con algunos c para probar el costo de una llamada a función, con el siguiente ensamblado yc fuente (usando fasm y gcc respectivamente)

assembly:

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  #include  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 los vinculaba importaba. Si me gcc intern.o extern.o como gcc intern.o extern.o , un resultado típico es

 162 181 

Pero enlazando en el orden opuesto gcc extern.o intern.o , obtuve un resultado más parecido al siguiente:

 162 130 

Que son diferentes fue muy sorprendente, pero no es la pregunta que estoy haciendo. ( pregunta relevante aquí )

La pregunta que estoy haciendo 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 uno, ¿cómo fue el costo de llamar a una función aparentemente negativa?

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

  • En el bytecode comstackdo, las llamadas a funciones no se optimizaron.
  • Ajustar la alineación de las funciones y los bucles para que estuvieran en todos los límites de 4 a 64 bytes no aceleró no_call, aunque algunas alineaciones se ralentizaron normal_call
  • Darle a la CPU / OS una oportunidad de calentar llamando a las funciones varias veces en lugar de una sola vez no tuvo un efecto notable de las medidas de tiempo medidos, ni cambia el orden de las llamadas ni se ejecuta por separado
  • Correr durante más tiempo no afecta la relación, por ejemplo, correr 1000 veces más, obtuve 162.168 y 131.578 segundos durante mis tiempos de ejecución

Además, después de modificar el código ensamblador para alinearlo en bytes, probé dando al conjunto de funciones un desplazamiento adicional y llegué a 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 más de 4 bytes de alineación para la sección ejecutable, al menos en mi máquina. Compensar el progtwig 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

Editar 2:

Otra cosa que noté es que si eliminas push ecx y pop ecx de ambas funciones, la salida se vuelve

 30 125 

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

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 espaciadas por 3 o más ciclos experimentarán una latencia más rápida (por ejemplo, con 4 imul eax,eax en el ciclo, mov [rdi], eax / mov eax, [rdi] solo toma el conteo cíclico de 12 a 15 ciclos por iteración.) pero cuando las cargas permiten ejecutar más densamente que eso, se sufre algún tipo de conflicto y obtienes alrededor de 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, back-to-back 6.2 a 6.9c), pero los vectores 128b siempre estuvieron alrededor de 5.0c. Ver detalles en el foro de Agner Fog .

Actualización2: la adición de una asignación redundante acelera el código cuando se comstack 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 (peor caso) en Skylake es 1 ciclo mejor que en los uarques anteriores, pero la variabilidad cuando la carga no se puede ejecutar de inmediato es similar.


Con la alineación (incorrecta) correcta, la call adicional en el ciclo puede ayudar a Skylake a observar una latencia de reenvío de tienda menor de empujar a pop. Pude reproducir esto con contadores de perf stat -r4 (Linux perf stat -r4 ), usando YASM. (He oído 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 perfundo en Windows con VTune o algo así.)

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

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

Parece que se trata de una interacción entre el front-end que no hace cola a tantos uops, lo que hace que el back-end tenga una latencia menor para el reenvío de tienda de push a pop.

IDK si reutilizar la misma dirección repetidamente para reenvío de tienda lo hace más lento (con uops de múltiples direcciones de tienda ya ejecutados antes de los uops de datos de tienda correspondientes), 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 redireccionar 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.

Progtwig de prueba NASM / YASM Linux (se ensambla en un binario estático completo que ejecuta el ciclo y luego sale, para que pueda perfilar todo el progtwig). 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 

Ejemplo de salida de una ejecución de call rápida:

 + asm-link -m32 -d call-tight-loop.asm -DFUNC=normal_call -DOFFSET=3 ... 080480d8 : 80480d8: c3 ret ... 08048113 : 8048113: b9 00 e1 f5 05 mov ecx,0x5f5e100 08048118 : 8048118: 51 push ecx 8048119: e8 ba ff ff ff call 80480d8  804811e: 59 pop ecx 804811f: 49 dec ecx 8048120: 83 f9 00 cmp ecx,0x0 8048123: 75 f3 jne 8048118  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 de reenvío de tienda variable

Empuja / presiona su contador de bucle, por lo que todo excepto las instrucciones call y ret (y cmp / jcc ) son parte de la cadena de dependencias de ruta de acceso crítica que involucra el contador de bucles.

Es de esperar que el pop tenga que esperar las actualizaciones del puntero de la stack por call / ret , pero el motor de la stack maneja esas actualizaciones con latencia cero . (Intel desde Pentium-M, AMD desde K10, según el microarch pdf de Agner Fog , así que supongo que tu CPU tiene uno, aunque no dijiste nada sobre en qué microarchitecture de CPU corriste tus pruebas).

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

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

Parece que las diferentes alineaciones para la parte superior del ciclo (es decir, no_call.loop_start: están causando cuellos de botella en el front-end. La versión de call tiene 3 twigs por iteración: la llamada, el ret y la bucle-bifurcación. Tenga en cuenta que el objective de la twig del ret es la instrucción inmediatamente después de la call . Cada uno de estos potencialmente interrumpe el front-end. Como en la práctica se observa una desaceleración real, debemos ver más de 1 ciclo de retardo por twig. O para la versión no_call, una única burbuja de captación / deencoding peor que unos 6 ciclos, lo que lleva a un ciclo perdido real al emitir uops en la parte fuera de orden 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éjenos saber qué CPU ha probado.

Mencionaré que push / pop dentro de un bucle en Skylake no deja de emitirse desde el Loop Stream Detector, y tiene que ser recuperado de la memoria caché uop todo el tiempo. El manual de optimización de Intel dice que para Sandybridge, un push / pop no coincidente dentro de un bucle le impide usar el LSD. Eso implica que puede usar el LSD para bucles con push / pop balanceado. 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 así.

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

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

Este es realmente uno de esos casos de “no hacer eso”: funciones diminutas en línea en lugar de llamarlas desde dentro de bucles muy cerrados.


Es posible que vea resultados diferentes si push / pop un registro que no sea el 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 quizás no igualmente. Podría hacer que un cuello de botella en el front-end sea más obvio.

Debería ver una aceleración enorme si push edx pero pop eax , por lo que las instrucciones push / pop no forman una cadena de dependencia transportada por bucle. Entonces la call / ret adicional 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 utilizado dec ecx / jnz . Además, cmp ecx,0 es menos eficiente que test ecx,ecx (tamaño de código más grande y no se puede fusionar macro en tantas CPU). De todos modos, totalmente irrelevante para la pregunta sobre el rendimiento relativo de sus dos bucles. (La falta de una directiva ALIGN entre las funciones significa que cambiar la primera habría cambiado la alineación de la bifurcación del bucle en la segunda, pero ya habrás explorado diferentes alineamientos).

La llamada a la función normal y su retorno 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 a la diferencia en el código que en realidad está tratando de medir.