具有函数调用的循环比空循环更快

Question

我使用以下程序集和c源（分别使用fasm和gcc）将一些程序集与一些c链接起来，以测试函数调用的成本

组件：

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

他们的不同令人惊讶，但这不是我要问的问题。（此处有相关问题）

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

编辑：只是为了提到评论中尝试的一些事情：

• 在编译的字节码中，函数调用没有被优化掉

此外，在修改html" target="_blank">汇编代码以按字节对齐后，我测试了给函数集一个额外的偏移量，得出了一些更奇怪的结论。以下是更新的代码：

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字节的对齐，至少在我的机器上是这样。通过偏移字节来偏移程序，这是我发现的。

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

162
131

else

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

一点也不确定该怎么做，但这就是我目前发现的

编辑2：

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

30
125

这表明这是其中最昂贵的部分。两次堆栈对齐都是相同的，所以这不是差异的原因。我最好的猜测是，不知何故，硬件经过优化，可以期待推送后的调用或类似的东西，但我不知道有任何类似的东西

Answer 1

除了第一次调用外，对normal_函数的调用和它的返回每次都会被正确预测，因此我预计不会因为调用的存在而看到任何时间上的差异。因此，您看到的所有计时差异（无论是快还是慢）都是由于其他影响（例如注释中提到的那些影响），而不是您实际尝试测量的代码差异。

Answer 2

更新：Skylake存储/重新加载延迟低至3c，但前提是时机正确。存储转发依赖链中涉及的自然间隔为3个或更多周期的连续加载将经历更快的延迟（例如，使用4imul eax，循环中的eax，mov[rdi]，eax/mov eax，[rdi]每次迭代只需要循环计数从12到15个周期），但是当允许加载执行得比这更密集时，会遇到某种类型的争用，每次迭代大约会获得4.5个周期。非整数平均吞吐量也是一个很大的线索，表明有一些不寻常的事情。

我看到32B向量（最佳情况6.0c，背靠背6.2到6.9c）也有同样的效果，但128b向量总是在5.0c左右。

更新2:2013年的一篇博客文章表明，在编译时添加冗余分配可以加快代码的速度，这一效果在所有Sandybridge系列CPU上都存在。

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

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

在偏移量=0时，我看到了更快的时间。。10、37、63-74、101和127在问题中指定的位置对齐128。L1I缓存线为64B，uop缓存关心32B边界。看起来，相对于64B边界的对齐才是最重要的。

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

这似乎是前端之间的一种交互，前端没有在前面排队等待如此多的UOP，导致后端具有较低的从推送到弹出的存储转发延迟。

IDK如果重复使用同一地址进行存储转发会使其速度变慢（在相应的存储数据UOP之前已经执行了多个存储地址UOP），或者什么。

测试代码：bash要构建的shell循环

(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）在subshell中是一种在重定向到日志文件时记录命令及其输出的方便方法。

asm link是一个运行yasm-felf32-Worphan-labels-gdwarf2调用紧密循环的脚本。asm“$@”

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

快速调用运行的样本输出：

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

您按下/弹出循环计数器，因此除了调用和ret指令（以及cmp/jcc）之外的所有内容都是涉及循环计数器的关键路径循环承载依赖链的一部分。

您可能希望，pop必须等待通过调用ret更新堆栈指针，但堆栈引擎以零延迟处理这些更新。（根据阿格纳·福格（Agner Fog）的microach pdf，英特尔从奔腾M开始，AMD从K10开始，所以我假设你的CPU有一个，尽管你没有说你在什么CPU微体系结构上运行测试。）

额外的调用/ret仍然需要执行，但乱序执行可以保持关键路径指令以其最大吞吐量运行。由于这包括存储的延迟-

推送-

似乎循环顶部的不同对齐方式（即无调用。循环开始：）导致了前端瓶颈。调用版本在每次迭代中有3个分支：调用、ret和循环分支。注意，ret的分支目标是调用后的指令。每一个都可能会破坏前端。由于您在实践中看到了实际的减速，我们必须看到每个分支的周期延迟超过1个。或者，对于无调用版本，单个获取/解码气泡比大约6个周期差，导致在向核心的无序部分发出UOP时实际浪费了一个周期。这太奇怪了。

猜测每个可能的uarch的实际微体系结构细节太复杂了，所以让我们知道您测试的是什么CPU。

不过，我要提到的是，Skylake上的循环内的推送阻止了它从循环流检测器发出，并且每次都必须从uop缓存中重新获取。英特尔的优化手册说，对于Sandybridge，循环内不匹配的推送/弹出会阻止它使用LSD。这意味着它可以将LSD用于具有平衡推送/弹出的循环。在我的测试中，Skylake上的情况并非如此（使用lsd.uops性能计数器），但我没有看到任何关于这是否是一个变化的提及，也没有看到SnB实际上是否也是这样。

此外，无条件分支总是结束一个uop-cache行。可能normal_function：与调用和jne在同一个自然对齐的32B机器代码块中，可能代码块不适合uop缓存。（只有3个uop-cache行可以缓存单个32Bx86html" target="_blank">代码块的解码uops）。但这并不能解释no_call循环出现问题的可能性，所以您可能不是在英特尔SnB系列微架构上运行的。

（更新，是的，循环有时主要从传统解码运行（idq.mite\u uops），但通常不是唯一的<代码>dsb2mite_开关。惩罚周期通常约为8k，并且可能仅在计时器中断时发生。调用循环运行更快的运行似乎与较低的idq相关。mite_uops，但在偏移量=37的情况下，仍为34M-63%，其中100M迭代需要401M个周期。）

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

如果推送循环计数器以外的寄存器，可能会看到不同的结果。这将推送/弹出与循环计数器分离，因此将有两个独立的依赖链。它应该同时加速call和no_call版本，但可能没有同等的速度。这只会使前端瓶颈更加明显。

如果您推送edx，但推送eax，您应该会看到巨大的加速，因此推送/弹出指令不会形成循环携带的依赖链。那么额外的调用ret肯定会成为瓶颈。

旁注：dec-ecx已经按您想要的方式设置了ZF，所以您可以只使用dec-ecx/jnz。此外，cmp ecx，0的效率低于测试ecx，ecx（更大的代码大小，无法在尽可能多的CPU上进行宏融合）。无论如何，这与两个循环的相对性能问题完全无关。（函数之间缺少ALIGN指令意味着更改第一个指令会更改第二个循环分支的对齐方式，但您已经探索了不同的对齐方式。）