慢速jmp指令

Question

慢速jmp指令

assemblyx86intelcpu-architecturebranch-prediction

12

作为对我的问题“在x86-64中使用32位寄存器/指令的优势”的跟进，我开始衡量指令的成本。我知道这已经做过多次（例如Agner Fog），但我只是为了好玩和自学而这样做。

我的测试代码非常简单（为了简化这里是伪代码，在实际汇编中）:

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

但是还有一些事情需要考虑。

如果循环的内部部分很大（large 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
    ....
}

结果如下：

对于 “大” 的循环大小（即 NI>10^4），我测量得到每个 jmp 指令花费了 4.2 纳秒的时间（相当于从 RAM 加载 42 字节或在我的机器上约 12 个时钟周期）。
对于 “小” 的循环大小（NI<10^3），我测量得到每个 jmp 指令花费了 1 纳秒的时间（大约为 3 个时钟周期，这听起来是合理的——Agner Fog 的表格显示了 2 个时钟周期的成本）。

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

因此，我的问题是：在“大”循环中，jmp 指令的高成本可能有什么解释？

附注：如果您想在自己的计算机上尝试它，可以从这里下载脚本，只需在src文件夹中运行 sh jmp_test.sh 命令。

编辑：实验结果确认了 Peter 的 BTB（分支目标缓冲器）大小理论。

下表显示了不同 NI 值的每个指令周期数（相对于 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指令，一个（尚未知名的）资源变得稀缺，这导致NI大于4000时性能下降。
这个资源不会与xor等指令共享-如果在它们后面依次执行jmp和xor，性能下降仍然发生在NI约为4000时。
但是，如果进行跳转，则此资源将与je共享-对于依次执行jmp+je，资源在NI约为2000时会变得稀缺。
但是，如果je根本没有跳转，则该资源再次变得稀缺，NI约为4000（第四行）。

Matt Godbolt的分支预测逆向工程文章表明，分支目标缓冲区的容量为4096个条目。这是非常有力的证据，说明BTB错过是小型和大型jmp循环之间观察到的吞吐量差异的原因。

- ead

1

名称在调试信息中。发布的可执行文件中不会出现标签名称。 - doug65536

3

请注意，xorq %rax,%rax 与 xorl %eax,%eax 的作用完全相同，因此几乎没有理由使用前者（除非需要在某个地方插入 nop 进行对齐）。 - fuz

1

你的“大型”10,000条指令循环轻松适合现代处理器的L2缓存（256K），因此你并没有测量RAM的速度。 - Ross Ridge

1

@RossRidge 你说得对，对于 mov 和 xor，我需要在循环中执行 10^7 条指令才能看到“RAM 速度”。但是从 10^3 到 10^4，jmp 变慢了 4 倍。我不是说这是由于 RAM - 这是另一回事，但我不太清楚它是什么。 - ead

2

你可能已经明白了（因为你首先编写了那个测试用例），但最好还是明确一下 - 你的jmp + cmp + je（无跳转）情况之所以直到大约4,000次跳转才会出现资源稀缺，是因为未被执行的跳转不会消耗BTB条目（实际上，没有任何东西可以放入BTB中！）。 - BeeOnRope

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Accepted Answer

我的猜测是BTB（分支目标缓冲区）的条目已经用完。流水线式代码获取需要在解码之前预测无条件分支的存在。详见下文。

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

尽管您的jmp是无操作码，但CPU没有额外的晶体管来检测这种特殊情况。它们的处理方式与任何其他jmp一样，这意味着必须从新位置重新开始指令获取，从而在流水线中创建了一个气泡。

要了解有关跳转及其对流水线CPU的影响的更多信息，经典RISC流水线中的控制危害应该是一个很好的介绍，以说明分支对于流水线CPU的困难之处。Agner Fog的指南解释了实际影响，但我认为假定了某些这种背景知识。

你的Intel Broadwell CPU 有一个uop缓存，它缓存解码指令（与32kiB L1 I-cache分开）。 uop缓存大小为32组8路，每行6个uops，总共1536个uops（如果每行都装满6个uops，则完美效率）。 1536个uops介于你的1000和10000个测试大小之间。在你的编辑之前，我预测你循环中慢到快的临界点将恰好在1536个总指令附近。它直到超过1536个指令才开始变慢，因此我认为我们可以排除uop缓存的影响。这不是我想象中那么简单的问题。 :)

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

从解码器中运行应该会产生更大的分支预测错误惩罚（例如可能是20个周期而不是15个周期），但这些不是预测错误的分支。

即使CPU不需要预测分支是否被采取，它仍然使用分支预测资源来预测在解码之前代码块中包含一个已采取的分支。缓存某个代码块中存在分支及其目标地址的事实，允许前端在实际解码jmp rel32编码之前开始从分支目标处获取代码。请记住，解码可变长度的x86指令是很困难的：你不知道一个指令从哪里开始直到先前的指令被解码。因此，你不能只是模式匹配指令流以寻找无条件跳转/调用，就像获取时一样。我的当前理论是当你用完分支目标缓冲区条目时会减慢速度。另请参见What branch misprediction does the Branch Target Buffer detect?，其中有一个很好的答案，以及这个Realworldtech thread中的讨论。

重要的一点是：BTB预测的是下一个需要获取的块，而不是在获取块中特定分支的确切目标。因此，CPU只需要预测下一个获取的地址，而不是为获取块中所有分支预测目标。点击此处了解更多。

是的，在运行像异或清零这样的高吞吐量操作时，内存带宽可能会成为瓶颈，但你在使用 jmp 时却遇到了不同的瓶颈。CPU 有时间从内存中获取 42B，但它没有这样做。预取可以轻松跟上每3个周期2字节的速度，因此几乎不会有 L1 I-cache 丢失。

在你的含/不含 REX 的 xor 测试中，如果测试循环足够大以不适合于 L3 缓存，则主内存带宽实际上可能已经成为瓶颈。我在 ~3GHz 的 CPU 上每个周期消耗 4 * 2B，这几乎达到了 DDR3-1600MHz 的 25GB/s 的最大值。即使 L3 缓存也足够快，可以跟上每个周期 4 * 3B 的速度。

主内存 BW 是瓶颈真是有趣；我最初猜测解码（以16字节块为单位）将是 3-byte XORs 的瓶颈，但我想它们太小了。

请注意，用核心时钟周期来测量时间更为常见。但是，在处理内存时，您的纳秒测量结果也很有用，因为为了省电而采用低时钟速度会改变核心时钟速度与内存速度之间的比例（即在最小CPU时钟速度下，内存瓶颈问题较少）。

如果要以时钟周期进行基准测试，请使用perf stat ./a.out。还有其他一些有用的性能计数器，这些计数器对于试图理解性能特征至关重要。

请参阅x86-64相对jmp性能，其中包含来自Core2（每个jmp 8个周期）和某些未知微架构的perf-counter结果，其中每个jmp大约需要10个周期。

现代CPU性能特征的细节即使在更白盒的条件下（阅读英特尔的优化手册和他们发布的有关CPU内部的内容）都很难理解。如果你坚持黑盒测试，不阅读像arstechnica关于新CPU设计的文章或者一些更详细的文章，例如David Kanter的Haswell微架构概述或者我之前提到的类似Sandybridge的写作，你会很快陷入困境。如果早期和经常卡住是可以接受的，并且你很开心，那么请继续做你正在做的事情。但是如果你不知道这些细节，像这种情况，回答你的问题就更加困难了。例如，我回答这个问题的第一个版本假设你已经阅读了足够多的内容，知道什么是uop高速缓存。