分支预测器是否可以告诉程序，跟随分支的可能性有多大？

Question

分支预测器是否可以告诉程序，跟随分支的可能性有多大？

cgccx86compiler-optimizationmicro-optimization

81

为了明确一下，我不需要任何可移植性的解决方案，所以任何会绑定到特定机器上的解决方案都是可以接受的。

基本上，我有一个if语句，在99%的情况下将计算为true，现在我想尽可能地提高性能，是否可以发出某种编译器命令（使用GCC 4.1.2和x86 ISA，如果有关系）来告诉分支预测器应该缓存这个分支？

- Andy Shulman

12

使用配置引导优化（-fprofile-generate），在一些测试数据上运行，然后使用-fprofile-use。这样gcc就会知道每个分支的统计信息，并能够为快速路径优化代码布局。但是，在没有PGO编译代码的情况下，builtin_expect仍然是一个好主意，特别是对于它有帮助的地方。由于很难为内核生成配置文件，因此Linux内核具有一些良好的宏（例如likely()和unlikely()）来实现这一点。 - Peter Cordes

微软也提供了PGO——http://blogs.msdn.com/vcblog/archive/2008/11/12/pogo.aspx。 - Hassan Syed

7个回答

65

是的。 http://kerneltrap.org/node/4705

__builtin_expect是一种方法，gcc（版本>= 2.96）为程序员提供，以向编译器指示分支预测信息。 __builtin_expect的返回值是传递给它的第一个参数（只能是整数）。

if (__builtin_expect (x, 0))
                foo ();

     [This] would indicate that we do not expect to call `foo', since we
     expect `x' to be zero.

- Drakosha

10

在 Microsoft 环境中，if 语句被预测为始终为真。某些版本具有档案引导优化。 - Charles Beattie

参见：https://dev59.com/h3VD5IYBdhLWcg3wDG_l - Ciro Santilli OurBigBook.com

37

Pentium 4（又称Netburst微架构）在jcc指令的前缀中有分支预测提示，但只有P4才会使用它们。请参见http://ref.x86asm.net/geek32.html和http://www.agner.org/optimize/的Agner Fog优秀汇编优化指南第3.5节。他还有一份关于C ++优化的指南。

早期和后期的x86 CPU会默默地忽略这些前缀字节。有没有使用likely / unlikely提示的性能测试结果？提到PowerPC有一些跳转指令，其中包含作为编码一部分的分支预测提示。这是一个非常罕见的架构特性。在编译时静态预测分支非常难以准确地做到，因此通常最好让硬件来解决。

关于最近的英特尔和AMD CPU中的分支预测器和分支目标缓冲区的确切行为，官方发布了很少的信息。优化手册（易于在AMD和英特尔的网站上找到）提供了一些建议，但未记录具体行为。一些人已经进行了测试，试图推断实现方式，例如Core2有多少BTB条目...无论如何，明确提示预测器的想法已被放弃（暂时）。

例如，已经有记录显示Core2具有分支历史缓冲区，可以避免在循环始终运行短的常量迭代次数时出现误预测，<8或16 IIRC。但不要过于急于展开循环，因为适合64字节（或Penryn上的19个uops）的循环不会有指令提取瓶颈，因为它从缓冲区重播...去阅读Agner Fog的pdf文件，它们非常好。

另请参见为什么英特尔在这些年里改变了静态分支预测机制？：自Sandybridge以来，据我们所知，英特尔根本不使用静态预测，这是通过试图反向工程CPU执行的性能实验得出的结论。（许多旧CPU在动态预测失误时采用静态预测作为后备。正常的静态预测是前向分支不被采纳，而后向分支被采纳（因为后向分支通常是循环分支）。）

< p > 使用GNU C的__builtin_expect来实现likely()/unlikely()宏的效果（就像Drakosha的答案所提到的那样）并不会直接将BP提示插入到汇编代码中。（在编译其他任何内容时都不会这样做，但在使用gcc -march=pentium4编译时可能会这样做。）

实际效果是布局代码，使快速路径具有较少的taken分支和可能更少的指令总数。这将有助于静态预测起作用的情况下的分支预测（例如，在动态预测器很冷的情况下，对于CPU，它会回退到静态预测而不仅仅是让分支在预测器缓存中别名）。

请参见What is the advantage of GCC's __builtin_expect in if else statements?以获取特定的代码生成示例。

taken分支的成本略高于未taken分支，即使完全预测。当CPU以16字节的块抓取代码以并行解码时，taken分支意味着该抓取块中的后续指令不是要执行的指令流的一部分。它会在前端创建气泡，这可能会成为高吞吐量代码的瓶颈（它在缓存未命中时不会在后端停顿，并具有高指令级并行性）。

跳转到不同的代码块还可能触及更多的缓存行，增加L1i缓存占用，如果它是冷的，也可能导致更多的指令缓存未命中。(以及潜在的uop缓存占用)。因此，快速通道短且线性也有另一个优点。

GCC的基于概要文件的优化通常使得likely/unlikely宏不必要。编译器会收集运行时数据，以便进行代码布局决策并识别热块/函数和冷块/函数。(例如，它会在热函数中展开循环，但不会在冷函数中展开。)请参见GCC手册中的-fprofile-generate和-fprofile-use。如何在g ++中使用概要文件指导的优化？否则，如果您没有使用likely/unlikely宏和PGO，则GCC必须使用各种启发式方法来进行猜测。默认情况下，在-O1及更高级别上启用-fguess-branch-probability。 https://www.phoronix.com/scan.php?page=article&item=gcc-82-pgo&num=1在Xeon Scalable服务器CPU（Skylake-AVX512）上使用gcc8.2对PGO和常规方式进行了基准测试。每个基准测试都获得了至少一点加速，有些获得了约10％的好处。(其中大部分可能来自于热循环中的循环展开，但其中一些显然来自于更好的分支布局和其他效果。)

- Peter Cordes

顺便说一句，如果您使用基于配置文件的优化，则可能不需要使用builtin_expect。PGO记录了每个分支走的方式，因此当您使用-fprofile-use进行编译时，gcc知道每个分支的常见情况是哪种情况。尽管如此，在没有PGO的情况下构建代码时，使用builtin_expect告诉它快速路径仍然是有好处的。 - Peter Cordes

7

我建议不要担心分支预测，而是对代码进行剖析并优化代码以减少分支数量。其中一个例子是循环展开，另一个例子是使用布尔编程技术而不是使用if语句。

大多数处理器都喜欢预取语句。通常，分支语句会在处理器内部引发故障，导致它清除预取队列。这是最大的惩罚所在。为了减少这个惩罚时间，重写（和设计）代码，使可用的分支更少。此外，一些处理器可以有条件地执行指令，而无需进行分支。

我通过使用循环展开和大型I/O缓冲区将一个程序的执行时间从1小时优化到了2分钟。在这种情况下，分支预测不会提供太多的时间节省。

- Thomas Matthews

1

“boolean programming techniques”是什么意思？ - someonewithpc

@someonewithrpc 这是通过使用位运算将多个情况合并为一个的示例。一个（愚蠢但仍然有效）的例子：将 a = b&1 ? 0 : 1; 替换为 a = b&1; - Simon

编译器不是已经完成了吗？ - Alexis

1

SUN C Studio为此情况定义了一些pragma。

#pragma rarely_called ()

如果条件表达式的一部分是函数调用或以函数调用开头，则此方法有效。

但是，无法标记通用的if/while语句。

- Lothar

-10

不，因为没有汇编命令可以让分支预测器知道。不用担心，分支预测器非常聪明。

此外，强制性评论关于过早优化以及它是邪恶的。

编辑：Drakosha提到了一些适用于GCC的宏。但是，我认为这是代码优化实际上与分支预测无关。

- rlbond

3

谢谢Knuth先生。如果这不是一个比赛，看看谁的解决方案运行速度最快，我完全同意。 - Andy Shulman

1

如果你需要每一个周期，为什么不使用内联汇编？ - rlbond

16

完整引用：“我们应该忘记关于小效率的事情，大约有97%的时间：过早优化是万恶之源。然而，在那关键的3%中，我们不应放弃机会。一个好的程序员不会被这种推理所麻痹，他会明智地仔细查看关键代码；但前提是必须先确定了那段代码。”（重点是我的加粗） - Roger Pate

5

当分支预测器不知道分支的情况下，它有一个静态规则：采取向后分支而不采取向前分支。如果您考虑for循环的工作原理，您就会明白为什么这是有道理的，因为您会多次跳回循环的顶部。因此，GCC宏控制的是GCC如何在内存中布置操作码，以便向前/向后分支预测规则最有效。 - Don Neufeld

2

这是完全错误的，实际上有一个汇编命令可以让分支预测器知道。但在除了Netburst架构之外的所有架构上都会被忽略。 - Gunther Piez

1

@don.neufeld：你提到的静态规则只存在于旧架构中，对于Core2及以上版本，冷跳转的方向是伪随机的，因为它取决于历史表中被覆盖的条目。 - Gunther Piez

-11

对我来说，这听起来有些过度 – 这种类型的优化只能节省微小的时间。例如，使用更新的gcc版本会对优化产生更大的影响。此外，尝试启用和禁用所有不同的优化标志；它们并不都能提高性能。

基本上，相比于其他许多有益的途径，这似乎极不可能产生任何重大差异。

编辑：感谢评论。我已经将其设置为社区wiki，但仍然保留了评论以供他人查看。

- Peter

1

不过，在某些情况下这也是有用的。例如，有一些编译器会将代码输出为 C 语言，并在每一行加上“if (break) break_into_debugger()”，以提供一个平台无关的调试解决方案。 - Lothar

8

实际上，在深度流水线处理器上，分支预测错误是非常昂贵的，因为它们需要完全清空流水线。相比指令执行，它们的代价可能高达20倍。如果他的基准测试结果告诉他分支预测有问题，那么他正在做正确的事情。顺便说一下，VTune会提供非常好的数据支持，如果你还没有尝试过的话。 - Don Neufeld

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

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

- Gunther Piez · Accepted Answer

是的，但它没有任何影响。除了旧的（废弃的）Netburst架构之前的一些体系结构会例外，即使在这种情况下也不会有明显的影响。

Intel引入了“分支提示”操作码，以及对某些较旧架构的冷跳转（向后预测为取，向前预测为不取）的默认静态分支预测。GCC使用__builtin_expect(x, prediction)来实现这一点，其中prediction通常为0或1。编译器发出的操作码在所有新的处理器架构（>= Core 2）上都被忽略了。这个小的特殊情况是在旧的Netburst架构上进行冷跳转的情况下才有可能实际起作用。Intel现在建议不要使用静态分支提示，可能是因为他们认为代码大小的增加比可能的边际加速更有害。

除了用于预测器的无用分支提示外，__builtin_expect还有其用途，编译器可以重新排序代码以提高缓存使用率或节省内存。

有多个原因它并不能像预期那样工作。

处理器可以完美地预测小循环（n < 64）。
处理器可以完美地预测小重复模式（n~7）。
处理器本身可以在运行时比编译器/程序员在编译时更好地估计分支的概率。
可预测性（分支被正确预测的概率）比分支是否被取更重要。不幸的是，这高度依赖于架构，并且预测分支可预测性是出了名的困难。

请参阅Agner Fog的手册，了解分支预测的内部工作原理。还可以查看gcc的邮件列表。