addはmul関数と比較して高速であることを知っています。
より効率的にするために、次のコードでmulの代わりにaddを使用する方法を知りたいです。
サンプルコード:
mov eax, [ebp + 8] #eax = x1
mov ecx, [ebp + 12] #ecx = x2
mov edx, [ebp + 16] #edx = y1
mov ebx, [ebp + 20] #ebx = y2
sub eax,ecx #eax = x1-x2
sub edx,ebx #edx = y1-y2
mul edx #eax = (x1-x2)*(y1-y2)
addはmulよりも高速ですが、2 つの一般的な値を乗算する場合、mulは加算操作を繰り返すループよりもはるかに高速です。
addを真剣に使用して、そのコードをmulよりも高速にすることはできません。小さな定数値 (2 など) を掛ける必要がある場合は、addを使用して速度を上げることができます。しかし、一般的なケースでは - いいえ。
事前にわからない2つの値を乗算する場合、x86アセンブラの乗算命令を打ち負かすことは事実上不可能です。
いずれかのオペランドの値が事前にわかっている場合は、少数の加算を使用することで乗算命令を打ち負かすことができる場合があります。これは、既知のオペランドが小さく、バイナリ表現に数ビットしかない場合に特に効果的です。未知の値xに2^p + 2 ^ q + ... 2 ^ rで構成される既知の値を掛けるには、ビットp、qの場合にx * 2 ^ p + x * 2 ^ q + .. x * 2*rを追加するだけです。 、...およびrが設定されます。これは、アセンブラで左シフトして追加することで簡単に実行できます。
; x in EDX
; product to EAX
xor eax,eax
shl edx,r ; x*2^r
add eax,edx
shl edx,q-r ; x*2^q
add eax,edx
shl edx,p-q ; x*2^p
add eax,edx
これに関する重要な問題は、レジスタの依存関係によって制約されたスーパースカラーCPUを想定すると、これを行うのに少なくとも4クロックかかることです。最近のCPUでは、乗算にかかるクロックは通常10以下であり、このシーケンスが時間より長くなる場合は、乗算を実行することをお勧めします。
9を掛けるには：
mov eax,edx ; same effect as xor eax,eax/shl edx 1/add eax,edx
shl edx,3 ; x*2^3
add eax,edx
これは乗算を打ち負かします。2クロックしかかかりません。
あまり知られていないのは、LEA（実効アドレスのロード）命令を使用して、高速の小さな定数を乗算することです。最悪の場合、実行時間が1クロックしかかからないLEAは、スーパースカラーCPUによる他の命令とオーバーラップすることがよくあります。
LEAは、本質的に「小さな定数乗数で2つの値を加算する」ことです。t、x、yが任意のレジスタである場合、k = 1,2,3（Intelリファレンスマニュアルを参照）に対してt = 2 ^ k * x+yを計算します。x == yの場合、xの1,2,3,4,5,8,9倍を取得できますが、xとyを個別のレジスタとして使用すると、中間結果を結合 して他のレジスタ（たとえば、t）に移動できます。 ）、これは非常に便利であることがわかります。これを使用すると、1つの命令を使用して9を掛けることができます。
lea eax,[edx*8+edx] ; takes 1 clock
LEAを注意深く使用すると、少数のサイクルでさまざまな固有の定数を乗算できます。
lea eax,[edx*4+edx] ; 5 * edx
lea eax,[eax*2+edx] ; 11 * edx
lea eax,[eax*4] ; 44 * edx
これを行うには、定数乗数を1、2、3、4、5、8、および9を含むさまざまな係数/合計に分解する必要があります。これを実行できる小さな定数の数は注目に値しますが、それでも3つしか使用しません。 4つの指示。
他の通常のシングルクロック命令（SHL / SUB / NEG / MOVなど）の使用を許可すると、純粋なLEAだけでは効率的に実行できない定数値を乗算できます。31を掛けるには：
lea eax,[4*edx]
lea eax,[8*eax] ; 32*edx
sub eax,edx; 31*edx ; 3 clocks
対応するLEAシーケンスは長くなります。
lea eax,[edx*4+edx]
lea eax,[edx*2+eax] ; eax*7
lea eax,[eax*2+edx] ; eax*15
lea eax,[eax*2+edx] ; eax*31 ; 4 clocks
これらのシーケンスを理解するのは少し難しいですが、組織的な攻撃を設定することができます。
LEA、SHL、SUB、NEG、MOVはすべてシングルクロック命令のワーストケースであり、他の命令に依存しない場合はゼロクロックであるため、このようなシーケンスの実行コストを計算できます。これは、動的プログラミングアルゴリズムを実装して、そのような命令の可能な限り最良のシーケンスを生成できることを意味します。これは、クロックカウントが特定のCPUの整数乗算よりも小さく（経験則として5クロックを使用）、すべてのレジスタを使い果たしていないか、少なくともレジスタを使い果たしていない場合にのみ役立ちます。すでに忙しい（流出を避ける）。
私は実際にこれをPARLANSEコンパイラに組み込みました。これは、Aの構造要素のサイズが既知の定数である構造A[i]の配列へのオフセットを計算するのに非常に効果的です。賢い人は答えをキャッシュする可能性があるので、同じ定数を乗算するたびに再計算する必要はありません。そのようなシーケンスを生成する時間はあなたが期待するよりも短いので、私は実際にはそれをしませんでした。
1から10000までのすべての定数を乗算するために必要な命令のシーケンスを出力することは、やや興味深いことです。それらのほとんどは、最悪の場合5〜6命令で実行できます。結果として、PARLANSEコンパイラは、ネストされた構造体の最も厄介な配列でさえインデックスを作成するときに、実際の乗算を使用することはほとんどありません。
乗算がかなり単純化されていない限り、addほとんどの場合、 は a よりも優れていませんmul。そうは言っても、乗算を行うために使用できます。add
Multiply by 2:
add eax,eax ; x2
Multiply by 4:
add eax,eax ; x2
add eax,eax ; x4
Multiply by 8:
add eax,eax ; x2
add eax,eax ; x4
add eax,eax ; x8
それらは 2 の累乗でうまく機能します。彼らが速いと言っているのではありません。これらは、派手な乗算命令が登場する前の時代には確かに必要でした。それは、Mostek 6502、Zilog z80、RCA1802 という地獄の炎の中で魂が鍛えられた誰かからのものです :-)
中間結果を保存するだけで、累乗以外で乗算することもできます。
Multiply by 9:
push ebx ; preserve
push eax ; save for later
add eax,eax ; x2
add eax,eax ; x4
add eax,eax ; x8
pop ebx ; get original eax into ebx
add eax,ebx ; x9
pop ebx ; recover original ebx
私は通常、主に読みやすさのためにコードを記述し、必要な場合にのみパフォーマンスを気にすることをお勧めします。ただし、アセンブラーで作業している場合は、その時点ですでに十分な可能性があります。しかし、任意の被乗数があるため、私の「解決策」が実際にあなたの状況に当てはまるかどうかはわかりません。
ただし、実行していることが実際に高速であることを確認するために、常にターゲット環境でコードをプロファイリングする必要があります。アセンブラーは、最適化のその側面をまったく変更しません。
乗算を行うために使用する、より汎用的なアセンブラを実際に見たい場合は、とaddで 2 つの符号なし値を取り、 で積を返すルーチンを次に示します。オーバーフローをエレガントに処理しません。axbxax
START: MOV AX, 0007 ; Load up registers
MOV BX, 0005
CALL MULT ; Call multiply function.
HLT ; Stop.
MULT: PUSH BX ; Preserve BX, CX, DX.
PUSH CX
PUSH DX
XOR CX,CX ; CX is the accumulator.
CMP BX, 0 ; If multiplying by zero, just stop.
JZ FIN
MORE: PUSH BX ; Xfer BX to DX for bit check.
POP DX
AND DX, 0001 ; Is lowest bit 1?
JZ NOADD ; No, do not add.
ADD CX,AX
NOADD: SHL AX,1 ; Shift AX left (double).
SHR BX,1 ; Shift BX right (integer halve, next bit).
JNZ MORE ; Keep going until no more bits in BX.
FIN: PUSH CX ; Xfer product from CX to AX.
POP AX
POP DX ; Restore registers and return.
POP CX
POP BX
RET
123これは、 multiplied by456が次と同じであるという事実に依存しています。
123 x 6
+ 1230 x 5
+ 12300 x 4
これは、小学校で掛け算を教えられたのと同じ方法です。ゼロまたは 1 で乗算するだけなので (つまり、足すか足さないか)、2 進数の方が簡単です。
アセンブラーで直接コーディングしたのはこれが最後だったので、かなり古い学校のx86（DEBUGセッションからの8086-実際にXPにまだ含まれているとは信じられません）です。高水準言語については、言いたいことがあります:-)
アセンブリ命令に関しては、命令の実行速度はクロックサイクルを使用して測定されます。Mul 命令は常に加算演算よりも多くのクロックサイクルを必要としますが、ループ内で同じ add 命令を実行すると、add 命令を使用して乗算を行うための全体的なクロックサイクルは、単一の mul 命令よりもはるかに多くなります。単一の add/mul 命令のクロック サイクルについて説明している次の URL をご覧ください。
http://home.comcast.net/~fbui/intel_a.html#add
http://home.comcast.net/~fbui/intel_m.html#mul
add をループに入れるのではなく、mul 命令を使用することをお勧めします。後者は非常に非効率的なソリューションです。
私はあなたがすでに持っている応答を反映する必要があります-一般的な乗算では、MUL を使用するのが最善です-結局のところ、それはそこにあるものです!
毎回特定の固定値を乗算する必要があることがわかっている特定のケースでは (たとえば、ビットマップ内のピクセル インデックスを計算する場合) 、乗算を (小さい) 一握りに分割することを検討できます。 SHL と ADD の - 例:
1280 x 1024 ディスプレイ - ディスプレイの各行は 1280 ピクセルです。
1280 = 1024 + 256 = 2^10 + 2^8
y * 1280 = y * (2 ^ 10) + y * (2 ^ 8) = 追加 (SHL y, 10), (SHL y, 8)
...グラフィックス処理が高速である必要がある可能性が高いことを考えると、このようなアプローチは貴重なクロック サイクルを節約する可能性があります。