11

モジュロ演算子「%」と除算演算子「/」は組み込み C++ では非常に効率が悪いと言われています。

次の式を別の方法で実現するにはどうすればよいですか。

a = b % c;

これは、次のロジックを使用して達成できることを理解しています。

a = b - c;
while (a >= c) {
  a = a - c;
}

しかし、私の質問は、 % 演算子と比較して、 while ループを含むこのコードは十分に効率的ですか?

ありがとう、キルティ

4

6 に答える 6

18

除算とモジュラスは、何をするにしてもコストのかかるハードウェア演算であり (これは、言語やコンパイラよりもハードウェア アーキテクチャに関連しています)、おそらく足し算よりも 10 倍遅くなります。

ただし、現在のラップトップやサーバー、およびハイエンドのマイクロコントローラーでは、キャッシュミスは分割よりもはるかに遅いことがよくあります。

除数が定数の場合、GCC コンパイラは多くの場合、それらを最適化できます。

単純なループは、通常、ハードウェア除算命令 (または、ハードウェアによって提供されていない場合は、それを実行するライブラリ ルーチン) を使用するよりもはるかに遅くなります。分割を避けてループに置き換えるのは間違っていると思います。

たとえば、2 のべき乗を使用してアルゴリズムを調整することもできますが、コードを使用することはお勧めしません。時期尚早の最適化は悪であることを忘れないでください。最初にプログラムを正しく作成してから、プロファイルを作成して問題のある箇所を見つけてください。

于 2011-11-15T06:16:08.240 に答える
7

%オペレーターほど効率的なものはありません。それを行うためのより良い方法があれば、合理的なコンパイラは自動的に変換します。%それが非効率的であると言われたら/、それは単にそれらが難しい操作だからです - モジュロを実行する必要がある場合は、それを実行してください。

より良い方法がある特殊なケースがあるかもしれません - 例えば mod a power of two はバイナリとして書くことができます - しかし、それらはおそらくあなたのコンパイラによって最適化されています。

于 2011-11-15T06:15:44.680 に答える
6

そのコードはほぼ確実に遅くなりますが、プロセッサ/コンパイラは除算/変更を実行することを決定します。一般に、基本的な算術演算子のショートカットを実現するのは非常に困難です。これは、mcu/cpu 設計者とコンパイラ プログラマーがほとんどすべてのアプリケーションでこれを最適化するのが得意だからです。

組み込みデバイス (すべてのサイクル/バイトが違いを生む可能性がある) での一般的なショートカットの 1 つは、ビット シフト演算子を使用して乗算と除算を実行し、ビットごとの and (&) を使用してモジュロを実行するために、すべてを基数 2 で保持することです。

例:

unsigned int x = 100;
unsigned int y1 = x << 4;   // same as x * 2^4 = x*16
unsigned int y2 = x >> 6;   // same as x / 2^6 = x/64
unsigned int y3 = x & 0x07; // same as x % 8
于 2011-11-15T06:18:41.113 に答える
1

コンパイル時に除数がわかっている場合、その演算は、いくつかのシフト、加算、およびその他の高速演算を使用して、逆数による乗算に変換できます。これは、ハードウェアに除算を実装している場合でも、最新のプロセッサではより高速になります。埋め込みターゲットには通常、除算/モジュロ用に高度に最適化されたルーチンがあります。これは、これらの操作が標準で必要とされるためです。

于 2011-11-15T06:24:44.710 に答える
1

コードを慎重にプロファイリングし、モジュロ演算子が内部ループの主要なコストであることがわかった場合は、役立つ最適化があります。算術左シフト (32 ビット値の場合) を使用して整数の符号を決定するためのトリックに既に精通している場合があります。

sign = ( x >> 31 ) | 1;

これにより、ワード全体に符号ビットが拡張されるため、負の値は -1 になり、正の値は 0 になります。次に、正の値が 1 になるようにビット 0 が設定されます。

モジュロよりも少ない量だけ値をインクリメントするだけの場合、この同じトリックを使用して結果をラップできます。

val += inc;
val -= modulo & ( static_cast< int32_t >( ( ( modulo - 1 ) - val ) ) >> 31 );

あるいは、モジュロ未満の値でデクリメントする場合、関連するコードは次のとおりです。

int32_t signedVal = static_cast< int32_t >( val - dec );
val = signedVal + ( modulo & ( signedVal >> 31 ) );

uint32_t を渡していたので static_cast 演算子を追加しましたが、必要ではないかもしれません。

単純な % 演算子とは対照的に、これは非常に役立ちますか? これは、コンパイラと CPU アーキテクチャによって異なります。VS2012 でコンパイルすると、単純なループが i3 プロセッサで 60% 高速に実行されることがわかりましたが、Raspberry Pi の ARM11 チップと GCC でコンパイルすると、20% の改善しか得られませんでした。

于 2013-05-08T09:37:52.500 に答える
0

定数による除算は、2の累乗または他のシフトの組み合わせを追加する場合のシフトによって実現できます。

http：// masm32.com/board/index.php?topic=9937.0には、x86アセンブリバージョンとCソースが最初の投稿からダウンロードされています。このコードが生成されます。

于 2011-11-15T06:42:15.513 に答える