循环调用函数比空循环快。
循环调用函数比空循环快。
我使用一些汇编和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.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 ; 这是我正在改变的数字
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 ecx
和pop ecx
,输出变为:
30 125
这表明这是最昂贵的部分。两次堆栈对齐方式相同,所以这不是差异的原因。我最好的猜测是,一些硬件可能在push之后期望有一个调用或类似的操作,但我不知道是否有类似的操作。
更新: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指令,因此更改第一个函数将更改第二个函数中的循环分支的对齐方式,但您已经尝试了不同的对齐方式。)
在这个问题中,对您的两个循环的相对性能进行了实验,并通过对齐方式的实验来探索问题的原因。