5

我知道add比mul函数更快。

我想知道如何在下面的代码中使用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)
4

5 回答 5

12

add比mul快，但是如果你想将两个通用值相乘，mul比任何循环迭代add操作要快得多。

您不能认真地使用add来使该代码比使用mul更快。如果您需要乘以一些小的常数值（例如 2），那么也许您可以使用add来加快速度。但对于一般情况 - 不。

于 2010-09-14T05:19:20.570 回答
9

如果您将两个事先不知道的值相乘，则实际上不可能击败 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

这样做的关键问题是，它至少需要 4 个时钟来执行此操作，假设超标量 CPU 受寄存器依赖性约束。在现代 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 for k=1,2,3（参见 Intel 参考手册），其中 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 编译器在索引最讨厌的嵌套结构数组时几乎从不使用实际的乘法。

于 2010-09-14T08:01:16.690 回答
4

除非您的乘法相当简单，否则add最有可能不会超过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

它们很好地适用于二的幂。我不是说他们更快。在花哨的乘法指令出现之前，它们当然是必要的。那是来自一个灵魂在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乘法运算，这里有一个例程，它将采用两个无符号值 inax并bx返回乘积 in ax。它不会优雅地处理溢出。

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乘以等于456：

    123 x 6
+  1230 x 5
+ 12300 x 4

这与您在小学/小学学习乘法的方式相同。使用二进制更容易，因为你只乘以零或一（换句话说，加或不加）。

这是相当老式的 x86（8086，来自 DEBUG 会话 - 我不敢相信他们实际上仍然在 XP 中包含那个东西），因为那是我最后一次直接在汇编程序中编码。对于高级语言有话要说:-)

于 2010-09-14T06:01:48.080 回答
3

对于汇编指令，执行任何指令的速度都是使用时钟周期来衡量的。Mul 指令总是需要更多的时钟周期然后加法操作，但是如果您在循环中执行相同的加法指令，那么使用加法指令进行乘法的整个时钟周期将比单个 mul 指令多得多。您可以查看以下 URL，其中讨论了单个 add/mul 指令的时钟周期。这样您就可以进行数学运算，哪个会更快。

http://home.comcast.net/~fbui/intel_a.html#add

http://home.comcast.net/~fbui/intel_m.html#mul

我的建议是使用 mul 指令而不是将 add 放入循环中，后者是非常低效的解决方案。

于 2010-09-14T05:27:50.923 回答
0

我不得不回应你已经做出的回应——对于一般乘法，你最好使用 MUL——毕竟这就是它的用途！

在某些特定情况下，您知道每次都希望乘以特定的固定值（例如，在计算位图中的像素索引时），那么您可以考虑将乘法分解为（小）少数SHL 和 ADD - 例如：

1280 x 1024 显示屏 - 显示屏上的每一行都是 1280 像素。

1280 = 1024 + 256 = 2^10 + 2^8

y * 1280 = y * (2 ^ 10) + y * (2 ^ 8) = ADD (SHL y, 10), (SHL y, 8)

...鉴于图形处理可能需要快速，这种方法可以为您节省宝贵的时钟周期。

于 2010-09-14T05:58:54.480 回答