168

#define私は彼らが使用しているに出くわしました__builtin_expect。

ドキュメントには次のように書かれています。

組み込み関数：long __builtin_expect (long exp, long c)

__builtin_expectコンパイラに分岐予測情報を提供するために使用できます。-fprofile-arcs一般に、プログラマーはプログラムが実際にどのように実行されるかを予測するのが苦手なので、これには実際のプロファイルフィードバックを使用することをお勧めします（ ）。ただし、このデータを収集するのが難しいアプリケーションがあります。

戻り値はの値でありexp、整数式である必要があります。ビルトインのセマンティクスは、が期待されるということ exp == cです。例えば：

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

fooはゼロであると予想されるため、を呼び出すことを期待していないことを示しxます。

では、直接使用しないのはなぜですか。

if (x)
    foo ();

__builtin_expect？を使用した複雑な構文の代わりに

4

7 に答える 7

216

以下から生成されるアセンブリコードを想像してみてください。

if (__builtin_expect(x, 0)) {
    foo();
    ...
} else {
    bar();
    ...
}

私はそれが次のようなものでなければならないと思います：

  cmp   $x, 0
  jne   _foo
_bar:
  call  bar
  ...
  jmp   after_if
_foo:
  call  foo
  ...
after_if:

（Cコードではなく）barケースがケースに先行するように命令が配置されていることがわかります。fooジャンプによって既にフェッチされた命令がスローされるため、これによりCPUパイプラインをより有効に活用できます。

ジャンプが実行される前に、その下の命令（barケース）がパイプラインにプッシュされます。fooケースが発生する可能性は低いため、ジャンプも発生する可能性は低く、パイプラインをスラッシングする可能性はほとんどありません。

于 2011-09-08T11:14:34.113 に答える
60

逆コンパイルして、GCC4.8がそれで何をするかを見てみましょう

Blagovestは、パイプラインを改善するためにブランチインバージョンについて言及しましたが、現在のコンパイラは実際にそれを行っていますか？確認してみましょう！

それなし__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)
        puts("a");
    return 0;
}

GCC 4.8.2x86_64Linuxでコンパイルおよび逆コンパイルします。

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 0a                   jne    1a <main+0x1a>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1
  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

メモリ内の命令の順序は変更されていません。最初に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 07                   je     17 <main+0x17>
  10:       31 c0                   xor    %eax,%eax
  12:       48 83 c4 08             add    $0x8,%rsp
  16:       c3                      retq
  17:       bf 00 00 00 00          mov    $0x0,%edi
                    18: R_X86_64_32 .rodata.str1.1
  1c:       e8 00 00 00 00          callq  21 <main+0x21>
                    1d: R_X86_64_PC32       puts-0x4
  21:       eb ed                   jmp    10 <main+0x10>

関数のputs最後、retqリターンに移動しました！

新しいコードは基本的に次のものと同じです。

int i = !time(NULL);
if (i)
    goto puts;
ret:
return 0;
puts:
puts("a");
goto ret;

この最適化はで行われませんでした-O0。

__builtin_expectしかし、使用しない場合よりも使用した場合の方が高速に実行される例を書いて頑張ってください。当時のCPUは本当に賢いです。私の素朴な試みはここにあります。

C++20[[likely]]および[[unlikely]]

C ++ 20は、これらのC++ビルトインを標準化しました。if -elseステートメントでC++ 20のlike/unlikely属性を使用する方法彼らはおそらく（しゃれ！）同じことをします。

于 2015-07-21T13:35:00.800 に答える
41

の考え方は__builtin_expect、式がcに評価されることが通常あることをコンパイラーに通知して、コンパイラーがその場合に最適化できるようにすることです。

誰かが自分が賢いと思っていて、これを行うことで物事をスピードアップしていると思います。

残念ながら、状況が非常によく理解されていない限り（彼らがそのようなことをしていない可能性が高い）、それは事態を悪化させた可能性があります。ドキュメントには次のようにも書かれています。

-fprofile-arcs一般に、プログラマーはプログラムが実際にどのように実行されるかを予測するのが苦手なので、これには実際のプロファイルフィードバックを使用することをお勧めします（ ）。ただし、このデータを収集するのが難しいアプリケーションがあります。

一般に、次の場合を除いて使用し__builtin_expectないでください。

  • 非常に現実的なパフォーマンスの問題があります
  • システムのアルゴリズムはすでに適切に最適化されています
  • 特定のケースが最も可能性が高いという主張を裏付けるパフォーマンスデータがあります
于 2011-09-08T11:03:59.067 に答える
13

説明で述べているように、最初のバージョンは構造に予測要素を追加し、x == 0ブランチがより可能性が高いこと、つまり、プログラムによってより頻繁に取得されるブランチであることをコンパイラーに通知します。

そのことを念頭に置いて、コンパイラーは条件を最適化して、予期された条件が成立したときに必要な作業量を最小限に抑えることができますが、予期しない条件が発生した場合はさらに多くの作業を行う必要があります。

コンパイルフェーズで条件がどのように実装されているか、また結果のアセンブリでどのように実装されているかを見て、一方のブランチがもう一方のブランチよりも作業が少ない可能性があることを確認してください。

ただし、結果のコードの違いは比較的小さいため、問題の条件が頻繁に呼び出されるタイトな内部ループの一部である場合にのみ、この最適化が顕著な効果をもたらすと期待します。また、間違った方法で最適化すると、パフォーマンスが低下する可能性があります。

于 2011-09-08T11:02:44.873 に答える
1

言い換えれば、あなたが尋ねていたと思う質問に対処する答えは見当たりません。

分岐予測をコンパイラに示唆する、より移植性の高い方法はありますか？

あなたの質問のタイトルは私にそれをこのようにすることを考えさせました：

if ( !x ) {} else foo();

コンパイラが「true」の可能性が高いと想定した場合、を呼び出さないように最適化できfoo()ます。

ここでの問題は、一般に、コンパイラが何を想定するかがわからないことです。したがって、この種の手法を使用するコードは、注意深く測定する必要があります（コンテキストが変更された場合は、時間をかけて監視する必要があります）。

于 2015-05-31T18:25:00.400 に答える
0

@BlagovestBuyuklievと@Ciroに従ってMacでテストします。アセンブルは明確に見え、コメントを追加します。

コマンドは gcc -c -O3 -std=gnu11 testOpt.c; otool -tVI testOpt.o

-O3を使用すると、__ builtin_expect（i、0）が存在するかどうかに関係なく、同じように見えます。 

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp     
0000000000000001    movq    %rsp, %rbp    // open function stack
0000000000000004    xorl    %edi, %edi       // set time args 0 (NULL)
0000000000000006    callq   _time      // call time(NULL)
000000000000000b    testq   %rax, %rax   // check time(NULL)  result
000000000000000e    je  0x14           //  jump 0x14 if testq result = 0， namely jump to puts
0000000000000010    xorl    %eax, %eax   //  return 0   ,  return appear first 
0000000000000012    popq    %rbp    //  return 0
0000000000000013    retq                     //  return 0
0000000000000014    leaq    0x9(%rip), %rdi  ## literal pool for: "a"  // puts  part, afterwards
000000000000001b    callq   _puts
0000000000000020    xorl    %eax, %eax
0000000000000022    popq    %rbp
0000000000000023    retq

-O2を使用してコンパイルすると、__ builtin_expect（i、0）を使用した場合と使用しない場合で外観が異なります。

最初になし

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    jne 0x1c       //   jump to 0x1c if not zero, then return
0000000000000010    leaq    0x9(%rip), %rdi ## literal pool for: "a"   //   put part appear first ,  following   jne 0x1c
0000000000000017    callq   _puts
000000000000001c    xorl    %eax, %eax     // return part appear  afterwards
000000000000001e    popq    %rbp
000000000000001f    retq

今__builtin_expect（i、0）で

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    je  0x14   // jump to 0x14 if zero  then put. otherwise return 
0000000000000010    xorl    %eax, %eax   // return appear first 
0000000000000012    popq    %rbp
0000000000000013    retq
0000000000000014    leaq    0x7(%rip), %rdi ## literal pool for: "a"
000000000000001b    callq   _puts
0000000000000020    jmp 0x10

要約すると、__builtin_expectは最後のケースで機能します。

于 2019-08-21T07:03:13.030 に答える
0

ほとんどの場合、分岐予測はそのままにしておく必要があり、心配する必要はありません。

それが有益である1つのケースは、多くの分岐を伴うCPU集約型アルゴリズムです。場合によっては、ジャンプによってが現在のCPUプログラムキャッシュを超え、CPUがソフトウェアの次の部分の実行を待機する可能性があります。最後にありそうもない枝を押すことによって、あなたはあなたの記憶を近くに保ち、ありそうもない場合にのみジャンプするでしょう。

于 2020-10-22T11:39:49.980 に答える