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

11 浏览
0 Comments

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

我使用一些汇编和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 
#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;
}

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

162
181

但如果链接的顺序相反为gcc extern.o intern.o,我得到的输出更接近于:

162

130

它们之间的差异非常令人惊讶,但这不是我要问的问题。(相关问题在这里

我要问的问题是,在第二次运行中,带有函数调用的循环为什么比没有函数调用的循环更快,为什么函数调用的成本似乎是负的。

编辑:

仅在评论中尝试的一些事情:

  • 在编译后的字节码中,函数调用没有被优化掉。
  • 调整函数和循环的对齐方式,使其在4到64字节边界上都没有加速no_call,尽管有些对齐方式会减慢normal_call的速度
  • 让CPU/操作系统多次调用函数而不仅仅是一次,不会对测量的时间长度产生显著影响,更改调用的顺序或分开运行也不会产生显著影响
  • 运行时间更长不会影响比例,例如运行时间更长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 ; 这是我正在改变的数字

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

如果(20 <= offset mod 128 <= 31),则输出为(近似):
162
131
否则
162(+/- 10)
162(+/- 10)

不确定如何解释这个结果,但这是我到目前为止发现的情况。

第二次编辑:

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

30
125

这表明这是最昂贵的部分。两次堆栈对齐方式相同,所以这不是差异的原因。我最好的猜测是,一些硬件可能在push之后期望有一个调用或类似的操作,但我不知道是否有类似的操作。

0
0 Comments

更新:Skylake的存储/加载延迟低至3个周期,但前提是“时机恰到好处”。存储转发依赖链中的连续加载如果自然地间隔3个或更多个周期,则会体验到更快的延迟(例如,在循环中使用4个imul eax,eax,mov [rdi], eax / mov eax, [rdi]的情况下,每次迭代的周期数从12增加到15)。但是,如果加载的密度超过这个范围,就会遇到某种类型的争用,每个迭代需要大约4.5个周期。非整数的平均吞吐量也是一个重要的线索,表明存在一些异常情况。

我在32B向量中也看到了相同的效果(最佳情况下为6.0个周期,连续运行为6.2至6.9个周期),但128B向量始终在5.0个周期左右。详情请参见Agner Fog的论坛上的细节

更新2:添加冗余赋值可以加快编译时未进行优化的代码的速度,这里有一个例子,以及2013年的一篇博客文章表明,所有Sandybridge系列的CPU都存在这种效应。

Skylake的连续存储转发延迟比以前的微架构提高了1个周期,但在加载无法立即执行时的变异性类似。


如果正确(错位)对齐,循环中的额外调用(call)实际上可以帮助Skylake观察到从push到pop的较低存储转发延迟。我使用perf计数器(Linux的perf stat -r4)和YASM重现了这个现象。(我听说在Windows上使用perf计数器不太方便,而且我也没有Windows开发机器。幸运的是,操作系统对答案并不重要;任何人都可以使用VTune或其他工具在Windows上重现我的perf计数器结果。)

在align 128指定的位置上,我看到偏移量为0..10、37、63-74、101和127的情况下都出现了更快的时间。 L1I高速缓存行为64B,uop缓存关心32B边界。看起来与64B边界对齐有关。

没有调用的循环始终为5个周期,但调用的循环可以从通常的几乎5个周期降至4个周期每次迭代。我在偏移量为38的情况下看到了较慢的性能(每次迭代5.68+-8.3%个周期)。根据perf stat -r4的结果(执行4次并取平均值),其他点也有一些小的问题,例如5.17个周期+-3.3%。

这似乎是前端没有提前排队那么多uop的结果,导致后端在从push到pop的存储转发方面具有较低的延迟。

我不知道使用相同的地址重复进行存储转发是否会使速度变慢(例如,在相应的存储数据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

子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源代码直接移植过来,没有对汇编进行任何优化。

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来操作循环计数器,因此除了call和ret指令(以及cmp/jcc指令)之外的所有指令都是关键路径循环传递的依赖链的一部分。

您可能会期望pop指令必须等待由call/ret更新的堆栈指针,但是堆栈引擎可以在零延迟下处理这些更新。(根据Agner Fog的微架构pdf,自Pentium-M以来的英特尔处理器和K10以来的AMD处理器都具有堆栈引擎,所以我假设您的CPU也有一个,尽管您没有提到您在哪个CPU微架构上进行了测试。)

额外的call/ret仍然需要执行,但是乱序执行可以使关键路径指令以其最大吞吐量运行。由于这包括存储-加载转发的延迟以及1个周期的dec延迟,这在任何CPU上都不是高吞吐量,并且前端是否成为瓶颈是令人惊讶的,无论对齐如何。

Skylake的push/pop延迟为5个周期,根据Agner Fog的数据,因此在该微架构上,您的循环每6个周期最多运行一次。这足够的时间让乱序执行运行call和ret指令。Agner列出了每3个周期的call的最大吞吐量,ret为每1个周期。或者在AMD Bulldozer上为2和2。他的表中没有列出关于call/ret对的吞吐量的任何内容,所以我不知道它们是否可以重叠。在AMD Bulldozer上,使用mov的存储/加载延迟为8个周期。我假设使用push/pop的存储/加载延迟也大致相同。

看起来不同的顶部对齐方式(即no_call.loop_start)会导致前端瓶颈。call版本的每次迭代有3个分支:call、ret和loop-branch。请注意,ret的分支目标是call之后的指令。每个分支都可能破坏前端。由于您在实践中看到了真正的减速效果,所以我们必须看到每个分支超过1个周期的延迟。对于no_call循环,可能会出现一个比大约6个周期更差的单个fetch/decode气泡,导致在将uop发布到核心的乱序部分时实际浪费一个周期。这很奇怪。

这真的是一个“不要这样做”的情况:在非常紧密的循环中内联微小的函数,而不是从中调用它们。


如果您将寄存器而不是循环计数器push/pop,可能会看到不同的结果。这将使push/pop指令与循环计数器分开,因此将有两个单独的依赖链。这应该加快调用和no_call版本的速度,但可能不会完全相同。这可能只会使前端瓶颈更加明显。

如果您将push edx但pop eax,那么push/pop指令就不会形成循环传递的依赖链。然后,额外的call/ret肯定会成为瓶颈。


副注:dec ecx已经设置了ZF,所以您可以直接使用dec ecx/jnz。此外,cmp ecx,0比test ecx,ecx更低效(代码大小更大,不能在尽可能多的CPU上宏融合)。无论如何,这与您的两个循环的相对性能问题无关。(由于没有在函数之间添加ALIGN指令,因此更改第一个函数将更改第二个函数中的循环分支的对齐方式,但您已经尝试了不同的对齐方式。)

在这个问题中,对您的两个循环的相对性能进行了实验,并通过对齐方式的实验来探索问题的原因。

0
0 Comments

循环中调用函数的速度比空循环快的原因是因为即使在第一次之外的每一次调用和返回都能正确地被预测,所以我不会因为调用的存在而期望看到任何由于调用而引起的时间差异。因此,你所看到的所有时间差异(无论是更快还是更慢)都是由其他影响(如评论中提到的那些)而不是你实际尝试测量的代码差异引起的。

即使是正确预测的分支也会导致指令获取延迟。如果循环体不是那么慢,你将会看到更大的效果。

解决方法:优化循环体的执行效率。

0