“条件调用”在 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 这样的条件调用指令会怎样？想象一下如果有这样一条指令“ccallcc" 具有像 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

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

• 它引入了几条指令（但它们的总周期数少于分支错误预测惩罚）
• 它需要写入内存（但堆栈可能已缓存？）
• 它总是执行2leas and mov即使没有拨打电话（但我的理解是这并不重要，因为 cmovcc例如，与 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 math和内存mov）。这对我来说意味着条件调用方法大约是等效的（尽管我的简单化分析可能在这里有缺陷？）。

至少，我的总体怀疑是通过在cmp and jl，我会让结果成为可能cmp将在之前可用jl可以推测性地执行（从而完全阻止分支预测）。尽管管道可能比这更长？这涉及到的领域（尽管已经阅读并保持了中等深度的理解）Agner Fog 的优化手册）我不是很熟悉。

我的假设是，对于（负和正）的均匀分布nums （其中分支预测将无法预测call）我的“条件调用”方法将优于围绕调用的分支。

我写了一个利用工具对这两种方法的性能进行基准测试。你可以git clone https://gist.github.com/baileyparker/8a13c22d0e26396921f501fe87f166a9 and make在您的机器上运行基准测试。

以下是对 1,048,576 个数字（均匀分布在int32_t最小值和最大值）。

|                    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 in the negate函数是否被错误预测（就像早期微架构上会发生的情况一样）。第二步是确定错误预测的成本是多少ret总执行时间的指令。我拥有的最接近 KBL 的东西是 CFL，结果我的数据与你的很接近。两者之间唯一相关的区别是 LSD 在 CFL 中启用，但在 KBL 中禁用。然而，LSD 在这种情况下是无关紧要的，因为call循环中的指令可防止 LSD 检测到任何循环。您还可以轻松地在 KBL 上重复相同的分析。

有多种方法可以分析分支指令的行为。但在这种特殊情况下，代码足够简单，事件计数方法可以显示我们需要的有关每个静态分支指令的所有信息。

The BR_INST_RETIRED_*性能事件可用于计算退休的动态分支指令的总数以及退休的特定类型的分支指令（包括条件、调用和返回）的总数。这BR_MISP_RETIRED_*events 可用于计算总错误预测、总条件错误预测和总呼叫错误预测。

完整的控制辉光图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 and ret. The jl指令有条件跳转到negate函数，其中包含ret. The jne指令用于for循环。第一列和第二列中显示的数字分别通过迭代总数和动态指令总数进行归一化。从程序的静态结构我们知道call, jl, conditional_call's ret, and jne在每次迭代中都执行一次。最里面的ret仅当执行jl分支被采取。使用性能事件，我们可以计算执行的返回指令的总数，并从中减去迭代的总数，以获得最内层的次数ret被执行。因为输入是根据均匀分布随机化的，所以最内部的ret执行了一半的时间。

The 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，因此可能代码中存在一些差异或不同代码片段的对齐方式导致了我们的结果之间的差异。