整数除算命令を持たない8ビットマイクロコントローラーのような小さな組み込みデバイスでは、モジュラス演算子が非効率的であることをどこかで読んだことがあります。おそらく誰かがこれを確認することができますが、違いは整数除算演算よりも5〜10倍遅いと思いました。
カウンター変数を保持し、modポイントで手動で0にオーバーフローする以外に、これを行う別の方法はありますか？
const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}
vs：
私が現在それをしている方法：
const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
if(fizzcount >= FIZZ)
{
print("Fizz\n");
fizzcount = 0;
}
}
ああ、ビット単位の演算の喜び。多くの除算ルーチンの副作用はモジュラスです。したがって、実際には除算がモジュラスよりも速い場合がほとんどありません。あなたがこの情報を入手した情報源に興味があります。乗算器を備えたプロセッサには、乗算器を使用した興味深い除算ルーチンがありますが、除算の結果からモジュラスまで、さらに2つのステップ（乗算と減算）で取得できるため、比較可能です。プロセッサに除算ルーチンが組み込まれている場合は、余りも提供されていることがわかります。
それでも、モジュラ演算を最適化する方法を本当に理解したい場合は、研究が必要なモジュラー算術に特化した数論の小さなブランチがあります。たとえば、モジュラー算術は魔方陣を生成するのに非常に便利です。
したがって、その流れの中で、xの例のモジュラスの数学を非常に低レベルで見てみましょう。これは、除算と比較してどれほど単純であるかを示しているはずです。
たぶん、問題について考えるより良い方法は、基数とモジュロ算術の観点からです。たとえば、目標はDOW mod 7を計算することです。ここで、DOWは曜日の16ビット表現です。これは次のように書くことができます：
DOW = DOW_HI*256 + DOW_LO
DOW%7 = (DOW_HI*256 + DOW_LO) % 7
= ((DOW_HI*256)%7 + (DOW_LO % 7)) %7
= ((DOW_HI%7 * 256%7) + (DOW_LO%7)) %7
= ((DOW_HI%7 * 4) + (DOW_LO%7)) %7
このように表現すると、上位バイトと下位バイトのモジュロ7の結果を個別に計算できます。高値の結果に4を掛けて低値に加算し、最後に7を法として結果を計算します。
8ビット数のmod7の結果の計算も、同様の方法で実行できます。次のように、8ビットの数値を8進数で書き込むことができます。
X = a*64 + b*8 + c
ここで、a、b、およびcは3ビットの数値です。
X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
= (a%7 + b%7 + c%7) % 7
= (a + b + c) % 7
以来64%7 = 8%7 = 1
もちろん、a、b、cは
c = X & 7
b = (X>>3) & 7
a = (X>>6) & 7 // (actually, a is only 2-bits).
の可能な最大値はa+b+cです7+7+3 = 17。したがって、もう1つの8進ステップが必要になります。完全な（テストされていない）Cバージョンは次のように書くことができます：
unsigned char Mod7Byte(unsigned char X)
{
X = (X&7) + ((X>>3)&7) + (X>>6);
X = (X&7) + (X>>3);
return X==7 ? 0 : X;
}
PICバージョンを書くのに少し時間を費やしました。実際の実装は、上記とは少し異なります
Mod7Byte:
movwf temp1 ;
andlw 7 ;W=c
movwf temp2 ;temp2=c
rlncf temp1,F ;
swapf temp1,W ;W= a*8+b
andlw 0x1F
addwf temp2,W ;W= a*8+b+c
movwf temp2 ;temp2 is now a 6-bit number
andlw 0x38 ;get the high 3 bits == a'
xorwf temp2,F ;temp2 now has the 3 low bits == b'
rlncf WREG,F ;shift the high bits right 4
swapf WREG,F ;
addwf temp2,W ;W = a' + b'
; at this point, W is between 0 and 10
addlw -7
bc Mod7Byte_L2
Mod7Byte_L1:
addlw 7
Mod7Byte_L2:
return
これがアルゴリズムをテストするためのliitleルーチンです
clrf x
clrf count
TestLoop:
movf x,W
RCALL Mod7Byte
cpfseq count
bra fail
incf count,W
xorlw 7
skpz
xorlw 7
movwf count
incfsz x,F
bra TestLoop
passed:
最後に、16ビットの結果（私はテストしていません）について、次のように書くことができます。
uint16 Mod7Word(uint16 X)
{
return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}
スコット
数値 mod 2 の累乗を計算する場合は、ビットごとの and 演算子を使用できます。2 番目の数値から 1 を引くだけです。例えば：
x % 8 == x & 7
x % 256 == x & 255
いくつかの注意事項:
ほとんどの場合、2 の累乗ではないモジュロを使用するとオーバーヘッドが発生します。これはプロセッサに関係なく (AFAIK)、モジュラス演算子を使用するプロセッサでさえ、マスク操作とは対照的に除算が数サイクル遅くなります。
ほとんどの場合、これは考慮に値する最適化ではなく、独自のショートカット操作を計算する価値がないことは確かです (特に、それでも除算または乗算が含まれる場合)。
ただし、経験則の 1 つは、配列サイズなどを 2 の累乗になるように選択することです。
したがって、曜日を計算する場合は、約 100 エントリの循環バッファーを設定する場合でも %7 を使用することもできます... 128 にしない理由はありません。その後、% 128 と書くことができ、ほとんどの (すべての) コンパイラーはこれを & 0x7F にします。
複数の組み込みプラットフォームで本当に高いパフォーマンスが必要な場合を除いて、プロファイルを作成するまで、パフォーマンス上の理由からコーディング方法を変更しないでください。
パフォーマンスを最適化するために扱いにくいように記述されたコードは、デバッグや保守が困難です。テストケースを作成し、ターゲットでプロファイリングします。モジュラスの実際のコストがわかったら、代替ソリューションをコーディングする価値があるかどうかを判断します。
@マシューは正しいです。これを試して：
int main() {
int i;
for(i = 0; i<=1024; i++) {
if (!(i & 0xFF)) printf("& i = %d\n", i);
if (!(i % 0x100)) printf("mod i = %d\n", i);
}
}
x%y == (x-(x/y)*y)
お役に立てれば。
組み込みの世界では、実行する必要のある「モジュラス」演算は、多くの場合、で実行できるビット演算にうまく分解されるものであり&、|場合によっては>>。
組み込みデバイスのプログラム可能なハードウェアにアクセスできますか? カウンターなどでしょうか。もしそうなら、シミュレートされた %. (VHDL で 1 回実行しましたが、まだコードがあるかどうかはわかりません。)
除算は 5 ～ 10 倍高速だとおっしゃいましたね。mod をシミュレートするために除算、乗算、および減算を行うことを検討しましたか? (編集: 元の投稿を誤解していました。分割が mod よりも速いのは奇妙だと思いました。それらは同じ操作です。)
ただし、特定のケースでは、mod 6.6 = 2*3 をチェックしています。したがって、最初に最下位ビットが 0 であるかどうかを確認すると、小さな利益が得られる可能性があります。次のようなものです。
if((!(x & 1)) && (x % 3))
{
print("Fizz\n");
}
ただし、それを行う場合は、利益が得られることを確認することをお勧めします。そして、いくつかのコメントをしています。そうでなければコードを見なければならない次の人にとっては気分が悪いでしょう。
必要な組み込みデバイスを実際に確認する必要があります。私が見たすべてのアセンブリ言語 (x86、68000) は、除算を使用してモジュラスを実装しています。
実際には、除算アセンブリ演算は除算の結果と残りを 2 つの異なるレジスタに返します。
@Jeff V: 問題が発生しました! (元のコードは mod 6 を探していましたが、現在は基本的に mod 8 を探しています)。あなたは余分な+1を続けています！コンパイラがそれを最適化してくれることを願っていますが、テストを 2 から開始して MAXCOUNT まで行ってみませんか? 最後に、(x+1) が 8 で割り切れないたびに true を返しています。それでよろしいですか? （あると思いますが、確認したいだけです。）
これが必ずしもより良いというわけではありませんが、常に最大になる内側のループとFIZZ、それを特定の回数繰り返す外側のループを持つことができます。MAXCOUNTがで割り切れない場合は、おそらく最後の数ステップを特別なケースにする必要がありますFIZZ。
そうは言っても、対象のプラットフォームで調査とパフォーマンスのプロファイリングを行って、現在のパフォーマンスの制約を明確に把握することをお勧めします。最適化の労力を費やすより生産的な場所があるかもしれません。
print ステートメントは、モジュラス演算子の最も遅い実装よりも桁違いに長くかかります。したがって、基本的に「一部のシステムで遅い」というコメントは、「すべてのシステムで遅い」となるはずです。
また、提供されている 2 つのコード スニペットは同じことを行いません。2番目のものでは、行
if(フィズカウント >= フィズ)
は常に false であるため、"FIZZ\n" は出力されません。