函数调用循环比空循环更快

Loop with function call faster than an empty loop

我将一些程序集与一些 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)

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

编辑: 只是想提一下评论中尝试过的一些事情:

此外,在修改汇编代码以按字节对齐后,我测试了给函数集额外的偏移量并得出了一些更奇怪的结论。这是更新后的代码:

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 字节,这是我发现的。

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 store/reload 延迟低至 3c,但前提是时机正确。自然间隔 3 个或更多周期的存储转发依赖链中涉及的连续加载将经历更快的延迟(例如,循环中有 4 imul eax,eax,仅 mov [rdi], eax / mov eax, [rdi]将每次迭代的循环计数从 12 增加到 15 个循环。)但是当允许负载执行得比这更密集时,就会出现某种类型的争用,每次迭代大约有 4.5 个循环。非整数平均吞吐量也是一个重要线索,表明存在异常。

我看到 32B 向量的效果相同(最佳情况 6.0c,连续 6.2 到 6.9c),但 128b 向量始终在 5.0c 左右。参见 details on Agner Fog's forum

更新 2: and a 2013 blog post 表示 此效果存在于所有 Sandybridge 家族 CPUs.

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


通过正确(错误)对齐,循环中的额外 call 实际上可以帮助 Skylake 观察到从推送到弹出的较低存储转发延迟。我能够使用 YASM 通过性能计数器 (Linux perf stat -r4) 重现这一点。 (我听说在 Windows 上使用性能计数器不太方便,而且我也没有 Windows 开发机器。幸运的是 OS 与答案并不相关;任何人都应该能够在 Windows 上使用 VTune 或其他工具重现我的性能计数器结果。)

我在 offset = 0..10、37、63-74、101 和 127 处看到了更快的时间,之后是在指定位置的 align 128这个问题。 L1I 缓存行是 64B,uop-cache 关心 32B 边界。看起来相对于 64B 边界的对齐才是最重要的。

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

这似乎是前端之间的交互,没有提前排队那么多 uops,导致后端从推送到弹出的存储转发延迟较低。

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


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

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

asm-link是一个脚本,运行s yasm -felf32 -Worphan-labels -gdwarf2 call-tight-loop.asm "$@" && ld -melf_i386 -o call-tight-loop call-tight-loop.o,然后运行s 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% )

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

你 push/pop 你的循环计数器,所以除了 callret 指令(以及 cmp/jcc)之外的所有内容都是涉及循环计数器的关键路径循环携带依赖链。

您预计 pop 必须等待 call/ret 对堆栈指针的更新,但是 . (Intel since Pentium-M, AMD since K10, according to Agner Fog's microarch pdf,所以我假设你的 CPU 有一个,即使你没有说什么 CPU 微架构你 运行 你的测试。)

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

根据 Agner Fog 的说法,

push->pop Skylake 上的延迟是 5 个周期,因此在那个 uarch 上,你的循环最多只能 运行 每 6 个周期迭代一次。 这是乱序执行 运行 callret 指令的充足时间。 Agner 列出了 call 的最大吞吐量为每 3 个周期一个,ret 为每 1 个周期一个。或者在 AMD Bulldozer 上,2 和 2。他的表没有列出任何关于 call/ret 对的吞吐量的信息,所以我不知道它们是否可以重叠。在 AMD Bulldozer 上,store/reload 与 mov 的延迟是 8 个周期。我认为它与 push/pop.

大致相同

循环顶部的不同对齐方式(即 no_call.loop_start:)似乎导致了前端瓶颈。 call 版本每次迭代有 3 个 b运行ches:调用、ret 和循环 b运行ch。请注意,ret 的 b运行ch 目标是 call 之后的指令。这些中的每一个都可能破坏前端。由于您在实践中看到实际减速,我们必须看到每个 b运行ch 超过 1 个周期延迟。或者对于 no_call 版本,单个 fetch/decode 气泡比大约 6 个周期更糟糕,导致在向核心的无序部分发出 uops 时实际浪费了一个周期。真奇怪。

要猜测每个可能的 uarch 的实际微体系结构细节是什么太复杂了,所以请告诉我们您测试的 CPU。

我要提到的是,Skylake 上循环内的 push/pop 阻止它从循环流检测器发出,并且每次都必须从 uop 缓存中重新获取。 Intel's optimization manual 表示对于 Sandybridge,循环内不匹配的 push/pop 会阻止它使用 LSD。这意味着它可以将 LSD 用于具有平衡 push/pop 的循环。在我的测试中,Skylake 的情况并非如此(使用 lsd.uops 性能计数器),但我没有看到任何提及这是否是一个变化,或者 SnB 是否真的也是这样。

此外,无条件 b运行ches 总是结束一个 uop-cache 行。有可能 normal_function: 在与 calljne 相同的自然对齐的 32B 机器代码块中,代码块可能不适合 uop 缓存。 (对于单个 32B 块的 x86 代码,只有 3 个 uop-cache 行可以缓存解码后的 uops)。但这并不能解释 no_call 循环出现问题的可能性,因此您可能不会 运行 在英特尔 SnB 系列微体系结构上使用。

(更新,是的,循环有时 运行 主要来自遗留解码(idq.mite_uops),但通常不是唯一的。dsb2mite_switches.penalty_cycles 通常是 ~8k,并且可能只发生在计时器中断上。call 循环 运行s 更快的 运行s 似乎与较低的 idq.mite_uops 相关,但偏移量 = 仍然是 34M +- 63% 37 种情况,其中 100M 次迭代花费了 401M 个周期。)

这确实是 "don't do that" 案例之一:内联微型函数,而不是从非常紧凑的循环中调用它们。


如果您 push/pop 寄存器不是循环计数器,您可能会看到不同的结果。这会将 push/pop 与循环计数器分开,因此会有 2 个独立的依赖链。它应该加速 call 和 no_call 版本,但可能不一样。它只会使前端瓶颈更加明显。

如果你 push edxpop eax,你应该会看到一个巨大的加速,所以 push/pop 指令不会形成循环携带的依赖链。那么多余的call/ret肯定是瓶颈


旁注:dec ecx 已经按照您想要的方式设置了 ZF,因此您可以只使用 dec ecx / jnz。此外,(更大的代码大小并且不能在尽可能多的 CPU 上进行宏融合)。无论如何,与关于两个循环的相对性能的问题完全无关。 (函数之间缺少 ALIGN 指令意味着更改第一个指令会改变第二个循环 b运行ch 的对齐方式,但您已经探索了不同的对齐方式。)

对 normal_function 的调用和它的 return 每次都会被正确预测,除了第一次,所以我不希望看到 any 由于呼叫的存在而导致的时间差异。因此,您看到的所有时间差异(无论是更快还是更慢)都是由于其他影响(例如评论中提到的)而不是您实际尝试测量的代码差异。