c - 使用函数调用循环比空循环更快

Question

我将某些程序集与某些c链接起来，以测试函数调用的成本，并使用以下程序集和c源代码(分别使用fasm和gcc)

部件:

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来源:

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

我得到的结果令人惊讶。首先，速度取决于我联系的顺序。如果我链接为 gcc intern.o extern.o，则典型输出为

162
181

但是以相反的顺序 gcc extern.o intern.o链接，我得到的输出更像:

162
130

他们的不同之处令人惊讶，但 不是是我要问的问题。 ( relevant question here)

我要问的问题是，在第二次运行中，使用函数调用的循环比没有使用函数调用的循环要快，调用函数的成本显然是负数。

编辑:
仅提及评论中尝试的一些事项:

在编译的字节码中，并未优化函数调用。

将函数和循环的对齐方式调整为从4到64字节边界的所有内容，都不会加快no_call的速度，尽管某些对齐方式会降低normal_call的速度

通过多次调用函数(而不是一次)来给CPU / OS一个预热的机会，这对测量的时间长度没有显着影响，更改调用顺序或单独运行

都没有

运行较长时间不会影响该比率，例如，运行1000倍以上，我得到

的运行时间为 162.168和 131.578秒

另外，在修改了汇编代码以使其按字节对齐之后，我进行了测试，为函数集提供了额外的偏移量，并得出了一些更奇怪的结论。这是更新的代码:

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

由于FASM至少在我的机器上不支持可执行部分的4字节以上的对齐，因此我不得不手动(且非便携式)强制执行64字节的对齐。通过 offset字节来抵消程序，这是我发现的。

if (20 <= offset mod 128 <= 31) then we get an output of (approximately):

162
131

else

162 (+/- 10)
162 (+/- 10)

完全不确定要做什么，但这是我到目前为止发现的

编辑2:

我注意到的另一件事是，如果您从这两个函数中删除 push ecx和 pop ecx，输出将变为

30
125

这表明那是最昂贵的部分。两次堆栈对齐都是相同的，因此这不是差异的原因。我最好的猜测是，某种程度上，硬件已经过优化，可以在推送或类似操作后进行 call ，但是我不知道这样的事情

Answer 1

更新: Skylake存储/重新加载延迟低至3c ，但前提是时机合适。自然地间隔3个或更多周期的存储转发依赖链中涉及的连续负载将经历更快的延迟(例如，循环中有4个imul eax,eax，mov [rdi], eax / mov eax, [rdi]仅使周期数从每次迭代的12到15个周期递增。)，但是如果允许负载执行得更密集，则将发生某种类型的争用，并且每次迭代可获得大约4.5个周期。非整数的平均吞吐量也很明显地表明存在异常。

我看到了32B vector 的效果相同(最好的情况是6.0c，背靠背是6.2到6.9c)，但是128b vector 始终在5.0c左右。参见details on Agner Fog's forum。

Update2:Adding a redundant assignment speeds up code when compiled without optimization和2013 blog post表示，这种影响存在于所有Sandybridge系列CPU 上。

Skylake上的背对背(最坏情况)存储转发延迟比以前的uarch上好1个周期，但是负载无法立即执行时的可变性相似。

通过正确(错误)对齐，循环中额外的call实际上可以帮助Skylake观察从推送到弹出的更低的存储转发延迟。我可以使用YASM在性能计数器(Linux perf stat -r4)上重现此内容。 (我听说在Windows上使用perf计数器较不方便，而且我也没有Windows开发机。幸运的是，该操作系统与答案并没有真正的关系；任何人都应该能够再现我的perf-counter结果在装有VTune的Windows上。)

我看到在问题中指定位置的align 128 之后，在offset = 0..10、37、63-74、101和127处的速度更快。 L1I缓存行是64B，而uop-cache关心的是32B边界。看起来相对于64B边界的对齐很重要。

无调用循环始终是稳定的5个周期，但是call循环每次迭代可以从通常的几乎5个周期降低到4c。在偏移量= 38(每次迭代5.68±8.3％周期)时，我看到了比平常慢的性能。根据perf stat -r4(执行4次并取平均值)，在其他点上存在小故障，例如5.17c +-3.3％。

这似乎是前端之间未进行排队的交互，从而导致后端从推送到弹出的存储转发延迟较低。

如果IDK重复使用相同的地址进行存储转发，则IDK会变慢(已在对应的存储数据uop之前执行了多个存储地址ucp)，或者发生了什么。

测试代码:bash shell循环以使用每个不同的偏移量来构建和分析asm:

(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

子 shell 中的 (set -x)是在重定向到日志文件时记录命令及其输出的便捷方法。

asm-link 是运行 yasm -felf32 -Worphan-labels -gdwarf2 call-tight-loop.asm "$@" && ld -melf_i386 -o call-tight-loop call-tight-loop.o，然后在结果上运行 objdumps -drwC -Mintel的脚本。

NASM / YASM Linux测试程序(组装成一个完整的静态二进制文件，运行该循环然后退出，因此您可以对整个程序进行概要分析。)OP的FASM源的直接端口，而没有对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

快速 call运行的示例输出:

+ 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% )

在注意到可变的存储转发延迟之前的旧答案

推送/弹出循环计数器，因此 call和 ret指令(以及 cmp / jcc)以外的所有内容都是涉及循环计数器的关键路径循环依赖项链的一部分。

您希望 pop必须等待 call / ret对堆栈指针的更新，但要等待 the stack engine handles those updates with zero latency。 (据 Agner Fog's microarch pdf称，英特尔自Pentium-M以来，AMD自K10以来，因此我假设您的CPU有一个，即使您未对运行测试的CPU微体系结构说什么也没说。)

额外的 call / ret仍然需要执行，但是乱序执行可以使关键路径指令以其最大吞吐量运行。由于这包括 dec从push / pop + 1个周期的存储->负载转发的等待时间，因此这在任何CPU上都不是很高的吞吐量，并且令人惊讶的是，前端可能成为任何对齐方式的瓶颈。

根据Agner Fog的说法，在Skylake上 push-> pop延迟为5个周期，因此，在uarch上，循环最多只能每6个周期运行一次迭代。
这对于无序执行有很多时间来运行 call和 ret指令。 Agner列出 call的最大吞吐量为每3个周期之一，而 ret的最大吞吐量为每1个周期之一。或在AMD Bulldozer的2和2上。他的表未列出有关 call / ret对的吞吐量的任何信息，因此IDK是否可以重叠。在AMD Bulldozer上，带有 mov的存储/重新加载延迟为8个周期。我认为与push / pop差不多。

似乎循环顶部的不同对齐方式(即 no_call.loop_start:)导致了前端瓶颈。 call版本每次迭代有3个分支:调用，ret和循环分支。请注意， ret的分支目标是 call之后的指令。这些都有可能破坏前端。由于您实际上看到的是实际的速度下降，因此我们必须看到每个分支有1个以上的循环延迟。或者对于no_call版本，单个获取/解码气泡差于大约6个周期，导致在向内核的乱序部分发出uops时导致实际浪费的周期。那真是怪了。

猜测每个可能的架构的实际微体系结构细节太复杂了，所以让我们知道您在哪个CPU上进行了测试。

我会提到，尽管Skylake上的循环内的 push / pop阻止了它从循环流检测器发出，并且每次都必须从uop缓存中重新获取。 Intel's optimization manual说，对于Sandybridge，循环内不匹配的push / pop阻止了它使用LSD。这意味着它可以将LSD用于具有平衡推入/弹出操作的循环。在我的测试中，在Skylake(使用 lsd.uops性能计数器)上不是这种情况，但是我没有看到有关这是否是更改或SnB实际上也是如此的任何提及。

同样，无条件分支总是以uop-cache行结尾。如果 normal_function:与 call和 jne放在同一自然对齐的32B机器代码大块中，则代码块可能不适合uop缓存。 (只有3个uop缓存行可以为x86代码的单个32B块缓存解码的uops)。但这不能解释no_call循环出现问题的可能性，因此您可能未在Intel SnB系列微体系结构上运行。

(更新，是的，循环有时主要从旧式解码( idq.mite_uops)运行，但通常不是排他性的。 dsb2mite_switches.penalty_cycles通常约为8k，并且可能仅在定时器中断时发生。 call循环运行得更快的运行似乎与更低的运行相关。 idq.mite_uops，但对于offset = 37的情况(仍然是100M迭代需要401M个周期)，仍然是34M +-63％。)

这实际上是“不这样做”的情况之一:内联微小函数，而不是从非常紧密的循环中调用它们。

如果您对循环计数器以外的寄存器 push / pop进行注册，则可能会看到不同的结果。这会将push / pop与循环计数器分开，因此会有2个独立的依赖链。它应该同时加快call和no_call版本的速度，但可能不尽相同。它只会使前端瓶颈更加明显。

如果您使用 push edx而不是 pop eax，应该会看到巨大的加速，因此push / pop指令不会形成循环承载的依赖链。然后，额外的 call / ret肯定是瓶颈。

旁注: dec ecx已经按照您想要的方式设置了ZF，因此您可以只使用 dec ecx / jnz。另外， cmp ecx,0 is less efficient than test ecx,ecx (较大的代码大小，不能在多个CPU上进行宏熔断)。无论如何，这与两个循环的相对性能完全无关。 (您在函数之间缺少 ALIGN指令意味着更改第一个将更改第二个循环分支的对齐方式，但是您已经探索了不同的对齐方式。)