C言語のIf-Else演算子とTernary演算子の速度差は？

Question

だから同僚の提案で、私は三元演算子とそれに相当するIf-Elseブロックの速度差をテストしました...三項演算子はIf-Elseよりも1倍から2倍高速なコードを生成するようです。私のコードは次のとおりです。

gettimeofday(&tv3, 0); 
    for(i = 0; i < N; i++) 
    { 
    a = i & 1; 
    if(a) a = b; else a = c; 
    } 
    gettimeofday(&tv4, 0); 


    gettimeofday(&tv1, 0); 
    for(i = 0; i < N; i++) 
    { 
    a = i & 1; 
    a = a ? b : c; 
    } 
    gettimeofday(&tv2, 0); 

（にclock_gettimeはgettimeofdayを使用していないため申し訳ありませんが...私は自分自身をより良くするために努力します。）

私はブロックをタイミング順序を変更しようとしたが、結果は思えます持続する。何がありますか？また、If-Elseは実行速度の点ではるかに大きな変動性を示します。 gccが生成するアセンブリを調べるべきですか？

ところで、これはすべて最適化レベル0（-O0）です。

私はこれを想像しているのですか、私が考慮していないものがあるのですか、これはマシン依存のものなのでしょうか？どんな助けもありがとうございます。

Answer 1

3進演算子がcmovにコンパイルされる可能性はありますが、if/elseはcmp + jmpになります。確かにアセンブリを（-Sを使って）見てみましょう。最適化が有効になっていると、どんなに良いコンパイラでも同じコードが生成されるため、どちらの場合でも最適化が問題になることはありません。

Answer 2

最適化がオンになっている場合、まともなコンパイラはこれらに対して同じコードを生成する必要があります。

Answer 3

これは素敵な説明です：http://www.nynaeve.net/?p=178

基本的には、分岐および個別の命令で設定よりも高速である「条件付きセット」プロセッサ命令が存在します。

Answer 4

もしあれば、あなたのコンパイラを変更してください！

この種の質問については、Try Out LLVMページを使用しています。これはLLVMの古いリリースです（まだgccのフロントエンドを使用しています）が、これは古いトリックです。でも、それは中国の可能性が高いですので、

は

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind { 
entry: 
    %0 = load i8** %argv, align 8     ; <i8*> [#uses=1] 
    %N = tail call i32 @atoi(i8* %0) nounwind readonly ; <i32> [#uses=5] 

    %2 = getelementptr inbounds i8** %argv, i64 1 ; <i8**> [#uses=1] 
    %3 = load i8** %2, align 8      ; <i8*> [#uses=1] 
    %b = tail call i32 @atoi(i8* %3) nounwind readonly ; <i32> [#uses=2] 

    %5 = getelementptr inbounds i8** %argv, i64 2 ; <i8**> [#uses=1] 
    %6 = load i8** %5, align 8      ; <i8*> [#uses=1] 
    %c = tail call i32 @atoi(i8* %6) nounwind readonly ; <i32> [#uses=2] 

    %8 = icmp sgt i32 %N, 0       ; <i1> [#uses=2] 
    br i1 %8, label %bb, label %bb11 

bb:            ; preds = %bb, %entry 
    %9 = phi i32 [ %10, %bb ], [ 0, %entry ]  ; <i32> [#uses=2] 
    %10 = add nsw i32 %9, 1       ; <i32> [#uses=2] 
    %exitcond22 = icmp eq i32 %10, %N    ; <i1> [#uses=1] 
    br i1 %exitcond22, label %bb10.preheader, label %bb 

bb10.preheader:         ; preds = %bb 
    %11 = and i32 %9, 1        ; <i32> [#uses=1] 
    %12 = icmp eq i32 %11, 0      ; <i1> [#uses=1] 
    %.pn13 = select i1 %12, i32 %c, i32 %b   ; <i32> [#uses=1] 
    %tmp21 = add i32 %N, -1       ; <i32> [#uses=1] 
    %a.1 = add i32 %.pn13, %tmp21     ; <i32> [#uses=2] 
    br i1 %8, label %bb6, label %bb11 

bb6:            ; preds = %bb6, %bb10.preheader 
    %13 = phi i32 [ %14, %bb6 ], [ 0, %bb10.preheader ] ; <i32> [#uses=2] 
    %14 = add nsw i32 %13, 1      ; <i32> [#uses=2] 
    %exitcond = icmp eq i32 %14, %N     ; <i1> [#uses=1] 
    br i1 %exitcond, label %bb10.bb11_crit_edge, label %bb6 

bb10.bb11_crit_edge:        ; preds = %bb6 
    %15 = and i32 %13, 1       ; <i32> [#uses=1] 
    %16 = icmp eq i32 %15, 0      ; <i1> [#uses=1] 
    %.pn = select i1 %16, i32 %c, i32 %b   ; <i32> [#uses=1] 
    %tmp = add i32 %N, -1       ; <i32> [#uses=1] 
    %d.1 = add i32 %.pn, %tmp      ; <i32> [#uses=1] 
    br label %bb11 

bb11:            ; preds = %bb10.bb11_crit_edge, %bb10.preheader, %entry 
    %a.0 = phi i32 [ %a.1, %bb10.bb11_crit_edge ], [ %a.1, %bb10.preheader ], [ 0, %entry ] ; <i32> [#uses=1] 
    %d.0 = phi i32 [ %d.1, %bb10.bb11_crit_edge ], [ 0, %bb10.preheader ], [ 0, %entry ] ; <i32> [#uses=1] 
    %17 = tail call i32 (i8*, ...)* @printf(i8* noalias getelementptr inbounds ([6 x i8]* @.str, i64 0, i64 0), i32 %a.0, i32 %d.0) nounwind ; <i32> [#uses=0] 
    ret i32 0 
} 

オーケー：ここ

は（あなたの簡易版）私の小さなサンプルプログラムです：

#include <stdio.h> 
#include <stdlib.h> 
#include <sys/time.h> 

int main (int argc, char* argv[]) { 
    int N = atoi(argv[0]); 

    int a = 0, d = 0, b = atoi(argv[1]), c = atoi(argv[2]); 

    int i; 
    for(i = 0; i < N; i++) 
    { 
    a = i & 1; 
    if(a) a = b+i; else a = c+i; 
    } 

    for(i = 0; i < N; i++) 
    { 
    d = i & 1; 
    d = d ? b+i : c+i; 
    } 

    printf("%d %d", a, d); 

    return 0; 
} 

、対応するLLVM IRが生成されています私は先に進んで、読みやすいようにいくつかの変数の名前を変更しました。

重要なビットは、これら二つのブロックです：

それぞれ aと dを設定

%.pn13 = select i1 %12, i32 %c, i32 %b   ; <i32> [#uses=1] 
    %tmp21 = add i32 %N, -1       ; <i32> [#uses=1] 
    %a.1 = add i32 %.pn13, %tmp21     ; <i32> [#uses=2] 

    %.pn = select i1 %16, i32 %c, i32 %b   ; <i32> [#uses=1] 
    %tmp = add i32 %N, -1       ; <i32> [#uses=1] 
    %d.1 = add i32 %.pn, %tmp      ; <i32> [#uses=1] 

。

そして結論は次のとおりです。は違い

注：2つの変数が実際に合併してしまった単純な例では、オプティマイザが類似性を検出しなかったことをここに思えます...

Answer 5

また、完全無店舗に行くと、それはどんな違いがあれば測定できる：今日のアーキテクチャでは

int m = -(i & 1); 
a = (b & m) | (c & ~m); 

は、プログラミングのこのスタイルは、流行の外に少し成長してきました。

Answer 6

（実際には（インライン）asmにしない限り）三項式をどのように解釈するのかは、コンパイラーによって異なります。これは、内部表現言語で 'if..else'という三項式を容易に理解することができ、ターゲットバックエンドに応じて、条件付き移動命令を生成することもできます（x86ではCMOVccはそのようなものです。 min/max、absなど）。条件付き移動を使用する主な動機は、分岐予測ミスのリスクをメモリ/レジスタ移動操作に転送することです。ほとんどの場合、条件付きでロードされるオペランド・レジスタは、cmov命令を利用するためにレジスタ・フォームに評価される必要があります。

これは、無条件評価プロセスが無条件である必要があり、プログラムの無条件パスの長さが長くなるように見えることを意味します。しかし、ブランチ誤予測はパイプラインを「フラッシング」することで解決されることが最も多いことを理解しています。つまり、実行を終了した命令は無視されます（No Operation命令に変わります）。これは、実際に実行される命令の数が、ストールまたはNOPのために高くなっていることを意味し、プロセッサパイプラインの深さおよび予測ミス率によってスケーリングされます。

これは、適切なヒューリスティックを決定する上で興味深いジレンマをもたらします。まず、パイプラインが浅すぎる場合や分岐予測が分岐履歴からパターンを完全に学習できない場合、cmovは価値がないことを確認します。条件付き議論の評価のコストが、平均的な誤予測からのコストよりも大きければ、それは価値がない。

これはおそらく、ヒューリスティックの決定が主に実行時プロファイリング情報に依存するため、コンパイラがcmov命令を利用するのが難しい主な理由になります。これはJITコンパイラでこれを使用する方が理にかなっています。これは、ランタイム計測フィードバックを提供し、これを使用するためのより強力なヒューリスティックを構築できるからです（「ブランチは本当に予測不可能ですか？」）。訓練データやプロファイラーのない静的コンパイラー側では、これが便利なときを想定するのが最も難しいです。しかし、前述のように、単純な負のヒューリスティックは、データセットが完全にランダムまたは強制的にcondであることをコンパイラが知っている場合です。 uncondする。評価はコストがかかります（おそらく、fp除算のような既約で高価な演算のために）、これを実行しないような優れたヒューリスティックを作成します。

その塩の価値のあるコンパイラはすべてそれを行います。質問は、すべての信頼できるヒューリスティックが使い果たされた後に何をするのでしょうか...