1

高性能コードから条件付き分岐を削除する場合、真のブール値をに変換してunsigned long i = -1すべてのビットを設定すると便利です。

またはのいずれかの値をとるint b（または）の入力からこの整数マスクブール値を取得する方法を思いつきました：bool b10

unsigned long boolean_mask = -(!b);

反対の値を取得するには：

unsigned long boolean_mask = -b;

誰かが以前にこの構造を見たことがありますか？私は何かに取り組んでいますか？-1のint値（私が想定している-b、または-(!b)生成している）がより大きなunsigned int型にプロモートされると、すべてのビットが設定されることが保証されますか？

コンテキストは次のとおりです。

uint64_t ffz_flipped = ~i&~(~i-1); // least sig bit unset
// only set our least unset bit if we are not pow2-1
i |= (ffz_flipped < i) ? ffz_flipped : 0;

次回このような質問をする前に、生成されたasmを調べます。コンパイラがここでブランチをCPUに負担させない可能性が非常に高いようです。

4

4 に答える 4

5

あなたが自分自身に尋ねるべき質問はこれです：あなたが書くならば：

int it_was_true = b > c;

そのit_was_true場合、1または0のいずれかになります。しかし、その1はどこから来たのでしょうか。

マシンの命令セットには、次の形式の命令が含まれていません。

Compare R1 with R2 and store either 1 or 0 in R3

または、確かに、そのようなもの。（この回答の最後にSSEにメモを付けて、前のステートメントが完全に正しくないことを示しています。）マシンには、いくつかの条件ビットで構成される内部条件レジスタと、比較命令（およびその他のいくつか）があります。算術演算-これらの条件ビットを特定の方法で変更します。その後、いくつかの条件ビット、または条件付きロード、場合によっては他の条件付き操作に基づいて、条件付き分岐を実行できます。

したがって、実際には、条件付き操作を直接実行する場合よりも、その1を変数に格納する方がはるかに効率が悪い可能性があります。コンパイラー（または少なくともコンパイラーを作成した人）はあなたよりも賢いかもしれないので、そうではなかったかもしれませんが、そうではなかったかもしれませんit_was_true。値をチェックするために、コンパイラーは適切なブランチなどを発行できます。

したがって、巧妙なコンパイラについて言えば、次のように生成されたアセンブリコードを注意深く見る必要があります。

uint64_t ffz_flipped = ~i&~(~i-1);

その式を見ると、5つの演算を数えることができます。3つのビット単位の否定、1つのビット単位の接続詞（and）、および1つの減算です。ただし、アセンブリ出力には5つの操作はありません（少なくとも、gcc -O3を使用する場合）。あなたは3つ見つけるでしょう。

アセンブリの出力を見る前に、いくつかの基本的な代数を実行しましょう。最も重要なアイデンティティは次のとおりです。

-X == ~X + 1

なぜそうなのか分かりますか？-X、2の補数は、別の言い方です。ここで、はワードのビット数です。実際、それが「2の補数」と呼ばれる理由です。どうですか？これは、Xのすべてのビットを対応する2の累乗から減算した結果と考えることができます。たとえば、単語に4ビットがあり、（5、つまり2 2 + 2 0）である場合、次に、これは、と考えることができます。これは、とまったく同じです。または、言い換えると：2n - Xn~XX0101~X101023×(1-0) + 22×(1-1) + 21×(1-0) + 20×(1-1)1111 − 0101

 −X == 2n − X
  ~X == (2n−1) − X つまり、
  ~X == (−X) − 1

私たちが持っていたことを忘れないでください

ffz_flipped = ~i&~(~i-1);

minusしかし、〜（〜i-1）を操作に変更できることがわかりました。

~(~i−1)
== −(~i−1) − 1
== −(−i - 1 - 1) − 1
== (i + 2) - 1
== i + 1

なんてクールなんだ！私たちはちょうど書いたかもしれません：

ffz_flipped = ~i & (i + 1);

これは、5回ではなく3回の操作です。

さて、あなたがそれに従ったかどうかはわかりません、そしてそれを正しくするのに少し時間がかかりました、しかし今度はgccの出力を見てみましょう：

    leaq    1(%rdi), %rdx     # rdx = rdi + 1 
    movq    %rdi, %rax        # rax = rdi                                        
    notq    %rax              # rax = ~rax                             
    andq    %rax, %rdx        # rdx &= rax

それで、gccはちょうど行って、それをすべて自分で理解しました。

SSEに関する約束されたメモ：SSEは、2つの16バイトレジスタ間で一度に16バイト単位の比較を実行する場合でも、並列比較を実行できることがわかりました。条件レジスタはそのために設計されたものではなく、とにかく、分岐する必要がないときに分岐したいと思う人は誰もいません。したがって、CPUは実際にSSEレジスタの1つ（16バイトのベクトル、または8つの「ワード」または4つの「ダブルワード」、操作の指示に関係なく）をブールインジケーターのベクトルに変更します。1しかし、それはtrueには使用されません。代わりに、すべてののマスクを使用します1。なんで？-(!B)プログラマーがその比較結果で次に行うことは、値をマスクするためにそれを使用することである可能性が高いため、並列ストリーミングバージョンを除いて、これはまさにあなたがトリックで行うことを計画していたことだと思います。

だから、安心してください、それはカバーされています。

于 2012-12-17T02:32:12.637 に答える
1

誰かが以前にこの構造を見たことがありますか？私は何かに取り組んでいますか？

多くの人がそれを見てきました。それは岩のように古いです。これは珍しいことではありませんが、コードが難読化されないように、インライン関数にカプセル化する必要があります。

また、コンパイラが実際に古いコードでブランチを生成していること、正しく構成されていること、およびこのマイクロ最適化によって実際にパフォーマンスが向上することを確認してください。（そして、各最適化戦略がどれだけの時間を削減するかをメモしておくことをお勧めします。）

プラス面では、完全に標準に準拠しています。

-1のint値（-bまたは-（！b）が生成すると思います）がより大きなunsigned int型にプロモートされると、すべてのビットが設定されることが保証されますか？

bまだ署名されていないことに注意してください。符号なしの数値は常に正であるため、キャストの結果は-1u特別なものではなく、それ以上の数値で拡張されることはありません。

あなたが異なるサイズを持っていて、肛門になりたいならば、これを試してください：

template< typename uint >
uint mask_cast( bool f )
    { return static_cast< uint >( - ! f ); }
于 2012-12-17T01:16:07.380 に答える
0 
struct full_mask {
  bool b;
  full_mask(bool b_):b(b_){}
  template<
    typename int_type,
    typename=typename std::enable_if<std::is_unsigned<int_type>::value>::type
  >
  operator int_type() const {
    return -b;
  }
};

使用する：

unsigned long long_mask = full_mask(b);
unsigned char char_mask = full_mask(b);
char char_mask2 = full_mask(b); // does not compile

基本的に、クラスを使用しfull_maskてキャスト先の型を推測し、その型のビットで満たされた符号なしの値を自動的に生成します。変換しようとしている型が符号なし整数型であることを検出するために、いくつかのSFINAEコードを挿入しました。

于 2012-12-17T01:57:13.943 に答える
0

デクリメントするだけで1/0を0/-1に変換できます。これによりブール条件が反転しますが、最初にブールの逆を生成できる場合、またはマスクの逆を使用できる場合は、2つではなく1つの操作になります。

于 2015-12-16T07:24:30.277 に答える