Cこのブランチレスハックは実際には高速ですか？

Question

私はCortex-Mベースのmicrocontrollerで-127と127の間の値をクランプしようとしています。

2つの競合する関数があります.1つは条件付きのものを使用し、もう1つは分岐なしのハックを使用します。hereです。

// Using conditional statements 
int clamp(int val) { return ((val > 127) ? 127 : (val < -127) ? -127 : val); } 

// Using branchless hacks 
int clamp(int val) { 
    val -= -127; 
    val &= (~val) >> 31; 
    val += -127; 
    val -= 127; 
    val &= val >> 31; 
    val += 127; 

    return val; 
} 

は今、私はこれらのいずれかの方法が他よりも高速であるかもしれないいくつかのケースでは知っている、そしてその逆が、一般的には、それはそれは本当に私には関係ないと見て無店舗技法を使用する価値があります私が使っているのは、私の場合はどちらもうまくいくでしょうか？

マイクロコントローラのバックグラウンドは、ARMベースのマイクロコントローラで、3段階のパイプライン、フェッチ、デコード、実行で90MIPSで動作しますが、何らかの分岐予測器があるようですが、詳細を掘り下げることはできませんでした。

Answer 1

ARMコード（-O3とGCC 4.6.3）：

clamp1: 
    mvn r3, #126 
    cmp r0, r3 
    movlt r0, r3 
    cmp r0, #127 
    movge r0, #127 
    bx lr 

clamp2: 
    add r0, r0, #127 
    mvn r3, r0 
    and r0, r0, r3, asr #31 
    sub r0, r0, #254 
    and r0, r0, r0, asr #31 
    add r0, r0, #127 
    bx lr 

Thumbコード：

clamp1: 
    mvn r3, #126 
    cmp r0, r3 
    it lt 
    movlt r0, r3 
    cmp r0, #127 
    it ge 
    movge r0, #127 
    bx lr 

clamp2: 
    adds r0, r0, #127 
    mvns r3, r0 
    and r0, r0, r3, asr #31 
    subs r0, r0, #254 
    and r0, r0, r0, asr #31 
    adds r0, r0, #127 
    bx lr 

どちらも、ARMの条件付き実行設計に無店舗感謝しています。私はあなたが本質的にパフォーマンスに匹敵すると賭けるでしょう。

Answer 2

ARMとx86アーキテクチャーは分岐命令に関して非常に異なっています。ジャンプを取るとパイプラインがクリアされ、スループットの面では、「どこにいたかに戻って」戻ってくるだけのクロックサイクルが必要になります。枝は条件付きで実行することだけを許可する

• ほとんどの命令セット、（http://simplemachines.it/doc/arm_inst.pdfのpg14）

  条件付き実行を先日ダウンロードしたPDFファイルを引用する

  。

• しかし、条件評価ハードウェアを再利用することによって、ARMは効果的に命令数を増やします。
• すべての命令には、CPUが実行するかどうかを決定する条件フィールドが含まれています。
• 実行されていない命令が1サイクル吸収されます。 - 次の命令のフェッチとデコードを可能にするためには、まだサイクルを完了していなければなりません。
• これにより、多くの分岐が不要になり、パイプラインが停止します（3サイクルのリフィル）。
• ブランチなしで非常に高密度のインラインコードを許可します。
• いくつかの条件付き命令を実行しない時間ペナルティは、しばしば必要となる分岐またはサブルーチン呼び出しのオーバーヘッドよりも小さい。

Answer 3

いいえ。C言語には速度がありません。それはCの実装によって導入されたコンセプトです。完全に最適なコンパイラは、両方を同じマシンコードに変換します。

Cコンパイラは、一般的なスタイルに準拠し、よく定義されたコードを最適化できる可能性が高くなります。 2番目の関数は明確に定義されていません。

これらの加算と減算により整数オーバーフローが発生する可能性があります。整数オーバーフローは未定義の動作ですので、プログラムが誤動作する可能性があります。楽観的には、ハードウェアがラッピングや飽和を実装する可能性があります。少し楽観的には、あなたのOSやコンパイラは整数オーバーフローのシグナルやトラップ表現を実装するかもしれません。整数のオーバーフローを検出すると、変数を変更したときのパフォーマンスに影響する可能性があります。最悪の場合、プログラムの整合性が失われます。

&と>>演算子は、符号付き型の実装定義の側面を持っています。それらは、トラップ表現の一例である負のゼロをもたらす可能性がある。トラップ表現を使用することは未定義の動作ですので、プログラムの整合性が失われる可能性があります。

おそらく、あなたのOSやコンパイラはintオブジェクトのパリティビットチェックを実装しています。この場合、変数が変更されるたびにパリティビットを再計算し、変数が読み取られるたびにパリティビットを検証することを想像してみてください。パリティチェックに失敗すると、プログラムの整合性が失われる可能性があります。

最初の機能を使用します。少なくともそれは明確に定義されています。あなたのプログラムが低速で実行されているように見える場合、このコードを最適化してもプログラムが大幅にスピードアップすることはありません。プロファイラを使用してより重要な最適化を見つけたり、より最適なOSやコンパイラを使用したり、高速なハードウェアを購入することができます。