4

この質問は、ソフトウェア側からの分岐予測の改善に関する Aater Suleman によるこの記事を読んだ後のフォローアップです。著者は、2 ビット飽和カウンタ方式の場合に分岐が発生することを予測する確率を高めるなど、条件文を「展開」する方法を提供しています。ここに抜粋があります：

例を挙げて説明しましょう。X が 0 から 99 までの確率変数であるとします。次のコードを実行します。

if (X > 5 && X < 95) //90% の確率で分岐する
do_something();

ただし、コードを次のように記述した場合:

if(X > 5) //95% の確率
で分岐する if(X < 95) //95% の確率で分岐する
do_something();

ブランチ プレディクタは、これらの両方のブランチをより正確に予測するのに適しています。これは、これらの両方のブランチに割り当てられたカウンタが、実行時に飽和状態のままになる可能性が高いためです (2 つの分岐が実行されない可能性が低いため)。

一般に、if ステートメントで条件を AND/OR するときはいつでも、組み合わせの偏りが大きいか偏りが少ないかを考え、より偏りのあるバージョンを選択する必要があります。

私の質問は次のとおりです。コンパイラは常にこのヒューリスティックに従いますか? コンパイラはISAとアーキテクチャの範囲に存在し、分岐予測スキームはプロセッサとより具体的なハードウェア実装の範囲に存在するため、コンパイラにはこのようなことを行う権限さえありますか?

私の直感では、そのような方法で制御ステートメントを拡張してもパフォーマンスが損なわれることはありませんが、同時に、コンパイラがそのような最適化を行うという証拠を見つけることができませんでした. もしそうなら、なぜ彼らはしないのですか？私の推論には何が欠けていますか?誰かがそのような最適化が特定のアーキテクチャまたは予測スキームに関して有害である例を提供できますか?

ありがとう。

4

2 に答える 2

4

Suleman はそのことを認識していないようです。

if (X > 5 && X < 95)
  do_something();

と

if(X > 5)
  if(X < 95)
    do_something();

C と C++ で意味的に同等です。最新の C 標準状態 (6.5.13/4):

ビットごとのバイナリ & 演算子とは異なり、&& 演算子は左から右への評価を保証します。2 番目のオペランドが評価される場合、1 番目と 2 番目のオペランドの評価の間にシーケンス ポイントがあります。最初のオペランドが 0 と等しい場合、2 番目のオペランドは評価されません。

コンパイラは、両方のコード サンプルに対して同じコードを生成する場合と生成しない場合があります。パフォーマンスを向上させるために、どちらかの形式を使用するようにプログラムを書き直すことはお勧めできません。結果は、コンパイラのバージョン、ISA、およびおそらくその他の変数に大きく依存します。このタイプの最適化はコンパイラーに任せますが、必要な情報はコンパイラーに提供してください。

GCC や LLVM などの一部のコンパイラでは、次のような明示的なヒントを与えることができます。

if (__builtin_expect(X > 5, 1)) {
  // This block is likely to be taken.
}
if (__builtin_expect(X <= 5, 0)) {
  // This block is unlikely to be taken.
}

もう 1 つの方法は、プロファイルに基づく最適化を使用することです。最初のステップでは、分岐命令に関する統計情報を含むデータベースを生成するために、プログラムを 1 回以上テスト実行する必要があります。2 番目のステップで、コンパイラはこのデータベースを使用してプログラムを最適化できます。詳細については、コンパイラのマニュアルを参照してください。

于 2013-01-08T18:52:44.473 に答える