performance - 慢速jmp指令

Question

作为我对问题The advantages of using 32bit registers/instructions in x86-64的跟进，我开始衡量指导费用。我知道这已经完成了多次（例如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
    ....
}

结果是：


对于“大”循环大小（已用于 NI>10^4），我测量的值为4.2 ns / jmp（相当于从RAM加载的42个字节，或在我的计算机上约为12个时钟周期）。
对于较小的循环大小（ NI<10^3），我测量的是1 ns / jmp-指令（大约3个时钟周期，这听起来似乎是合理的-Agner Fog的表显示了2个时钟周期的成本）。


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

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

PS：如果您想在计算机上试用，可以从 here下载脚本，只需在src-folder中运行 sh jmp_test.sh。



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

下表显示了针对不同 Ǹ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之类的指令共享-如果 NI和 jmp相互执行，则大约4000的 xor仍会导致性能下降。
但是，如果进行了跳转，则此资源与 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（分支目标缓冲区）条目已用完。见下文。



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

要了解有关跳转及其对流水线CPU的影响的更多信息，Control Hazards in a classic RISC pipeline应该很好地介绍了为何流水线CPU很难分支的原因。阿格纳·福格（Agner Fog）的指南解释了实际的含义，但是我认为应该假设其中的一些背景知识。



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

uop缓存的大小为32组8路，每行6 oups，总共1536 uops（如果每行装满6 oups，则效率非常高）。
1536微码介于1000和10000之间。在您进行编辑之前，我预计从慢到快的临界值大约在您的循环中共有1536条指令。直到远远超过1536条指令，它才不会减慢速度，因此我认为我们可以排除uop-cache的影响。这不是我想的那么简单的问题。 :)

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

从解码器运行可能会给分支带来较大的错误预测损失（例如，可能是20个周期而不是15个周期），但是这些并不是错误预测的分支。



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

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

我当前的理论是，当用完分支目标缓冲区条目时，您的速度会变慢。

另请参见What branch misprediction does the Branch Target Buffer detect?，它有一个很好的答案，并在此Realworldtech thread中进行了讨论。

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



是的，当运行诸如xor-zeroing之类的非常高吞吐量的东西时，内存带宽可能会成为瓶颈，但是您使用jmp遇到了另一个瓶颈。 CPU将有时间从内存中获取42B，但这不是它的工作。预取可以很容易地保持每3个时钟2个字节的速度，因此L1 I高速缓存未命中应该接近于零。

在具有/不具有REX测试的xor中，如果您使用足够大的循环进行测试以不适合L3缓存，则实际上主内存带宽可能一直是瓶颈。在〜3GHz的CPU上，每个周期消耗4 * 2B，这大约可以最大达到DDR3-1600MHz的25GB / s的速度。不过，即使是L3高速缓存，其速度也足以使其每个周期保持4 * 3B的速度。

有趣的是主内存带宽是瓶颈。最初，我猜想解码（以16字节为一组）将成为3字节XOR的瓶颈，但我想它们足够小。



还要注意，以核心时钟周期衡量时间更为正常。但是，我猜想，当您查看内存时，以ns为单位的测量非常有用，因为低时钟速度可节省功耗，从而改变了核心时钟速度与内存速度的比值。 （即，在最低CPU时钟速度下，内存瓶颈问题不大。）

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

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



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

如果尽早地被卡住并且经常没事，并且您在找乐子，那么请务必继续做您正在做的事情。但是，如果您不知道这些详细信息（例如在这种情况下），那么人们就很难回答您的问题。 ：/例如我对这个答案的第一个版本假定您已经阅读了足够的知识，以了解uop缓存是什么。