慢跳转指令

Question

跟进我的问题 , I started to measure the costs of instructions. I'm aware that this have been done multiple times (e.g. Agner Fog)，但我这样做是为了娱乐和自学。

我的测试代码非常简单（为了简单起见，这里是伪代码，实际上是在汇编程序中）：

for(outer_loop=0; outer_loop<NO;outer_loop++){
    operation  #first
    operation  #second
    ...
    operation #NI-th
}

但有些事情还是要考虑的。

如果循环内部很大（大NI>10^7），整个循环的内容放不进指令缓存，因此必须一遍又一遍地加载，使速度RAM 定义执行所需的时间。例如，对于较大的内部部分，xorl %eax, %eax（2 个字节）比 xorq %rax, %rax（3 个字节）快 33%。
如果 NI 很小并且整个循环很容易放入指令缓存中，那么 xorl %eax, %eax 和 xorq %rax, %rax 的速度同样快，每个时钟周期可以执行 4 次。

然而，这个简单的模型不适用于 jmp-指令。对于 jmp-指令，我的测试代码如下所示：

for(outer_loop=0; outer_loop<NO;outer_loop++){
    jmp .L0
    .L0: jmp .L1
    L1: jmp L2
    ....
}

结果是：

对于 "large" 循环大小（已经为 NI>10^4）我测量了 4.2 ns/jmp-指令（相当于从 RAM 加载 42 个字节或大约 12 个时钟周期我的机器）。
对于小循环大小 (NI<10^3)，我测量了 1 ns/jmp- 指令（大约 3 个时钟周期，这听起来很合理 - Agner Fog 的 tables 显示成本2 个时钟周期）。

指令jmp LX使用2字节eb 00编码。

因此，我的问题是： "large" 循环中 jmp 指令的高成本的解释是什么？

PS: 如果您想在您的机器上试用，您可以从 here 下载脚本，只需运行 sh jmp_test.sh 在 src-文件夹中。

编辑：实验结果证实了彼得的 BTB 尺寸理论。

以下 table 显示不同 ǸI 值（相对于 NI=1000）的每条指令的周期数：

|oprations/ NI        | 1000 |  2000|  3000|  4000|  5000| 10000|
|---------------------|------|------|------|------|------|------|
|jmp                  |  1.0 |  1.0 |  1.0 |  1.2 |  1.9 |   3.8|
|jmp+xor              |  1.0 |  1.2 |  1.3 |  1.6 |  2.8 |   5.3|
|jmp+cmp+je (jump)    |  1.0 |  1.5 |  4.0 |  4.4 |  5.5 |   5.5|
|jmp+cmp+je (no jump) |  1.0 |  1.2 |  1.3 |  1.5 |  3.8 |   7.6|

可见：

对于 jmp 指令，（尚未知）资源变得稀缺，这导致 ǸI 大于 4000 的性能下降。
此资源不与 xor 等指令共享 - 如果 jmp 和 xor 在之后执行，性能下降仍然持续 NI 大约 4000彼此。
但如果进行跳跃，此资源将与 je 共享 - jmp+je 之后，资源变得稀缺 NI 大约 2000 .
然而，如果 je 根本不跳，资源又一次变得稀缺 NI 大约 4000（第 4 行）。

Matt Godbolt's branch-prediction reverse engineering articles确定分支目标缓存容量为4096个条目。这是非常有力的证据，表明 BTB 未命中是观察到的小型和大型 jmp 循环之间吞吐量差异的原因。

Answer 1

TL:DR：我目前的猜测是运行宁出 BTB（分支目标缓冲区）条目。流水线代码获取需要在解码之前预测无条件分支的存在。见下文。

2021 年更新：https://blog.cloudflare.com/branch-predictor/ 详细探讨了这一点，使用 jmp next_insn 的块作为实验。例如，分支密度和别名（相对于 64 字节行的相同偏移量）可能很重要。

即使您的 jmp 是空操作，CPU 也没有额外的晶体管来检测这种特殊情况。它们的处理方式与任何其他方式一样 jmp，这意味着必须从新位置重新开始取指令，从而在管道中产生气泡。

要了解有关跳转及其对流水线 CPUs 的影响的更多信息，Control Hazards in a classic RISC pipeline 应该很好地介绍为什么分支对于流水线 CPUs 很困难。 Agner Fog 的指南解释了实际意义，但我认为假设有一些此类背景知识。

您的 Intel Broadwell CPU has a uop-cache，它缓存解码指令（与 32kiB L1 I-缓存分开）。

uop缓存大小为32组8路，每行6uop，共1536uop（如果每行都打包6ups，效率完美）。 1536 微指令介于 1000 和 10000 测试大小之间。在你编辑之前，我预测从慢到快的截止点将在你的循环中大约 1536 条指令总数。直到远远超过 1536 条指令，它才完全变慢，所以我认为我们可以排除 uop-cache 的影响。这不是我想的那么简单的问题。 :)

运行来自 uop 缓存（小代码大小）而不是 x86 指令解码器（大循环）意味着在识别 jmp 指令的阶段之前有更少的流水线阶段。因此，即使预测正确，我们也可能期望来自持续不断的跳跃流的气泡更小。

来自解码器的

运行应该给予更大的分支预测错误惩罚（比如可能是 20 个周期而不是 15 个），但这些不是预测错误的分支。

即使 CPU 不需要预测分支是否被采用，它仍然使用分支预测资源来预测代码块包含被采用的分支在解码之前。

缓存某个代码块中存在分支的事实及其目标地址，允许前端在 jmp rel32 编码实际解码之前开始从分支目标获取代码。请记住，解码可变长度的 x86 指令很困难：在解码前一条指令之前，您不知道一条指令从哪里开始。因此，您不能仅对指令流进行模式匹配以在其获取后立即寻找无条件跳转/调用。

我目前的理论是，当您运行超出分支目标缓冲区条目时，您正在减速。

另见 which has a nice answer, and discussion in this Realworldtech thread。

一个非常重要的点：BTB 预测下一个要提取的块，而不是提取块中特定分支的确切目的地。因此，不必为获取块中的所有分支预测目标，the CPU just needs to predict the address of the next fetch.

是的，当运行处理非常高的吞吐量（如异或归零）时，内存带宽可能会成为瓶颈，但 jmp 会遇到不同的瓶颈。 CPU 将有时间从内存中获取 42B，但这不是它正在做的。预取可以很容易地每 3 个时钟跟上 2 个字节，因此 L1 I-cache 未命中率应该接近于零。

在您的 xor with/without REX 测试中，如果您使用足够大的循环进行测试以不适合 L3 缓存，则主内存带宽实际上可能是那里的瓶颈。我在 ~3GHz CPU 上每个周期消耗 4 * 2B，这几乎达到了 DDR3-1600MHz 的 25GB/s 的最大值。不过，即使是 L3 缓存也足够快，可以跟上每个周期 4 * 3B。

有趣的是，主内存 BW 是瓶颈；我最初猜测解码（以 16 字节为单位）将是 3 字节 XOR 的瓶颈，但我猜它们足够小。

另请注意，在核心时钟周期中测量时间更为正常。但是，我猜，当您查看内存时，您在 ns 中的测量值很有用，因为用于节能的低时钟速度会改变核心时钟速度与内存速度的比率。（即内存瓶颈至少不是问题 CPU 时钟速度。）

要在时钟周期中进行基准测试，请使用 perf stat ./a.out。还有其他有用的性能计数器，它们 必不可少 以试图了解性能特征。

有关 Core2 的性能计数器结果（每个 jmp 8 个周期）和一些未知的微体系结构，请参阅，其中每个 jmp 约为 10c。

即使在或多或少的白盒条件下，现代 CPU 性能特征的细节也很难理解（阅读英特尔的优化手册，以及他们发布的有关 CPU 内部结构的内容） .如果你坚持进行黑盒测试，你会很早就陷入困境，如果你不阅读关于新 CPU 设计的 arstechnica 文章之类的东西，或者可能更详细的东西，比如 David Kanter 的 Haswell microarch overview，或我之前链接的类似 Sandybridge 文章。

如果早早陷入困境并且经常没问题并且你很开心，那么一定要继续做你正在做的事情。但是，如果您不知道这些细节，那么人们就更难回答您的问题，例如本例。：/例如我这个答案的第一个版本假设你已经阅读了足够多的内容，知道 uop 缓存是什么。

慢跳转指令

Slow jmp-instruction

assembly

x86

intel

cpu-architecture

branch-prediction