c++ - 循環バッファの残りのスペースを計算するための単純化されたアルゴリズム?

Question

これよりも循環バッファーの残りのスペースを計算する簡単な (単一の) 方法があるかどうか疑問に思っていましたか?

int remaining = (end > start)
                ? end-start
                : bufferSize - start + end;

Answer 1

予測が不十分な条件が CPU のパイプラインを遅くすることが心配な場合は、これを使用できます。

int remaining = (end - start) + (-((int) (end <= start)) & bufferSize);

しかし、それは時期尚早の最適化である可能性があります (これをホットスポットとして実際に識別していない限り)。はるかに読みやすい現在の手法に固執してください。

Answer 2

うーん....

int remaining = (end - start + bufferSize) % bufferSize;

13 トークン、勝ちますか?

Answer 3

循環バッファーのサイズが 2 のべき乗である場合、循環バッファーのストレージへのインデックスではなく、仮想ストリーム内の位置を保持して表すことで、さらに効果を発揮できstartますend。startとendが署名されていないと仮定すると、上記は次のようになります。

int remaining= bufferSize - (end - start);

実際にバッファから要素を取得するのはもう少し複雑ですが、オーバーヘッドは通常、2 の累乗サイズの循環バッファ ( でマスキングするだけbufferSize - 1) で十分に小さく、循環バッファの他のすべてのロジックをよりシンプルでクリーンにします。さらに、もう心配する必要がないので、すべての要素を使用できますend==start。

Answer 4

C++ 標準、セクション 5.6、パラグラフ 4 によると:

二項 / 演算子は商を生成し、二項 % 演算子は最初の式を 2 番目の式で割った剰余を生成します。/ または % の 2 番目のオペランドがゼロの場合、動作は未定義です。それ以外の場合、(a/b)*b + a%b は a に等しくなります。両方のオペランドが負でない場合、残りは負ではありません。そうでない場合、剰余の符号は実装定義です。

脚注は、商をゼロに向けて丸めることが推奨されることを示唆しています。これにより、残りが負になります。

したがって、(end - start) % bufferSizeアプローチは確実に機能しません。C++ にはモジュラー演算がありません (符号なし整数型によって提供される意味を除く)。

j_random_hacker が推奨するアプローチは異なり、良さそうに見えますが、単純さや速度が実際に改善されているかどうかはわかりません。boolean から int への変換は巧妙ですが、精神的な解析が必要であり、コンパイラとマシンによっては、?: を使用するよりも手間がかかる可能性があります。

あなたはそこに最もシンプルで最高のバージョンを持っていると思います。私はそれを変更しません.

Answer 5

条件を失う：

int remaining = (end + bufferSize - start - 1) % bufferSize + 1

編集:-1と+1は の場合end == startです。その場合、このメソッドはバッファが空であると想定します。バッファーの特定の実装によっては、オフ バイ 1 の状況を回避するためにこれらを調整する必要がある場合があります。