assembly - amd64上“条件调用”的表现

在代码的关键部分考虑条件函数调用时,我发现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 ,我们都被迫分支。 如果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

这种方法有一些潜在的缺点:

  • 它引入了几条指令(但它们的总周期少于分支误预测惩罚)
  • 它需要写入内存(但堆栈可能已缓存?)
  • 即使没有进行调用,它总是执行2个leamov (但我的理解是无关紧要,因为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)。 这对我来说,条件调用方法大致相当(尽管我的简单分析可能存在缺陷吗?)。

至少,我通过在cmpjl之间引入几个指令的总体怀疑,我可以在jl可以被推测性地执行之前可以得到cmp的结果(从而完全阻止了分支预测) 。 虽然管道可能比这长? 这涉及到哪些领域(尽管已阅读并保留了对Agner Fog优化手册的中等深度理解),我不是很熟悉。

我的假设是对的均匀分布(阴性及阳性) num s(其中分支预测将无法预测各地分公司call ),我的“有条件呼叫”的方式将跑赢待命分支。

我写了一个线束来衡量这两种方法的表现 您可以git clone https://gist.github.com/baileyparker/8a13c22d0e26396921f501fe87f166a9make在您的计算机上运行基准测试。

这是每个方法在1,048,576个数字(均匀分布在int32_t min和max之间)的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上运行。 因此,分析的第一步是确定negate函数中的ret是否被错误预测(如早期微体系结构中会发生的那样)。 第二步是确定在总执行时间上错误预测ret指令的成本是多少。 我对KBL最接近的是CFL,我的数字与你的数字相近。 两者之间唯一相关的区别是在CFL中启用了LSD,但在KBL中禁用了LSD。 但是,在这种情况下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函数,该函数包含jlret jl指令有条件地跳转到包含retnegate函数。 jne指令用于循环。 第一列和第二列中显示的数字分别通过迭代总数和动态指令总数归一化。 我们从程序的静态结构中知道, call jlconditional_callretjne在每次迭代中都执行一次。 最内部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 ,这是错误预测的一半。

为了在conditional_call方法中测量单个ret误预测的平均成本,可以用lea/jmp序列替换ret指令,以便使用BTB而不是RAS来进行预测。 通过此更改,唯一错误预测的指令是jl 在执行时间的差别可以被认为是用于总成本的估计ret的错误预测。 在我的CFL处理器,这是每11.3次ret的错误预测。 此外, conditional_callbranch_over_call快约3%。 您对KBL的数字表明,平均成本ret错误预测是大约13个周期。 我不确定这种差异的原因是什么。 它可能不是微架构的。 我使用过gcc 7.3但你使用的是gcc 8,所以可能在代码或不同代码片段的对齐方面存在一些差异,导致我们的结果之间存在差异。

正如@fuz在评论中指出的那样,性能问题几乎肯定是由于返回地址堆栈(RAS) ,它是函数返回的专用分支预测器。

作为从jmp和手动堆栈修改中单独callret指令的优点,CPU可以满足运行代码的意图。 特别是,当我们call一个函数时,它可能会ret ,当它发生时,我们将跳回到在call之前推送的rip 换句话说, call s通常与ret配对。 CPU利用这一点来保持一个固定长度的只返回地址堆栈,称为返回地址堆栈(RAS)。 除了将返回地址推送到实际的内存堆栈之外, call指令还会将其推送到RAS。 这样,当遇到ret时,CPU可以弹出RAS(这比实际堆栈的内存访问快得多)并且推测性地执行返回。 如果事实证明从RAS弹出的地址是从堆栈弹出的地址,则CPU继续没有惩罚。 但是,如果RAS预测错误的返回地址,则发生管道刷新,这是昂贵的。

我原来的直觉是条件指令会更好,因为它们会给比较结果留出时间在跳转之前到达。 然而,无论可能提供什么好处,有一个不平衡的jmp / ret (我的条件调用用jmp替换call ,但被调用的函数仍然使用了ret )导致RAS可能总是预测错误的返回地址(因此我的方法,尽管最初试图避免这种情况,导致更多的管道停滞)。 RAS的加速比我的“优化”更重要,因此分支方法优于条件调用方法。

根据一些经验结果,不匹配的callret (特别是使用jmp + ret )比正确配对callret需要多5-6倍的周期。 一些卫生巾数学表明,对于1,048,576次调用,3.1GHz的+21周期的惩罚会增加总运行时间约7.1ms。 观察到的放缓程度低于此。 这可能是条件指令延迟跳跃直到条件准备好的组合以及跳跃在存储器中的固定位置之间振荡的事实(其他分支预测器可能变得善于预测)。

转载请注明来自askonline.tech,本文标题:assembly - amd64上“条件调用”的表现


 Top