有没有GCC编译器提示可以强制分支预测始终按照特定的方式进行?

127

对于英特尔架构,有没有一种方法可以指示GCC编译器在我的代码中始终强制分支预测以特定方式进行? 英特尔硬件是否支持这样做?其他编译器或硬件呢?

我会在C ++代码中使用它,在那里我知道我希望快速运行的情况,并且不在意其他分支需要被采取时的减速,即使最近已经采取了该分支。

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}
作为对 Evdzhan Mustafa 的后续问题,提示能否仅为处理器第一次遇到指令指定提示,所有后续的分支预测都正常工作?
作为对 Evdzhan Mustafa 的跟进提问,提示是否只能为处理器第一次遇到该指令时指定提示,而所有后续的分支预测则正常工作?

如果出现任何异常情况(与编译器无关),也可以抛出异常。 - Shep
2
密切相关:Linux内核中的likely()/unlikely()宏 - 它们如何工作?它们有什么好处? - Michael Hampton
8个回答

93

GCC支持函数__builtin_expect(long exp, long c)来提供这种功能。您可以在此处查看文档here

其中exp是使用的条件,c是期望的值。例如,在您的情况下,您希望

if (__builtin_expect(normal, 1))

由于句法不太自然,通常可以通过定义两个自定义宏来使用。

#define likely(x)    __builtin_expect (!!(x), 1)
#define unlikely(x)  __builtin_expect (!!(x), 0)

只是为了简化任务。

请注意:

  1. 这不是标准的做法。
  2. 编译器/CPU分支预测器可能比你更擅长决定这些事情,所以这可能是一种过早的微观优化。

3
为什么您展示宏而不是 constexpr 函数?请说明原因。 - Columbo
23
@Columbo:我不认为一个 constexpr 函数可以取代这个宏。我相信它必须直接出现在 if 语句中。同样的原因,assert 也永远不可能是一个 constexpr 函数。 - Mooing Duck
10
使用宏的原因之一是因为在C或C ++中,这是仅有的几个地方之一,其中宏比函数更加语义正确。该函数之所以似乎有效,是因为优化(它是一种优化:constexpr 仅涉及值语义,而不涉及实现特定汇编代码的内联);对代码的直接解释(无内联)是没有意义的。根本没有理由使用函数来实现这个。 - Alex Celeste
3
考虑到__builtin_expect本身就是一种优化提示,所以认为简化其使用的方法取决于优化是不太有说服力的。 另外,我添加constexpr限定符并不是为了使其能够正常工作,而是为了使其在常量表达式中能够正常工作。同时,确实有使用函数的理由。例如,我不想用一个可爱的名称(如"likely")来污染我的整个命名空间。我得使用诸如LIKELY这样的名称,以强调它是一个宏并避免碰撞,但这样做只会让代码变得丑陋。 - Columbo
2
没有 PGO,编译器对分支的可能性几乎没有任何信息,因为它几乎没有上下文信息。有各种启发式方法,例如“返回常量的分支不太可能被执行,因为这是一种常见的错误处理模式”,但它们的使用受到限制,可能完全错误。另一方面,CPU 中的动态分支预测器更有可能做出正确的决策,但那时代码已经生成了。源提示不会干扰预测器。 - BeeOnRope
显示剩余6条评论

48

gcc有 long __builtin_expect (long exp, long c)我强调):

您可以使用__builtin_expect为编译器提供分支预测信息。通常,最好使用实际的性能反馈来进行优化(-fprofile-arcs),因为程序员通常不能正确地预测他们的程序的实际性能。但是,在某些情况下,很难收集这些数据。

返回值是exp的值,exp应该是一个整数表达式。内置函数的语义是预期exp == c。例如:

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

表示我们不希望调用foo,因为我们希望x为零。由于exp的限制只能使用整数表达式,因此您应该使用以下构造:

if (__builtin_expect (ptr != NULL, 1))
   foo (*ptr);

在测试指针或浮点数值时,如文档所述,您应该优先使用实际的配置文件反馈,本文显示了一个实际示例,至少在他们的情况下,这种方法最终比使用__builtin_expect来说更加有效。另请参见如何在g++中使用基于配置文件的优化?

我们还可以在Linux内核新手文章中找到关于kernal宏likely()和unlikely()使用此功能的信息:

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

注意,在我们的宏中使用了!!,可以在为什么使用 !!(condition) 而不是 (condition)?中找到其解释。

仅因为这种技术在Linux内核中使用并不意味着始终有必要使用它。正如我最近回答的这个问题在将参数作为编译时常量或变量传递时函数性能的差异中所看到的,很多手动优化技术在一般情况下都不起作用。我们需要仔细地分析代码,以了解一种技术是否有效。许多旧技术甚至可能与现代编译器优化无关。

请注意,虽然内建函数不具备可移植性,但clang 也支持 __builtin_expect

此外,在一些架构上可能没有影响


适用于Linux内核的东西并不足以满足C++11的要求。 - Maxim Egorushkin
@MaximEgorushkin 注意,我实际上并不推荐使用它,事实上我引用的gcc文档甚至没有使用那种技术。我想说的是,在走这条路之前要仔细考虑替代方案。 - Shafik Yaghmour

48

不,没有。(至少在现代x86处理器上是这样的。)

__builtin_expect在其他回答中提到,它会影响gcc编译汇编代码的方式。但它 并不直接影响CPU的分支预测。 当然,通过重新排列代码,会对分支预测产生间接影响。但在现代x86处理器上,没有一条指令告诉CPU“假设该分支被/未被执行”。

有关更多细节,请参见此问题:Intel x86 0x2E / 0x3E前缀分支预测实际使用了吗?

明确表示,__builtin_expect和/或使用-fprofile-arcs都可以通过代码布局向分支预测器提供提示(请参见x86-64汇编性能优化-对齐和分支预测)来优化代码性能,并通过将“不太可能”的代码与“可能”的代码分开,从而改善缓存行为。


10
这是不正确的。在所有现代x86版本中,预测算法的默认设置是预测前向分支不被采取,而后向分支则被采取(请参见https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts)。因此,通过重新排列代码,您可以有效地向CPU提供提示。这正是当您使用`__builtin_expect`时,GCC所做的事情。 - Nemo
8
@Nemo,你有没有读完我回答的第一句话?我的回答或给出的链接已经涵盖了你所说的一切内容。问题是是否能够“强制分支预测始终按照某种方式进行”,对此的答案是“不行”,而我认为其他答案在这方面不够清楚。 - Artelius
5
好的,我应该认真阅读。在我看来,这个答案在技术上是正确的,但是没有用,因为问题的提问者显然正在寻找__builtin_expect。所以这应该只是一条评论。但它并不是错误的,所以我取消了我的负评。 - Nemo
3
在我看来,这并不是无用的;它是关于CPU和编译器实际工作方式的有用澄清,这可能与使用/不使用这些选项的性能分析相关。例如,您通常不能使用__builtin_expect轻松创建一个测试用例,然后使用perf stat进行测量,从而产生非常高的分支错误率。它只影响分支布局。顺便说一下,自Sandybridge或至少Haswell以来,英特尔几乎没有使用静态预测;BHT中总是会有一些预测,无论它是否过时。 https://xania.org/201602/bpu-part-two - Peter Cordes
1
现代英特尔CPU(缺乏)静态预测的更多细节:为什么英特尔在这些年里改变了静态分支预测机制? - Peter Cordes

24

在C++11中定义likely/unlikely宏的正确方法如下:

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

[[likely]] 不同,该方法适用于所有 C++ 版本,但依赖于非标准扩展 __builtin_expect


当这些宏以此方式定义时:

#define LIKELY(condition) __builtin_expect(!!(condition), 1)

那可能改变if语句的含义并破坏代码。请考虑以下代码:

#include <iostream>

struct A
{
    explicit operator bool() const { return true; }
    operator int() const { return 0; }
};

#define LIKELY(condition) __builtin_expect((condition), 1)

int main() {
    A a;
    if(a)
        std::cout << "if(a) is true\n";
    if(LIKELY(a))
        std::cout << "if(LIKELY(a)) is true\n";
    else
        std::cout << "if(LIKELY(a)) is false\n";
}

它的输出:

if(a) is true
if(LIKELY(a)) is false

如您所见,使用!!作为bool转换的定义破坏了if语句的语义。

这里的重点不是operator int()operator bool()应该有关联。这是良好的实践。

而是使用!!(x)而非static_cast<bool>(x)会丢失关于C++11 上下文转换的上下文。


请注意,上下文转换是通过2012年的一个缺陷引入的,即使在2014年末仍存在实现差异。实际上,看起来我链接的这个案例对于gcc仍然不起作用。 - Shafik Yaghmour
@ShafikYaghmour,关于switch中涉及的上下文转换,你提出了一个有趣的观察,谢谢。这里涉及到的上下文转换是特定于类型bool和列出的五个特定上下文的上下文转换,但不包括switch上下文。 - Maxim Egorushkin
2
在你的例子中,你只使用了(condition),而没有使用!!(condition)。在更改后,两者都是true(使用g++ 7.1测试)。你能否构造一个实际演示当你使用!!进行布尔化时所讨论的问题的例子? - Peter Cordes
啊,是的,重载operator!就可以了 :P - Peter Cordes
4
正如Peter Cordes指出的那样,你说:“当这些宏以这种方式定义时:”,然后展示了一个使用“!!”的宏,“可能会改变if语句的含义并导致代码出错。考虑以下代码:”,然后你展示的代码根本没有使用“!!”,而且已知在C++11之前就已经存在问题。请修改答案,展示一个给定的使用“!!”的宏会出错的例子。 - Carlo Wood
显示剩余2条评论

19
正如其他答案已经充分建议的那样,您可以使用__builtin_expect来向编译器提供关于如何排列汇编代码的提示。正如官方文档所指出的,在大多数情况下,您脑中内置的汇编器不会像GCC团队精心制作的汇编器那样好。最好使用实际的配置文件数据来优化代码,而不是猜测。
类似的方法,但尚未提到的是一种强制编译器在“冷”路径上生成代码的GCC特定方式。这涉及使用noinlinecold属性,它们恰好执行它们听起来要做的事情。这些属性只能应用于函数,但是在C++11中,您可以声明内联lambda函数,并且这两个属性也可以应用于lambda函数。
虽然这仍然属于微优化的一般类别,因此标准建议适用-测试不要猜测-但我觉得它比__builtin_expect更普遍有用。几乎没有x86处理器的任何一代使用分支预测提示(参考),因此您唯一能够影响的就是汇编代码的顺序。由于您知道哪些是错误处理或“边缘情况”代码,因此可以使用此注释来确保编译器永远不会预测到它并且在优化大小时将其链接到“热”代码之外。
示例用法:
void FooTheBar(void* pFoo)
{
    if (pFoo == nullptr)
    {
        // Oh no! A null pointer is an error, but maybe this is a public-facing
        // function, so we have to be prepared for anything. Yet, we don't want
        // the error-handling code to fill up the instruction cache, so we will
        // force it out-of-line and onto a "cold" path.
        [&]() __attribute__((noinline,cold)) {
            HandleError(...);
        }();
    }

    // Do normal stuff
    ⋮
}

更好的是,当有profile feedback可用时(例如使用-fprofile-use编译时),GCC将自动忽略此选项并选择profile feedback。详见官方文档:https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes

3
忽略分支预测提示前缀是因为它们不是必需的,你可以通过重新排列代码来达到完全相同的效果。(默认的分支预测算法是猜测向后分支会被执行,向前分支则不会。)因此,实际上,你可以给CPU提供一个提示,这就是__builtin_expect所做的。它并不无用。你说的cold属性也是有用的,但我认为你低估了__builtin_expect的实用性。 - Nemo
现代英特尔CPU不使用静态分支预测。您所描述的算法,@Nemo,在早期处理器中使用,其中向后分支被预测为已采取,向前分支被预测为不采取,直到Pentium M等处理器,但现代设计基本上只是随机猜测,索引到它们的分支表中在那里会期望找到有关该分支的信息,并使用任何信息(即使它可能是垃圾)。因此,分支预测提示从理论上讲可能是有用的,但在实践中可能并非如此,这就是英特尔将其删除的原因。 - Cody Gray
需要明确的是,分支预测的实现非常复杂,而且注释中的空间限制迫使我大大简化了它。这本身就是一个完整的答案。现代微架构中可能仍然存在静态分支预测的痕迹,例如Haswell,但它已经不像过去那么简单了。 - Cody Gray
你有“现代英特尔CPU不使用静态分支预测”的参考资料吗?英特尔自己的文章(https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts)则表示相反...但那是2011年的。 - Nemo
没有官方参考资料,@Nemo。英特尔对其芯片中使用的分支预测算法保密极了,将其视为商业机密。大部分已知信息都是通过经验测试得出的。像往常一样,Agner Fog的材料是最好的资源,但他甚至说:“分支预测器似乎已在Haswell中重新设计,但关于其构造几乎没有什么了解。”我不记得我最初在哪里看到证明静态BP不再使用的基准测试了,不幸的是。 - Cody Gray
显示剩余3条评论

12

从C++20开始,likely和unlikely属性应该已经被规范化并且已经在g++9中得到支持。因此如此处所讨论的那样,您可以编写

if (a > b) {
  /* code you expect to run often */
  [[likely]] /* last statement here */
}

例如,在以下代码中,由于if块中的[[unlikely]]else块被内联了。

int oftendone( int a, int b );
int rarelydone( int a, int b );
int finaltrafo( int );

int divides( int number, int prime ) {
  int almostreturnvalue;
  if ( ( number % prime ) == 0 ) {
    auto k                         = rarelydone( number, prime );
    auto l                         = rarelydone( number, k );
    [[unlikely]] almostreturnvalue = rarelydone( k, l );
  } else {
    auto a            = oftendone( number, prime );
    almostreturnvalue = oftendone( a, a );
  }
  return finaltrafo( almostreturnvalue );
}


1
为什么在 if 中使用 [[unlikely]] 而在 else 中使用 [[likely]] - WilliamKF
没有任何原因,只是在尝试属性应该放在哪里的过程中最终得出了这个结论。 - pseyfert
非常酷。太遗憾了,这种方法不适用于旧版的C++。 - Maxim Egorushkin
神奇的godbolt链接 - Lewis Kelsey
请注意,这些不暗示运行时分支预测(至少对于大多数ISA而言,因为实际上没有机制可以做到这一点,特别是在现代x86上,不存在回退到静态预测未采取前向分支的情况,请参见其他答案),因此这并不真正回答标题问题。但这正是您想要的:提示编译器哪个路径是热点可能很有用,这样它就可以布置该路径以涉及更少的采取分支(超标量前端使用宽连续指令获取更容易)。 - Peter Cordes

5

__builtin_expect可以用来告诉编译器你期望分支走哪个方向。这会影响代码的生成。典型的处理器按顺序运行代码更快。因此,如果你写:

if (__builtin_expect (x == 0, 0)) ++count;
if (__builtin_expect (y == 0, 0)) ++count;
if (__builtin_expect (z == 0, 0)) ++count;

编译器将会生成类似以下的代码:
if (x == 0) goto if1;
back1: if (y == 0) goto if2;
back2: if (z == 0) goto if3;
back3: ;
...
if1: ++count; goto back1;
if2: ++count; goto back2;
if3: ++count; goto back3;

如果你的提示正确,这将执行代码而不会实际执行任何分支。它将比正常序列运行得更快,其中每个if语句将在条件代码周围进行分支并执行三个分支。
较新的x86处理器具有预计采取的分支的指令,或者针对预计不采取的分支的指令(有一个指令前缀;不确定详细信息)。不确定处理器是否使用它。它并不是很有用,因为分支预测会处理这个问题。因此,我认为你实际上无法影响分支预测。

2
关于OP的问题,GCC没有办法告诉处理器总是假定分支是否被执行。你可以使用__builtin_expect来实现其他人所说的功能。此外,我认为你不想总是告诉处理器分支是否被执行。如今的处理器(例如英特尔架构)可以识别相当复杂的模式并有效地适应。
但是,在某些情况下,您希望默认情况下分支是否被预测为已执行或未执行:当您知道代码将被“冷”调用时,与分支统计有关。
一个具体的例子是异常管理代码。按定义,管理代码会出现异常,但也许在发生最大性能时期望(可能需要尽快处理关键错误),因此您可能希望控制默认预测。
另一个例子是:您可能会对输入进行分类,并跳转到处理分类结果的代码中。如果有很多分类,处理器可能会收集统计信息,但由于相同的分类不会很快发生且预测资源专用于最近调用的代码,因此会失去它们。我希望有一种原始方法可以告诉处理器“请不要将预测资源专用于此代码”,就像有时可以说“不要缓存此内容”。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接