GCC的__builtin_expect到什么程度?

27

回答另一个问题时,我对此产生了好奇。我很清楚

if( __builtin_expect( !!a, 0 ) ) {
    // not likely
} else {
    // quite likely
}

将"很有可能"分支加速(通常情况下),通过类似提示处理器/更改汇编代码顺序/某种魔法的方式来实现。(如果有人可以解释一下那个魔法,那就太好了)。

但这对于a)内联if、b)变量和c)除0和1之外的值是否有效?即,是否会

__builtin_expect( !!a, 0 ) ? /* unlikely */ : /* likely */;

或者

int x = __builtin_expect( t / 10, 7 );
if( x == 7 ) {
    // likely
} else {
    // unlikely
}

或者

if( __builtin_expect( a, 3 ) ) {
    // likely
    // uh-oh, what happens if a is 2?
} else {
    // unlikely
}

有任何影响吗?这一切是否取决于目标架构?

2个回答

23

你读过GCC文档吗?

Built-in Function: long __builtin_expect (long exp, long c)

You may use __builtin_expect to provide the compiler with branch prediction information. In general, you should prefer to use actual profile feedback for this (-fprofile-arcs), as programmers are notoriously bad at predicting how their programs actually perform. However, there are applications in which this data is hard to collect.

The return value is the value of exp, which should be an integral expression. The semantics of the built-in are that it is expected that exp == c. For example:

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

indicates that we do not expect to call foo, since we expect x to be zero. Since you are limited to integral expressions for exp, you should use constructions such as

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

when testing pointer or floating-point values.

为了解释一下,__builtin_expect 特别有用于表达程序可能采取的分支。你问编译器如何利用这个见解 - 好吧,考虑一下这段代码:
if (x == 0)
    return 10 * y;
else
    return 39;

在机器码中,CPU通常可以被要求“转到”另一行(这需要时间,并且根据CPU的不同可能会防止其他执行优化——即低于机器码级别——例如,请参见http://en.wikipedia.org/wiki/Instruction_pipeline下面的分支标题),或者调用其他代码,但没有真正的if/else概念,其中真和假的代码是相等的...你必须分支离开以找到一个或另一个的代码。这样做的方式基本上是,伪代码如下:
test whether x is 0
if it was goto else_return_39
return 10 * y
else_return_39:
return 39

大多数CPU在跳转到else_return_39:标签之后比直接掉到return 10 * y更慢,所以“真”分支的代码将比假分支更快到达。当然,机器码可以测试x是否不等于0,将“false”代码(return 39)放在第一位,从而颠倒性能特征。
这就是__builtin_expect的控制方式——您可以告诉编译器将真或假分支放在需要较少分支才能到达的位置,从而获得微小的性能提升。
但是,这对a)内联ifs、b)变量和c)值为0和1以外的值是否有效呢?
a)周围函数是否内联化并不改变需要在if语句出现的分支处进行分支的需要(除非优化器看到if语句测试的条件始终为truefalse,只有一个分支永远无法运行)。因此,它同样适用于内联代码。

[ 你的评论显示你对条件表达式 - a ? b : c - 感兴趣。我不确定 - 关于这个问题有一个有争议的答案,可以在 https://dev59.com/W2Uq5IYBdhLWcg3wHcv5 找到可能会提供一些见解,或者是进一步探索的基础 ]

b) 变量 - 你假设:

int x = __builtin_expect( t / 10, 7 );
if( x == 7 ) {

那样行不通 - 编译器没有义务将这些期望与变量关联并在下次看到if时记住它们。您可以使用gcc -S生成汇编语言输出进行验证(就像我为gcc 3.4.4所做的那样):无论预期值如何,汇编都不会改变。
c) 非0和1的值
对于整数(long)值有效,因此是的。上面引用的文档的最后一段专门解决了这个问题:

you should use constructions such as

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

when testing pointer or floating-point values.

为什么?如果指针类型大于long,那么调用__builtin_conversion(long, long)将会有效地切掉一些不太重要的位进行测试,并且无法将(高阶)剩余部分纳入测试中。同样,浮点数值可能比长整型更大,转换可能无法产生您期望的结果。通过使用布尔表达式,例如ptr != NULL(给定true转换为1,false转换为0),您可以确保获得预期的结果。


是的,我确实阅读了文档(当然!)。就像我说的,我已经知道要点了。你误解了我的(a)部分;我指的是“内联if”的syntax(它有更好的名称吗?很多人使用三元运算符,但那只是它的形式,不是名称)。另外,对于(c),我指的是其他long值,而不是其他数据类型(正如我在示例中所提到的)。实际上,我想知道为什么它首先是一个长整型,而不是一个intchar_Bool - Dave
1
@Dave:C++11标准/5.16将“条件运算符”指定为特指?,一般指“条件表达式”。关于(c)——我重新阅读了你的示例,并理解了你的担忧。虽然我对(a,3)/a==2情景没有比你更多的信息,但我可以想象参数为“long”的原因只是为了避免添加机器代码指令以缩短或转换参数:例如,如果是bool,那么编译器可能需要确保非零值被改变为1。同样,对于“char”,它可能需要与255进行“&”操作。 - Tony Delroy
听起来很可信。我得记住“条件运算符”! - Dave
@Dave:编辑上面的内容,包括来自https://dev59.com/W2Uq5IYBdhLWcg3wHcv5的答案 - 干杯。 - Tony Delroy
我之前看过那个答案,但对他的方法不满意;它并没有说到如何在输出中实际包含分支预测,只是一个无用的函数调用,在更高的 O 值时被优化掉了。如果他将其编译为期望值为 1 和 0 的两种情况,并在高度优化时寻找差异,效果会更好。 - Dave
显示剩余2条评论

19

但是这对于a)内联ifs,b)变量和c)值为0和1以外的值有效吗?

这适用于用于确定分支的表达式上下文。

所以,a)是。 b)不是。 c)是。

所有这些是否都取决于目标架构?

是的!

它利用使用指令流水线的架构,这使得CPU可以在当前指令完成之前开始处理即将到来的指令。

(如果有人能澄清这个神奇的东西,那就太好了)。

(“分支预测”使这个描述变得复杂,因此我故意省略了它)

任何类似if语句的代码都意味着表达式可能导致CPU跳转到程序中的其他位置。 这些跳转会使CPU的指令流水线无效。

__builtin_expect允许(不能保证)gcc尝试组装代码,以便可能情况涉及的跳转比备选方案少。


好的,这是对主要问题非常清晰的回答,最后一部分基本上是我想到的。如果a为2,您能否解释一下最后一个示例可能会发生什么? - Dave
@Dave:你赢了,尽管你不应该。__builtin_expect永远不会生成错误的代码,只会生成不同的代码。在某些情况下,不同的代码会更好,而在其他情况下则会更差。你希望最常见的情况是代码更好,但在其他情况下它也可能更好。 - David Schwartz
@DavidSchwartz 但它是否假装它是写成了 __builtin_expect(!!a,1),或者无论如何都执行相同的操作,甚至比没有 __builtin_expect 更慢。这是一个无意义的问题,但我很感兴趣。正如我在对另一个答案的评论中所说,我的主要好奇心是为什么他们选择使用 long,而不是 intchar_Bool - Dave
1
请注意在 if( __builtin_expect( !!a, 0 ) ) 中对 a 的双重否定。这让我感到困惑 - !!a == a,那么为什么要双重否定呢?原因是 __builtin_expect 需要整数参数,但如果您在宏中使用 __builtin_expect 并且宏的调用者提供了指针或浮点数,则该怎么办。通过使用 !!,它允许直接使用非整数参数。第一个 ! 将非整数转换为 0 或 1,例如将指针 NULL 转换为整数 1。第二个 ! 修正逻辑,即将该 1 转换回 0,这在逻辑上就是我们期望将 NULL 映射到的值。 - tullaman
1
@gangwei_d 《GCC手册》链接规定:“返回值是exp的值,exp应该是一个整数表达式”,然后继续说要使用ptr != NULL来评估指针。因此,当内置函数的使用由宏中介时,该宏通常使用!!技巧来覆盖宏参数的所有可能性。这就是我对!!存在的解释。但我也接受其他理论。 - tullaman
显示剩余2条评论

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