Linux内核中可能/不太可能的宏如何工作以及它们的好处是什么？

Question

我一直在挖掘Linux内核的某些部分,发现这样的调用:

if (unlikely(fd < 0))
{
    /* Do something */
}

要么

if (likely(!err))
{
    /* Do something */
}

我找到了它们的定义:

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

我知道它们是为了优化,但它们是如何工作的？使用它们可以预期性能/尺寸减少多少？至少在瓶颈代码中(当然在用户空间中)是否值得麻烦(并且可能失去可移植性).

Answer 1

它们暗示编译器发出的指令将导致分支预测有利于跳转指令的"可能"侧.这可能是一个巨大的胜利,如果预测是正确的,这意味着跳转指令基本上是免费的并且将采取零周期.另一方面,如果预测是错误的,则意味着需要刷新处理器流水线并且可能花费几个周期.只要预测在大多数情况下是正确的,这将有利于性能.

像所有这些性能优化一样,您应该只在进行大量分析后才能确保代码真正处于瓶颈状态,并且可能具有微观特性,即它在紧密循环中运行.通常Linux开发人员都很有经验,所以我想他们会这样做.他们并不太关心可移植性,因为他们只针对gcc,他们对他们想要生成的程序集非常了解.

Answer 2

让我们反编译看看GCC 4.8对它的作用

没有 __builtin_expect

#include "stdio.h"
#include "time.h"

int main() {
    /* Use time to prevent it from being optimized away. */
    int i = !time(NULL);
    if (i)
        printf("%d\n", i);
    puts("a");
    return 0;
}

使用GCC 4.8.2 x86_64 Linux编译和反编译:

gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o

输出:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       75 14                   jne    24 <main+0x24>
  10:       ba 01 00 00 00          mov    $0x1,%edx
  15:       be 00 00 00 00          mov    $0x0,%esi
                    16: R_X86_64_32 .rodata.str1.1
  1a:       bf 01 00 00 00          mov    $0x1,%edi
  1f:       e8 00 00 00 00          callq  24 <main+0x24>
                    20: R_X86_64_PC32       __printf_chk-0x4
  24:       bf 00 00 00 00          mov    $0x0,%edi
                    25: R_X86_64_32 .rodata.str1.1+0x4
  29:       e8 00 00 00 00          callq  2e <main+0x2e>
                    2a: R_X86_64_PC32       puts-0x4
  2e:       31 c0                   xor    %eax,%eax
  30:       48 83 c4 08             add    $0x8,%rsp
  34:       c3                      retq

在内存中的指令顺序不变:第一printf,然后puts和retq回报.

同 __builtin_expect

现在替换if (i)为:

if (__builtin_expect(i, 0))

我们得到:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       74 11                   je     21 <main+0x21>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1+0x4
  15:       e8 00 00 00 00          callq  1a <main+0x1a>
                    16: R_X86_64_PC32       puts-0x4
  1a:       31 c0                   xor    %eax,%eax
  1c:       48 83 c4 08             add    $0x8,%rsp
  20:       c3                      retq
  21:       ba 01 00 00 00          mov    $0x1,%edx
  26:       be 00 00 00 00          mov    $0x0,%esi
                    27: R_X86_64_32 .rodata.str1.1
  2b:       bf 01 00 00 00          mov    $0x1,%edi
  30:       e8 00 00 00 00          callq  35 <main+0x35>
                    31: R_X86_64_PC32       __printf_chk-0x4
  35:       eb d9                   jmp    10 <main+0x10>

该printf(编译__printf_chk)被转移到功能的尽头,之后puts,并返回提高分支预测由其他的答案中提到.

所以它基本上是相同的:

int i = !time(NULL);
if (i)
    goto printf;
puts:
puts("a");
return 0;
printf:
printf("%d\n", i);
goto puts;

这种优化没有完成-O0.

但是,写一个运行速度__builtin_expect比没有运行得更快的例子,祝你好运,那些时候CPU非常聪明.我天真的尝试就在这里.

Answer 3

这些是宏,它们向编译器提供有关分支可能采用的方式的提示.如果宏可用,宏将扩展为GCC特定扩展.

GCC使用这些来优化分支预测.例如,如果您有类似以下内容

if (unlikely(x)) {
  dosomething();
}

return x;

然后它可以重构这个代码更像是:

if (!x) {
  return x;
}

dosomething();
return x;

这样做的好处是,当处理器第一次采用分支时,会产生很大的开销,因为它可能已经推测性地加载并进一步执行代码.当它确定它将采用分支时,它必须使其无效,并从分支目标开始.

大多数现代处理器现在都有某种分支预测,但这只会在您之前通过分支时提供帮助,并且分支仍在分支预测缓存中.

编译器和处理器可以在这些场景中使用许多其他策略.您可以在维基百科上找到有关分支预测变量如何工作的更多详细信息:http://en.wikipedia.org/wiki/Branch_predictor

Answer 4

它们使编译器发出硬件支持它们的相应分支提示.这通常只意味着在指令操作码中篡改几位,因此代码大小不会改变.CPU将开始从预测位置获取指令,并在达到分支时刷新管道并重新开始,如果结果是错误的话.在提示正确的情况下,这将使分支更快 - 确切地说,取决于硬件的速度有多快; 以及这对代码性能的影响程度取决于时间提示的正确比例.

例如,在PowerPC CPU上,一个未打印的分支可能需要16个周期,一个正确提示的8个和一个错误提示的24个.在最里面的循环中,良好的提示可以产生巨大的差异.

可移植性并不是真正的问题 - 可能是定义在每个平台的标题中; 您可以简单地为不支持静态分支提示的平台定义"可能"和"不太可能".

Answer 5

（一般评论 - 其他答案涵盖了细节）

您没有理由因为使用它们而失去可移植性。

您始终可以选择创建一个简单的零效果“内联”或宏，以便您可以使用其他编译器在其他平台上进行编译。

如果您使用其他平台，您将无法获得优化的好处。

Answer 6

long __builtin_expect(long EXP, long C);

此构造告诉编译器表达式EXP很可能具有值C.返回值为EXP. __builtin_expect旨在用于条件表达式.在几乎所有情况下,它都将在布尔表达式的上下文中使用,在这种情况下,定义两个辅助宏更方便:

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

然后可以使用这些宏

if (likely(a > 1))

参考:https://www.akkadia.org/drepper/cpumemory.pdf