22

2 つの数値のうち小さい方を取得するプログラムが必要ですが、「x が y より小さい場合」という標準を使用するかどうか疑問に思っています。

int a, b, low;
if (a < b) low = a;
else low = b;

これより多かれ少なかれ効率的です：

int a, b, low;
low = b + ((a - b) & ((a - b) >> 31));

（または、int delta = a - b一番上に置き、インスタンスをそれで置き換えるバリエーションa - b）。

私は、これらのうちどれがより効率的であるか (または、違いが小さすぎて関連性がない場合)、および if-else ステートメントと一般的な選択肢の効率性を考えています。

4

16 に答える 16

31

（免責事項：以下は、ほとんどの場合必要のない非常に低レベルの最適化を扱います。読み続けると、コンピューターが高速であり、この種のことを心配する理由がないことを訴える権利を放棄します。）

ステートメントを削除する利点の1つifは、分岐予測のペナルティを回避できることです。

分岐予測のペナルティは、一般に、分岐が簡単に予測されない場合にのみ問題になります。分岐は、ほとんどの場合、取得される場合と取得されない場合、または単純なパターンに従う場合に簡単に予測できます。たとえば、ループステートメントの分岐は最後の分岐を除いて毎回行われるため、簡単に予測できます。ただし、次のようなコードがある場合

a = random() % 10
if (a < 5)
  print "Less"
else
  print "Greater"

その場合、このブランチは簡単に予測できず、ブランチの間違った部分で実行されたキャッシュのクリアと命令のロールバックに関連する予測ペナルティが頻繁に発生します。

この種のペナルティを回避する1つの方法は、三項（?:）演算子を使用することです。単純なケースでは、コンパイラーはブランチではなく条件付き移動命令を生成します。

それで

int a, b, low;
if (a < b) low = a;
else low = b;

になります

int a, b, low;
low = (a < b) ? a : b

2番目のケースでは、分岐命令は必要ありません。さらに、ビットをいじる実装よりもはるかに明確で読みやすくなっています。

もちろん、これはマイクロ最適化であり、コードに大きな影響を与える可能性はほとんどありません。

于 2010-06-09T20:38:28.820 に答える
9

簡単な答え：1つの条件付きジャンプは、2つの減算、1つの加算、ビット単位のand、およびシフト演算を組み合わせたものよりも効率的です。 私はこの点について十分に教育を受けており（コメントを参照）、通常はより効率的であると言うほど自信がありません。

実用的な答え：いずれにせよ、プログラマーがその2番目の例が何をしているのかを理解するのにかかる時間ほど、余分なCPUサイクルにほとんどお金を払っていません。最初に読みやすさ、次に効率のためのプログラム。

于 2010-06-09T20:39:43.280 に答える
8

これを gcc 4.3.4、amd64 (core 2 duo)、Linux でコンパイル:

int foo1(int a, int b)
{
    int low;
    if (a < b) low = a;
    else low = b;
    return low;
}

int foo2(int a, int b)
{
    int low;
    low = b + ((a - b) & ((a - b) >> 31));
    return low;
}

私は得る：

foo1:
    cmpl    %edi, %esi
    cmovle  %esi, %edi
    movl    %edi, %eax
    ret

foo2:
    subl    %esi, %edi
    movl    %edi, %eax
    sarl    $31,  %eax
    andl    %edi, %eax
    addl    %esi, %eax
    ret

...コードがジャンプしないため、分岐予測にはカウントされないと確信しています。また、if ステートメントのないバージョンは 2 命令長くなります。私はコーディングを続け、コンパイラーに仕事を任せようと思います。

于 2010-06-09T23:18:55.407 に答える
7

最大の問題は、2番目の例が64ビットマシンでは機能しないことです。

ただし、それを無視しても、最新のコンパイラは、可能な限りブランチレス予測を検討し、推定速度を比較するのに十分なほど賢いです。したがって、2番目の例は実際には遅くなる可能性があります

ほとんどのダムコンパイラでさえこの特殊なケースを認識するのに十分賢いので、ifステートメントと三項演算子の使用に違いはありません。

【編集】これはとても面白いトピックだと思うので、ブログに投稿しました。

于 2010-06-09T20:59:42.113 に答える
7

低レベルの最適化と同様に、ターゲットの CPU/ボードのセットアップでテストします。

私のコンパイラ (x86_64 上の gcc 4.5.1) では、最初の例は次のようになります。

cmpl    %ebx, %eax
cmovle  %eax, %esi

2番目の例は次のようになります

subl    %eax, %ebx
movl    %ebx, %edx
sarl    $31, %edx
andl    %ebx, %edx
leal    (%rdx,%rax), %esi

すべてのケースで最初のものの方が速いかどうかはわかりませんが、きっと速いでしょう。

于 2010-06-09T21:16:21.053 に答える
4

このような単純なことについては、実験して試してみませんか?

通常、最初にプロファイリングし、これをホットスポットとして識別し、変更を試して結果を表示します。

乱数を渡す (完全な分岐予測が表示されないようにするため) 両方の手法を Visual C++ 2010 と比較する簡単なプログラムを作成しました。合計で 50 ミリ秒未満で、if バージョンの方が高速になる傾向がありました。codegen を見ると、コンパイラは単純な if を cmovl 命令に正常に変換し、分岐を完全に回避しています。

于 2010-06-09T21:18:01.627 に答える
4

いずれにせよ、アセンブリはほんの数命令で済み、いずれにしても、それらの命令の実行にはピコ秒かかります。

アプリケーションのプロファイルを作成して、最適化の取り組みをより価値のあるものに集中させます。

また、このタイプの最適化によって節約された時間は、それを維持しようとする人が浪費する時間に見合うものではありません。

このような単純なステートメントの場合、三項演算子は非常に直感的です。

low = (a < b) ? a : b;

明確かつ簡潔。

于 2010-06-09T20:34:59.453 に答える
1

私は、これらのどれがより効率的であるか（または、違いが関連性が非常に小さいかどうか）、およびif-elseステートメントと一般的な選択肢の効率性を考えています。

デスクトップ/サーバー CPU は、パイプライン用に最適化されています。CPU は分岐する必要がなく、複数の ALU を使用して式の一部を並列に評価できるため、理論的には 2 番目の方が高速です。このような CPU には、独立した操作が混在する非分岐コードが最適です。（しかし、それでさえ、最初のコードをブランチレスにすることを可能にする最新の「条件付き」CPU命令によって現在否定されています。）

組み込み CPU では、多くの場合 (他のすべてのものと比較して) 安価である場合に分岐します。また、操作を順不同で評価するための多くの予備の ALU もありません (順不同の実行をまったくサポートしている場合)。コード/データが少ないほど良い - キャッシュも小さい。(私は、組み込みアプリケーションでブーブルソートを使用することさえ見てきました。このアルゴリズムは、メモリ/コードを最小限しか使用せず、少量の情報に対して十分に高速です。)

重要: コンパイラの最適化を忘れないでください。多くのトリックを使用して、コンパイラは、インライン化、定数の伝播、リファクタリングなどの分岐自体を削除できる場合があります。

しかし、最終的には、そうです。違いはごくわずかであり、関連性があるとは言えません。長期的には、読みやすいコードが勝ちます。

CPU の面では、コードをマルチスレッド化して OpenCL 対応にするために今時間を費やすことは、よりやりがいがあります。

于 2010-06-10T16:02:28.393 に答える
1

このような最適化は、他の問題によって簡単に圧倒される可能性があることに気付いていませんでした。たとえば、このルーチンを 2 つの大きな数値配列 (さらに悪いことに、メモリに散在する数値のペア) で実行している場合、現在の CPU で値をフェッチするコストにより、CPU の実行パイプラインが簡単に停止する可能性があります。

于 2010-06-09T20:46:55.333 に答える
0

gcc -o foo -g -p -O0、Solaris9v240でのプロファイル結果

 %Time Seconds Cumsecs  #Calls   msec/call  Name
  36.8    0.21    0.21 8424829      0.0000  foo2
  28.1    0.16    0.37       1    160.      main
  17.5    0.10    0.4716850667      0.0000  _mcount
  17.5    0.10    0.57 8424829      0.0000  foo1
   0.0    0.00    0.57       4      0.      atexit
   0.0    0.00    0.57       1      0.      _fpsetsticky
   0.0    0.00    0.57       1      0.      _exithandle
   0.0    0.00    0.57       1      0.      _profil
   0.0    0.00    0.57    1000      0.000   rand
   0.0    0.00    0.57       1      0.      exit

コード：

int
foo1 (int a, int b, int low)        
{
   if (a < b) 
      low = a;   
   else 
      low = b;         
   return low;
}

int                       
foo2 (int a, int b, int low)
{
   low = (a < b) ? a : b;
   return low;
}


int main()
{
    int low=0;
    int a=0;
    int b=0;
    int i=500;
    while (i--)
    {
       for(a=rand(), b=rand(); a; a--)
       {
           low=foo1(a,b,low);
           low=foo2(a,b,low);
       }        
    }
    return 0;
}

データに基づくと、上記の環境では、ここで述べられているいくつかの信念の正反対は真実ではありませんでした。'この環境では'構造が三項よりも速かった場合は？：構築する

于 2010-06-09T21:40:20.713 に答える
0

なぜとで？low = a;_ そして、なぜですか？31がCPUワードサイズと関係がある場合、コードが異なるサイズのCPUで実行されるとしたらどうでしょうか。iflow = a;else31

if..elseの方法はより読みやすく見えます。私は、プログラムがコンパイラーと同じように人間にも読めるようにするのが好きです。

于 2010-06-09T20:40:50.360 に答える
-1

あなたが本当に効率を抑えようとしているのでない限り、これはあなたが心配する必要があることではないと思います。

私の単純な考えは、他のコードがいくつかの操作を実行している間に、1つのことを比較しているので、ifの方が速いということです。しかし、繰り返しになりますが、違いはごくわずかだと思います。

于 2010-06-09T20:38:48.110 に答える
-1

Gnu C++の場合は、これを試してください

int min = i <? j;

私はそれをプロファイリングしていませんが、間違いなく打ち負かすものだと思います.

于 2010-06-09T23:03:10.040 に答える