以比空循环更快的速度循环函数调用

我将一些程序集与一些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("nn%dn", ct2 - ct1);

    ct1 = clock();
    normal_call();
    ct2 = clock();
    printf("%dn", ct2 - ct1);

    return 0;
}

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

162
181

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

162
130

他们是不同的是非常惊讶,但不是我问的问题。 (相关问题在这里)

我所问的问题是,在第二次运行中,函数调用的循环是如何比没有循环的循环更快,调用函数的成本显然是负的。

编辑:只是提到一些在评论中尝试的东西:

  • 在编译的字节码中,函数调用没有被优化。
  • 将函数和循环的对齐调整为4到64字节边界的所有内容都不会加速no_call,尽管某些对齐确实减慢了normal_call
  • 通过多次调用函数而不是一次调用函数来预热CPU / OS,对测量时间长度没有显着影响,也不会改变调用顺序或单独运行
  • 运行时间较长不会影响比率,例如运行时间延长1000倍我的运行时间为162.168131.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
    

    我必须手动(并且不可移植)强制64字节对齐,因为FASM不支持可执行部分至少4个字节对齐,至少在我的机器上。 通过offset字节offset程序,这是我发现的。

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

    不知道该怎么做,但这是我迄今为止发现的

    编辑2:

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

    30
    125
    

    这表明这是最昂贵的部分。 堆栈对齐两次都是一样的,所以这不是造成差异的原因。 我最好的猜测是,不知何故硬件经过优化,可以在推送或类似的事情之后得到呼叫,但我不知道这样的事情


    更新: Skylake存储/重载延迟低至3c ,但前提是时机正确。 涉及存储转发依赖链的连续负载自然间隔3个或更多个周期,将会遇到更快的延迟(例如,4个imul eax,eax循环中的imul eax,eaxmov [rdi], eax / mov eax, [rdi]只需要每次循环的循环次数从12次增加到15次),但是当负载被允许执行得更加密集时,就会出现某种类型的争用,并且每次迭代大约会产生4.5次循环。 非整数平均吞吐量也是一个很大的线索,有一些不寻常的东西。

    我看到了32B矢量(最佳情况下为6.0c,背靠背为6.2到6.9c)的效果,但128b矢量总是在5.0c左右。 查看Agner Fog论坛的详细信息。

    Update2:在不进行优化编译时添加冗余分配可以加快代码速度,2013年的博客文章指出, 这种影响在所有Sandybridge系列CPU上都存在

    Skylake上的背靠背(最糟糕的情况)存储转发延迟比以前的原始存储更好1个周期,但是当负载不能立即执行时的可变性是相似的。


    通过正确(错误)对齐,循环中的额外call实际上可以帮助Skylake观察到从推送到流行的较低存储转发延迟。 我能够使用perf stat -r4在perf性能指标(Linux perf stat -r4 )中重现这一点。 (我听说在Windows上使用perf计数器不太方便,无论如何我没有Windows开发机器,幸运的是操作系统与答案无关;任何人都应该能够重现我的perf-counter结果在Windows上用VTune或其他东西。)

    我在偏移量= 0..10,37,63-74,101和127处看到在问题中指定的点处align 128之后的更快时间 。 L1I高速缓存线是64B,而uop-cache关心32B的边界。 它看起来相对于64B边界对齐是重要的。

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

    这似乎是前端之间的交互,而不是排在前面的许多uops之间,导致后端从push到pop存储转发的延迟更低。

    IDK如果重复使用相同的地址进行存储转发会使其速度变慢(多个存储地址uops已经在相应的存储数据uops之前执行),或者是什么。


    测试代码: 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
    

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

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

    您可以按/弹出循环计数器,因此除callret指令(以及cmp / jcc )之外的所有内容都是涉及循环计数器的关键路径循环依赖链的一部分。

    你会期望pop将不得不等待通过call / ret更新堆栈指针,但堆栈引擎会以零延迟处理这些更新。 (根据Agner Fog的microarch pdf,自从Pentium-M和AMD以来,Intel一直都是Intel,所以我假设你的CPU有一个,即使你没有说你在哪个CPU微架构上运行测试。)

    额外的call / ret仍然需要执行,但无序执行可以使关键路径指令保持其最大吞吐量。 由于这包括从dec / push + pop + 1周期的store-> load转发的延迟,所以这在任何CPU上都不是高吞吐量,并且令人惊讶的是,前端可能成为任何对齐的瓶颈。

    按照Agner Fog的说法, push - > pop延迟在Skylake上是5个周期,所以你的循环每6个周期最多只能运行一次迭代。 这是大量的无序执行的时间来运行callret指令。 瓦格纳列出了最大吞吐量call一个每3个周期的,并ret在每1个循环之一。 或AMD推土机,2个2他的表不列出有关吞吐量的任何call / ret对,所以IDK无论这些可以重叠或没有。 在AMD推土机上, mov存储/重新加载延迟是8个周期。 我认为它与push / pop大致相同。

    似乎循环顶部的不同对齐(即no_call.loop_start:导致前端瓶颈。 call版本每次迭代有3个分支:call,ret和循环分支。 请注意, ret的分支目标是在call之后的指令。 这些可能会破坏前端。 由于您在实践中看到实际的减速,所以我们必须看到每个分支的循环延迟超过1个循环。 或者对于no_call版本,单个读取/解码泡泡的时间差大于6个周期,导致实际的浪费周期将uops发布到内核的无序部分。 这很奇怪。

    猜测每个可能的uarch的实际微架构细节是多么复杂,因此让我们知道您测试的CPU是什么。

    我会提到,虽然在Skylake上的循环内部的push / pop阻止它从循环流检测器发出,并且必须每次从uop缓存中重新获取它。 英特尔的优化手册说,对于桑迪布里奇来说,循环内部的不匹配的推/停操作会阻止它使用LSD。 这意味着它可以将LSD用于具有平衡推/流的循环。 在我的测试中,Skylake不是这种情况(使用lsd.uops性能计数器),但我没有看到任何提及这是否是变化,或者SnB是否也是如此。

    而且,无条件分支总是结束uop-cache行。 normal_function:可能是normal_function:在与calljne相同的自然对齐的32B机器代码块中,可能代码块不适合uop缓存。 (只有3个uop-cache行可以为单个32B块的x86代码缓存解码的uops)。 但是这并不能解释no_call循环出现问题的可能性,所以你可能没有在Intel SnB系列微架构上运行。

    (更新,是的,有时循环运行,主要是从传统的解码( idq.mite_uops ),但通常不完全。 dsb2mite_switches.penalty_cycles通常〜8K,大概只发生在定时器中断。其中的运行call循环运行速度更快似乎与较低的idq.mite_uops相关,但在偏移= 37的情况下仍然为34M + - 63%,其中100M迭代花费了401M周期。)

    这确实是那些“不这样做”的案例之一:内联小函数,而不是在非常紧密的循环中调用它们。


    如果您push / pop除循环计数器以外的寄存器,您可能会看到不同的结果。 这将把push / pop从循环计数器中分离出来,所以会有2个独立的依赖链。 它应该加快呼叫和非呼叫版本,但可能不会同样。 它可能会使前端瓶颈更加明显。

    如果你push edxpop eax ,你应该看到一个巨大的加速,所以push / pop指令不会形成一个循环运行的依赖链。 然后额外的call / ret肯定会成为一个瓶颈。


    注意: dec ecx已经按照你想要的方式设置了ZF,所以你可以使用dec ecx / jnz 。 此外, cmp ecx,0的效率低于test ecx,ecx (更大的代码大小,并且不能在多个CPU上进行宏观保险)。 无论如何,与你的两个循环的相对性能问题完全无关。 (在函数之间缺少一个ALIGN指令意味着更改第一个函数会改变第二个循环分支的对齐方式,但是您已经探索了不同的对齐方式。)


    normal_function的调用和它的返回将被正确地预测,除了第一次,所以我不希望看到由于调用的存在而在时间上的任何差异。 因此,您看到的所有时间差异(无论更快还是更慢)都是由于其他效果(如评论中提到的那些效果)造成的,而不是您实际尝试测量的代码差异。

    链接地址: http://www.djcxy.com/p/28773.html

    上一篇: Loop with function call faster than an empty loop

    下一篇: Problems with ADC/SBB and INC/DEC in tight loops on some CPUs