Bai*_*ker 10 x86 assembly x86-64 branch-prediction
在代码的关键部分考虑条件函数调用时,我发现gcc和clang都会在调用中分支.例如,对于以下(通常是微不足道的)代码:
int32_t __attribute__((noinline)) negate(int32_t num) {
return -num;
}
int32_t f(int32_t num) {
int32_t x = num < 0 ? negate(num) : num;
return 2*x + 1;
}
GCC和clang都基本上编译如下:
.global _f
_f:
cmp edi, 0
jg after_call
call _negate
after_call:
lea rax, [rax*2+1]
ret
这让我想到:如果x86有一个像ARM这样的条件调用指令怎么办？想象一下,如果有这样的指令"ccall cc "与语义如cmov cc.然后你可以这样做:
.global _f
_f:
cmp edi, 0
ccalll _negate
lea rax, [rax*2+1]
ret
虽然我们无法避免分支预测,但我们确实消除了分支.也就是说,在实际的GCC/clang输出中,我们被迫分支,无论是否num < 0.如果num < 0我们必须分支两次.这似乎很浪费.
现在这样的指令在amd64中不存在,但我设计了一种模拟这种指令的方法.我通过分解call func其组成部分来做到这一点:( push rip技术上很好[rip+label_after_call_instruction])然后jmp func.我们可以使jmp条件,但没有条件push.我们可以通过计算[rip+label_after_call_instruction]并将其写入堆栈中的适当位置来模拟这一点,然后rsp如果我们计划调用该函数(实际上"推送"它[rip+label_after_call_instruction])则有条件地更新.它看起来像这样:
.global _f
_f:
cmp edi, 0
# ccalll _negate
lea rax, [rip+after_ccall] # Compute return address
mov [rsp-8], rax # Prepare to "push" return address
lea rax, [rsp-8] # Compute rsp (after push)
cmovl rsp, rax # Conditionally push (by actually changing rsp)
jl _negate # "Conditional call"
after_ccall:
lea rax, [rax*2+1]
ret
这种方法有一些潜在的缺点:
lea秒,mov即使没有进行调用(但我理解这并不重要,因为cmov cc占用与mov相同的周期数,例如)为了检查每种方法的属性,我运行了关键部分iaca.如果你安装了它(并且你在下面克隆我的基准要点),你可以跑去make iaca看看.传递IACAFLAGS='-arch=...'指定不同的拱门.
分支的输出方法:
Intel(R) Architecture Code Analyzer Version - v3.0-28-g1ba2cbb build date: 2017-10-30;16:57:45
Analyzed File - ./branch_over_call_iaca.o
Binary Format - 64Bit
Architecture - SKL
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 0.82 Cycles Throughput Bottleneck: Dependency chains
Loop Count: 36
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
--------------------------------------------------------------------------------------------------
| Cycles | 0.5 0.0 | 0.0 | 0.3 0.0 | 0.3 0.0 | 1.0 | 0.0 | 0.5 | 0.3 |
--------------------------------------------------------------------------------------------------
DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3)
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion occurred
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis
| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
-----------------------------------------------------------------------------------------
| 1 | 0.5 | | | | | | 0.5 | | jnle 0x6
| 4^# | | | 0.3 | 0.3 | 1.0 | | | 0.3 | call 0x5
Total Num Of Uops: 5
并且条件调用方法的输出:
Intel(R) Architecture Code Analyzer Version - v3.0-28-g1ba2cbb build date: 2017-10-30;16:57:45
Analyzed File - ./conditional_call_iaca.o
Binary Format - 64Bit
Architecture - SKL
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 1.94 Cycles Throughput Bottleneck: Dependency chains
Loop Count: 35
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
--------------------------------------------------------------------------------------------------
| Cycles | 1.0 0.0 | 1.0 | 0.5 0.0 | 0.5 0.0 | 1.0 | 1.0 | 1.0 | 0.0 |
--------------------------------------------------------------------------------------------------
DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3)
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion occurred
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis
| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
-----------------------------------------------------------------------------------------
| 1 | | 1.0 | | | | | | | lea rax, ptr [rip]
| 2^ | | | 0.5 | 0.5 | 1.0 | | | | mov qword ptr [rsp-0x8], rax
| 1 | | | | | | 1.0 | | | lea rax, ptr [rsp-0x8]
| 1 | 1.0 | | | | | | | | cmovl rsp, rax
| 1 | | | | | | | 1.0 | | jl 0x6
Total Num Of Uops: 6
我看起来像条件调用方法似乎使用更多的硬件.但我发现有趣的是条件方法只有1个uop(分支结束方法有5个uop).我想这是有道理的,因为在引擎盖下,调用变成了push和jmp(并且push变成了rsp数学和一个内存mov).这对我来说,条件调用方法大致相当(尽管我的简单分析可能存在缺陷吗？).
至少,我的总体怀疑是通过在cmp和之间引入几条指令jl,我可以在推测性地执行cmp之前使得结果可用jl(从而完全阻止分支预测).虽然管道可能比这长？这涉及到哪些领域(尽管已经阅读并保留了对Agner Fog优化手册的中等深度理解),我不是很熟悉.
我的假设是,对于(负和正)nums(其中分支预测将无法预测周围的分支)的均匀分布call,我的"条件调用"方法将优于呼叫周围的分支.
我写了一个线束来衡量这两种方法的表现.你可以git clone https://gist.github.com/baileyparker/8a13c22d0e26396921f501fe87f166a9和make你的机器上运行的基准.
这是1,048,576个数字(均匀分布在int32_t最小值和最大值之间)的每个方法的100次迭代的运行时间.
| CPU | Conditional Call | Branch Over |
|-------------------------------------------|-----------------:|------------:|
| Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz | 10.9872 ms | 8.4602 ms |
| Intel(R) Xeon(R) CPU E3-1240 v6 @ 3.70GHz | 8.8132 ms | 7.0704 ms |
这些结果在运行中是一致的,虽然通过增加数组大小(或迭代次数)来放大,但总是获胜.
我也尝试重新排序条件调用步骤(首先计算和条件更新rsp,然后写入堆栈),但这样做的表现相似.
我错过了什么硬件细节(或误解)解释了这一点？根据我的计算,额外的指令在6-7个周期附近增加,但是一个分支误预测成本为15.因此,平均一半的数字被预测为错误,因此每次迭代花费15/2个周期(对于分支超过接近)并且总是6-条件调用的7个周期.来自iaca的uops表明这方面的方法更加接近.那么,性能是否应该更接近？我的示例代码是否太做作/简短？我的基准测试技术不适合这种低级关键部分测试吗？有没有办法重新排序/更改条件调用,使其更高性能(可能更好或与分支方法相当)？
tl; dr为什么我的条件调用代码(第四个代码片段)比我的基准测试中的 gcc/clang(条件跳转call)(第二个代码片段)(第一个代码段中的代码)表现更差？
您可以准确地确定为什么该conditional_call方法比 慢branch_over_call。您已在两个 KBL 处理器上完成了实验，但您引用的博客文章并未讨论 RAS 如何在 KBL 上工作。因此，分析的第一步是确定函数ret中的是否negate被错误预测（就像早期微架构上会发生的情况一样）。第二步是确定错误预测该ret指令对总执行时间的成本是多少。我拥有的最接近 KBL 的东西是 CFL，结果我的数据与你的很接近。两者之间唯一相关的区别是 LSD 在 CFL 中启用，但在 KBL 中禁用。然而，在这种情况下，LSD 是无关紧要的，因为call循环中的指令会阻止 LSD 检测任何循环。您还可以轻松地在 KBL 上重复相同的分析。
有多种方法可以分析分支指令的行为。但在这种特殊情况下，代码足够简单，事件计数方法可以显示我们需要的有关每个静态分支指令的所有信息。
性能BR_INST_RETIRED_*事件可用于对引退的动态分支指令的总数以及包括条件、调用和返回的特定类型的引退的分支指令的总数进行计数。这些BR_MISP_RETIRED_*事件可用于计算总错误预测、总条件错误预测和总呼叫错误预测。
完整的控制发光图conditional_call如下所示：
total misp
call 1 0
jl 1 0.5
ret 0.5 1
ret 1 0
jne 1 0
第一call条指令调用该conditional_call函数，其中包含jl和ret。该jl指令有条件地跳转到negate包含ret. 该jne指令用于for循环。第一列和第二列中显示的数字分别通过迭代总数和动态指令总数进行归一化。从程序的静态结构中我们知道call，jl、conditional_call、 s ret、 和jne在每次迭代中都会执行一次。最里面的部分仅在分支被获取ret时执行。使用性能事件，我们可以计算执行的返回指令的总数，并从中减去迭代的总数，以获得最内层指令的执行jl次数。因为输入是根据均匀分布随机化的，所以最里面的部分被执行一半的时间ret也就不足为奇了。ret
指令call永远不会被错误预测。jne除了指令的最后一次执行（退出循环的地方）之外，指令也永远不会被错误预测。因此，我们可以将条件错误预测的总数归因于该jl指令。可以从错误预测的总数中减去它，以获得可以归因于任一或两个返回指令的返回错误预测的数量。ret当第一个错误预测失败ret或使 RAS 失准时，第二个可能会做出错误预测。确定第二个是否ret被错误预测的一种方法是使用 的精确采样BR_MISP_RETIRED.ALL_BRANCHES。另一种方法是使用您引用的博客文章中描述的方法。确实，只有最内心的预测ret是错误的。jl一半时间预测错误的事实表明，指令要么被预测为总是被执行，要么总是被预测为不被执行。
完整的控制发光图branch_over_call如下所示：
total misp
call 1 0
jg 1 0.5
call 0.5 0
ret 0.5 0
ret 1 0
jne 1 0
唯一被错误预测的指令是jg，它有一半的时间被错误预测。
衡量单个项目的平均成本ret为了测量该方法中conditional_call，ret可以用序列替换指令lea/jmp，以便使用 BTB 而不是 RAS 进行预测。通过此更改，唯一被错误预测的指令是jl。执行时间的差异可以被视为对ret错误预测总成本的估计。在我的 CFL 处理器上，每次错误预测大约需要 11.3 个周期ret。此外，conditional_call也变得比 快 3% 左右branch_over_call。您在 KBL 上的数据表明，错误预测的平均成本ret约为 13 个周期。我不确定这种差异的原因是什么。它可能不是微架构。我使用了 gcc 7.3，但您使用了 gcc 8，因此可能代码中存在一些差异或不同代码片段的对齐方式导致我们的结果之间存在差异。