ブランチレスオーバーフローの処理

Question

ブランチなしで自動的にオーバーフローを処理するセーフバッファのタイプを作成しようとしています。バッファサイズは2の累乗であり、有効な正の（すなわち、ゼロを含まない）インデックスのみを有するものとする。また、インデックスに格納された要素が検索キーと等しい場合は、指定されたインデックスでの削除である、チェックされた削除も可能です。

私は基本的にこの

Element *buffer[256]; 

inline void buffer_insert(size_t index, Element *elem){ 
    buffer[index < 256 && index] = elem; 
} 

//Optional: checked insert to prevent overwrite. Will only insert 
//if the buffer holds NULL at index. 
inline void buffer_checkedInsert(size_t index, Element * elem){ 
    buffer[index && !buffer[index < 256 && index]] = elem; 
} 

inline void buffer_checkedRemove(size_t index, Element *elem){ 
    buffer[0] = NULL; //Maybe useful if buffer[0] stores elem 
    buffer[((elem == buffer[index < 256 && index)) && index] = NULL; 
} 

buffer[0]が有効なバッファ・インデックスではありませんように、私は基本的に、渡されたインデックスが範囲外であるときはいつでも、インデックス0にアクセスするような何かのために行っていました。また、削除される要素が削除に渡される要素と等しくないときはいつでもインデックス0にアクセスする必要があります。また、バッファにインデックスに何かが含まれている場合は、インデックス0にアクセスすることもできます。

私の質問は以下のとおりです。

• は、私は本当に無店舗を持っているものですか？ Cコンパイラが& &の短絡を使用することを決定した場合、コードが分岐する可能性があるためです。
• & &が分岐を引き起こす場合、分岐を伴わない同じ振る舞いを持つ代替案がありますか？
• これは基本的なオーバーフローチェックよりも高速ですか？あるいは、Cコンパイラがどうにかしてif(index < 256) buffer[index] = elemのブランチレス版を与えることができましたか？

Answer 1

私は本当にブランチレスですか？ Cコンパイラが& &の短絡を使用することを決定した場合、コードが分岐する可能性があるためです。

多分。コンパイラは、これらの場合にブランチレスマシンコードを発行するのに十分なほど賢明かもしれませんが、それに頼ることはできません。

& &原因が分岐する場合、分岐を必要としないこの場合は同じ動作を持っている代替手段はありますか？

あなたの質問はちょっと混乱しています。コンパイラが&&オペレーションを実装するために分岐コードを発行するという事実は、そのオペレーションの定義された動作に従います。同じ振る舞いを持つ任意の代替案は、同じ分岐の可能性を与えなければならない。

一方、が同じ結果を計算する代替方法があるかどうかを尋ねる場合は、すべての場合で、そうであればそれらの式を書き換えて分岐できなくすることができます。たとえば、あなたは&かそこらのような*演算子のいずれかを使用できます。

buffer[(index < 256) & (index != 0)] = elem; 

をそれとも、あなたが実際に必要な動作を実装できます。

buffer[(index < 256) * index] = elem; 

をコンパイラがあろうと考える理由はありませんこれらの計算のいずれかの分岐命令を発行する。そうであれば、それはターゲットアーキテクチャ上でパフォーマンスが向上すると考えているからでしょう。

これは基本的なオーバーフローチェックよりも高速ですか？あるいは、Cコンパイラがif（index < 256）buffer [index] = elemのブランチレス版を何とか与えることができましたか？

ブランチレスバージョンは確かにです。は高速です。それらは、（非）ブランチが多く実行されるワークロードでは、観測可能なほど高速であり、容易に識別できるパターンはありません。しかし、（非）分岐がほとんど規則的なパターンに従うならば、特にほとんど常に一方向に進むならば、CPUの分岐予測ユニットは少なくともブランチレス割り当てと同じくらい速い通常の有効性チェックを行うことができます。

最終的に、実際のデータやそのファクシミリでコードの実際のパフォーマンスをベンチマークすることなく、心配する必要はありません。結果はデー​​タに依存する可能性が高く、重要な点は、プログラムの実行時間が求めている機能に費やされた時間に依存します。これまでにない優れたベンチマークがない限り、明快さと保守性をコードする必要があります。