13

抽象的すぎる質問で申し訳ありませんが、私にとっては非常に実用的です + 一部の専門家は同様の経験があり、説明できる可能性があります。

約 10000 行の大きなコードがあります。

ある場所に置くと気づきます

if ( expression ) continue;

ここで、expression は常に false (コードと cout のロジックで二重にチェックされます) ですが、不明なパラメーターに依存します (そのため、コンパイラーはコンパイル中にこの行を単純に取り除くことはできません)。プログラムの速度は25% 向上します (計算の結果同じだ）。ループ自体の速度を測定すると、速度アップ係数は 3 より大きくなります。

なぜこれが起こるのか、また、そのようなトリックなしでこのスピードアップの可能性を利用する方法は何ですか?

PS私はgcc 4.7.3、-O3最適化を使用しています。

より詳しい情報：

  1. 2 つの異なる表現を試しましたが、どちらも機能します。

  2. 行を次のように変更すると:

    if ( expression ) { cout << " HELLO " << endl; continue; };

    スピードアップはなくなりました。

  3. 行を次のように変更すると:

    expression;

    スピードアップはなくなりました。

  4. 行を囲むコードは次のようになります。

    for ( int i = a; ;  ) {
  do {
    i += d;
    if ( d*i > d*ilast ) break;

      // small amount of calculations, and conditional calls of continue;

  } while ( expression0 );
  if ( d*i > dir*ilast ) break;

  if ( expression ) continue;

   // very big amount calculations, and conditional calls of continue;

}

    for ループが奇妙に見えます。これは、このボトルネックをキャッチするためにループを修正したためです。当初、expression は expression0 に等しく、do-loop の代わりにこれだけを継続しました。

  5. 分岐予測を理解するために __builtin_expect を使ってみました。と

      // the expression (= false) is supposed to be true by branch prediction.
if ( __builtin_expect( !!(expression), 1) ) continue;

    スピードアップは 25% です。

      // the expression (= false) is supposed to be false by branch prediction.
if ( __builtin_expect( !!(expression), 0) ) continue;

    スピードアップはなくなりました。

  6. -O3 の代わりに -O2 を使用すると、効果がなくなります。このコードは、False 条件を使用した高速 O3 バージョンよりもわずかに (~3%) 遅くなります。

  7. 「-O2 -finline-functions -funswitch-loops -fpredictive-commoning -fgcse-after-reload -ftree-vectorize」も同様です。もう 1 つのオプション: "-O2 -finline-functions -funswitch-loops -fpredictive-commoning -fgcse-after-reload -ftree-vectorize -fipa-cp-clone" を使用すると、効果が増幅されます。「ライン」を使用しても速度は同じですが、「ライン」を使用しない場合、コードは 75% 遅くなります。

  8. その理由は、次の条件演算子にあります。したがって、コードは次のようになります。

    for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  if ( expression ) continue;

    // calculations1

  if ( expression2 ) {
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

    ほとんどの場合、expression2 の値は false です。だから私はそれを次のように変更しました：

    for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  // if ( expression ) continue; // don't need this anymore

    // calculations1

  if ( __builtin_expect( !!(expression2), 0 ) ) { // suppose expression2 == false
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

    そして、望ましい25％のスピードアップを手に入れました。もう少しでも。そして、行動はクリティカルラインに依存しなくなりました。

推測なしでこの動作を説明できる資料を誰かが知っている場合、私は彼らの答えを読んで受け入れることを非常に嬉しく思います.

4

3 に答える 3

3

それを見つけた。

その理由は、直後の条件演算子にありました。したがって、コードは次のようになります。

for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  if ( expression ) continue;

    // calculations1

  if ( expression2 ) {
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

ほとんどの場合、expression2 の値は false です。そこで、次のように変更しました。

for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  // if ( expression ) continue; // don't need this anymore

    // calculations1

  if ( __builtin_expect( !!(expression2), 0 ) ) { // suppose expression2 == false
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

そして、望ましい25％のスピードアップを手に入れました。もう少しでも。そして、行動はクリティカルラインに依存しなくなりました。

それを説明する方法がわからず、分岐予測に関する十分な資料が見つかりません。

しかし、要点はcalculation2をスキップする必要があるということだと思いますが、コンパイラはこれを認識せず、デフォルトでexpression2 == trueと想定しています。その間、単純な続行チェックで

if ( expression ) continue;

式 == false であり、どのような場合でも実行する必要があるため、calculation2 を適切にスキップします。より複雑な操作 (cout など) がある場合、式が true であり、トリックが機能しないと想定されます。

推測せずにこの動作を説明できる資料を誰かが知っている場合、私は彼らの答えを読んで受け入れることを非常に嬉しく思います。

于 2013-10-28T20:47:32.150 に答える
0

言いたくないのですが、答えはかなり技術的なものになり、さらに重要なことに、コードに非常に固有のものになります。そのため、あなた以外の誰もあなたの質問の根源を調査するために時間を費やすことはないでしょう。他の人が示唆しているように、分岐予測やパイプラインに関連するその他のコンパイル後の最適化に依存する可能性が非常に高いです。

これがコンパイラの最適化の問題であるか、コンパイル後 (CPU) の最適化であるかを絞り込むために私が提案できる唯一のことは、-O2vsを使用してコードを再度コンパイルすることです-O3が、今回は次の追加オプションを追加します -fverbose-asm -S。各出力を 2 つの異なるファイルにパイプし、sdiff などを実行してそれらを比較します。多くの違いが見られるはずです。

残念ながら、アセンブリ コードを十分に理解していなければ、理解するのは難しいでしょう。正直なところ、Stack Overflow でこの問題に数分以上費やす忍耐力 (または時間) を持っている人は多くありません。アセンブリ (おそらく x86) に堪能でない場合は、アセンブリの出力を解析するのに役立つ同僚や友人を見つけることをお勧めします。

于 2013-10-28T21:46:57.893 に答える
0

到達不可能な分岐の導入により、フロー グラフが分割されます。通常、コンパイラは、実行の流れがループの先頭から終了テストまで、そして最初に戻るということを認識しています。これで、フローがループから抜けることができるノードがグラフに追加されました。ここで、ループ本体を 2 つの部分に分けて別の方法でコンパイルする必要があります。

これにより、ほとんどの場合、コードが悪化します。ここにない理由は 1 つだけ推測できます。プロファイリング情報を使用してコンパイルしなかったためです。したがって、コンパイラは仮定を行う必要があります。特に、実行時に分岐が行われる可能性について想定する必要があります。

明らかに、前提条件が異なるため、生成されるコードの速度が異なる可能性は十分にあります。

于 2013-10-28T16:24:13.300 に答える