add vs mul(IA32-Assembly)

Question

我知道与mul函数相比,add更快.

我想知道如何在下面的代码中使用add而不是mul来提高效率.

示例代码:

            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)

Answer 1

add比mul快,但是如果你想要乘以两个通用值,mul比任何循环迭代添加操作要快得多.

您不能认真使用add来使代码变得比使用mul更快.如果你需要乘以一些小的常数值(比如2),那么也许你可以使用add来加快速度.但对于一般情况 - 没有.

Answer 2

如果要将两个您事先不知道的值相乘,则实际上不可能超过x86汇编程序中的乘法指令.

如果您事先知道其中一个操作数的值,则可以通过使用少量添加来击败乘法指令.当已知操作数很小并且在其二进制表示中仅具有几个位时,这尤其有效.要将未知值x乘以包含2 ^ p + 2 ^ q + ... 2 ^ r的已知值,您只需添加x*2 ^ p + x*2 ^ q + .. x*2*r如果位p,q ,...和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(加载有效地址)指令来实现快速乘以小常数.LEA只占用一个时钟最坏的情况,其执行时间通常可以通过超标量CPU与其他指令重叠.

LEA本质上是"用小常数乘法器加两个值".它计算t = 2 ^ k*x + y为k = 1,2,3(参见英特尔参考手册),t,x和y为任何寄存器.如果x == y,则可以获得1,2,3,4,5,8,9倍x,但使用x和y作为单独的寄存器允许将中间结果组合 并移动到其他寄存器(例如,到t) ),结果非常方便.使用它,您可以使用单个指令完成乘以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 [i]的数组的偏移量,其中A中结构元素的大小是已知常量.一个聪明的人可能会缓存答案,因此每次乘以相同的常数时都不必重新计算; 我实际上并没有这样做,因为生成此类序列的时间少于您的预期.

有趣的是打印出所有常数乘以1到10000所需的指令序列.大多数指令可以在最坏情况下的5-6指令中完成.因此,PARLANSE编译器甚至在索引甚至最糟糕的嵌套结构数组时也几乎不使用实际的乘法.