c++ - なぜモジュロ演算子が必要なのですか?

Question

mod 操作を論理に置き換えることができるというドキュメントを読みましたが、次のようになります。

その代わり：

int Limit = Value % Range;

あなたがやる：

int Limit = Value & (Range-1);

しかし、コンパイラは依然として mod 命令を生成します。私の質問は基本的に次のとおりです。

Answer 1

いいえ...Rangeが 2 の累乗の場合にのみ機能します。

%他のすべての値については、モジュラス演算子が必要です。

負の数を扱う場合、いくつかの微妙な (おそらく実装定義の) 違いもあります。

---

補足として、%演算子を使用すると、おそらく読みやすくなります。

Answer 2

モジュロを2の累乗である場合にのみ、モジュロに置き換えることができます。基本数学を使用して、モジュロなしでモジュロを置き換えることができます。

a = b % c;

で行うことができます

x = b % c;
a = b / (x*c);

例でこれを確認しましょう

25 % 7 = 
25 / 7 = 3 (integer math)
25 - (3 * 7) =
25 - 21 = 4

モジュロ演算子がないので、とにかく電卓でそれを行う必要があります。

ご了承ください

25 & (7-6) = 
0x19 & 0x6 = 0x0

したがって、置換は機能しません。

ほとんどのプロセッサにはモジュロがないだけでなく、多くのプロセッサには除算がありません。ハッカーの喜びの本をチェックしてください。

なぜモジュロが必要なのですか？ハードウェアを燃やして除算した場合は、モジュロを追加するためにさらに1マイル進んでもかまいません。ほとんどのプロセッサは、質問を次のレベルに引き上げます。ソフトウェアで実行できるのに、なぜハードウェアで分割を実装するのでしょうか。あなたの質問に対する答えは、ほとんどのプロセッサフ​​ァミリにはモジュロがなく、ソフトウェアソリューションと比較してチップの面積や消費電力などの価値がないため、多くのプロセッサフ​​ァミリには除算がありません。ソフトウェアソリューションは、それほど苦痛/費用がかからない/危険です。

さて、あなたの質問は、優勝したポスターが答えたものではないと思います。Rangeが2の累乗であり、IDが機能する場合...最初に、コンパイル時に範囲が不明な場合は、減算とand、2つの演算、およびおそらく中間変数を実行する必要があります。モジュロよりもはるかにコストがかかるため、コンパイラは、モジュロの代わりに減算と最適化を行うのにエラーが発生します。範囲が2の累乗であり、コンパイル時にわかっている場合は、より優れた/より優れたコンパイラーが最適化されます。特に、可変ワード長の命令セットを使用すると、小さい命令を大きい命令よりも使用できる場合があります。範囲をロードしてモジュロを実行する方が、ゼロ以外のビット（ IDに一致する範囲では、値に1つのビットが設定され、他のビットはゼロになります。0x100、0x40、0x8000など）、モジュロを実行します。ロードイミディエートプラスモジュロは、ロードイミディエートプラスおよびよりも安価である可能性があります。または、モジュロイミディエートは、およびイミディエートよりも安価である可能性があります。命令セットと、コンパイラがソリューションをどのように実装したかを調べる必要があります。

最適化を行っていない例をいくつか投稿することをお勧めします。コンパイラが期待していた最適化を行った例をたくさん投稿できると思います。

Answer 3

他の人が述べているように、範囲は 2^n-1 でなければならず、それでも実行時に行うと問題が発生します。

最近のアーキテクチャ (たとえば、P4 時代以降のもの) では、整数除算命令のレイテンシは最悪の場合で 26 ～ 50 サイクル程度です。比較すると、乗算は 1 ～ 3 サイクルで実行でき、多くの場合、並列処理の方がはるかに優れています。

DIV 命令は商を EAX で返し、剰余を EDX で返します。「剰余」は自由です（モジュラスは剰余です）。

実行時に範囲が可変である何かを実装する場合、& を使用したい場合は、次のことを行う必要があります。

a) 範囲が 2^n-1 であるかどうかを確認します。そうであれば & codepath: を使用します。これはブランチであり、キャッシュ ミスの可能性などです。大きなレイテンシの可能性を追加します b) 2^n-1 でない場合は、a を使用しますDIV命令

式に分岐を追加する代わりに DIV を使用すると (キャッシュのエビクションが不十分な場合、数百または数千サイクルのコストがかかる可能性があります)、DIV が明らかに最良の選択になります。さらに、符号付きデータ型で & を使用している場合は、変換が必要になります (混合データ型には & はありませんが、DIV には & があります)。さらに、DIV がモジュラスから分岐するためだけに使用され、残りの結果が使用されない場合、投機的実行は適切に実行できます。また、命令を並行して実行できる複数のパイプラインによって、パフォーマンスの低下がさらに軽減されます。

実際のコードを使用している場合、多くのキャッシュが作業中のデータと、すぐに作業するか、作業したばかりの他のコードとデータでいっぱいになることを覚えておく必要があります。ブランチの予測ミスが原因で、キャッシュ ページを削除して、それらがページインするのを待つ必要はありません。ほとんどの場合、モジュロでは、i = 7 になるだけではありません。d = i % 4; 直前に (予測されキャッシュされた) サブルーチン呼び出しであるサブルーチンを頻繁に呼び出す大きなコードを使用しています。さらに、おそらくそれ自体が分岐予測も使用しているループで実行しています。ループを使用したネストされた分岐予測は、最新のマイクロプロセッサではかなりうまく処理されますが、実行しようとしている予測に追加するのは単純に愚かです。

要約すると、DIV を使用することは、一般的な使用例では最新のプロセッサでより理にかなっています。キャッシュの考慮事項やその他の理由により、コンパイラが 2^n-1 を生成するのは実際には「最適化」ではありません。その整数除算を本当に微調整する必要があり、プログラム全体がそれに依存している場合は、除数を 2^n-1 にハードコーディングし、ビットごとの & ロジックを自分で作成することになります。

最後に、これはちょっとした言い訳です。整数除算用の専用 ALU ユニットは、レイテンシを実際に約 6 ～ 8 サイクルに減らすことができます。データ パスが最終的に約 128 ビット幅になり、整数 DIV が正常に機能している場合、そのための不動産を誰も持っていません。