delphi – 某些CPU在紧循环中的ADC / SBB和INC / DEC存在问题

我在Delphi中编写一个简单的BigInteger类型.它主要由TLimb的动态数组组成,TLimb是一个32位无符号整数,32位大小的字段也保存BigInteger的符号位.

要添加两个BigInteger,我创建一个适当大小的新BigInteger,然后在一些记账后,调用以下过程,将三个指针传递给左右操作数和结果的数组的各个开始,以及分别为左右肢数.

普通代码：

class procedure BigInteger.PlainAdd(Left,Right,Result: PLimb; LSize,RSize: Integer); 
asm
// EAX = Left,EDX = Right,ECX = Result
        PUSH    ESI
        PUSH    EDI
        PUSH    EBX
        MOV     ESI,EAX                 // Left
        MOV     EDI,EDX                 // Right
        MOV     EBX,ECX                 // Result
        MOV     ECX,RSize               // Number of limbs at Left
        MOV     EDX,LSize               // Number of limbs at Right
        CMP     EDX,ECX
        JAE     @SkipSwap
        XCHG    ECX,EDX                 // Left and LSize should be largest
        XCHG    ESI,EDI                 // so swap
@SkipSwap:
        SUB     EDX,ECX                 // EDX contains rest
        PUSH    EDX                     // ECX contains smaller size
        XOR     EDX,EDX                  
@MainLoop:
        MOV     EAX,[ESI + climbSize*EDX]  // climbSize = SizeOf(TLimb) = 4.
        ADC     EAX,[EDI + climbSize*EDX]
        MOV     [EBX + climbSize*EDX],EAX
        INC     EDX
        DEC     ECX
        JNE     @MainLoop
        POP     EDI                        
        INC     EDI                        // Do not change Carry Flag
        DEC     EDI
        JE      @LastLimb
@RestLoop:
        MOV     EAX,[ESI + climbSize*EDX]
        ADC     EAX,ECX
        MOV     [EBX + climbSize*EDX],EAX
        INC     EDX
        DEC     EDI
        JNE     @RestLoop
@LastLimb:
        ADC     ECX,ECX                    // Add in final carry
        MOV     [EBX + climbSize*EDX],ECX
@Exit:
        POP     EBX
        POP     EDI
        POP     ESI
end;
// RET is inserted by Delphi compiler.

这个代码运行良好,我非常满意,直到我注意到,在我的开发设置(Win7在iMac上的Parallels VM中)是一个简单的PURE PASCAL加载例程,在使用变量模拟进位的同时,几个if子句比我简单直接的手工汇编程序要快.

在某些cpu(包括我的iMac和一台较旧的笔记本电脑)上花了一阵时间,DEC或INC和ADC或SBB的组合可能非常慢.但是在我的其他大部分人(我有五台电脑来测试它们,尽管其中四个完全一样),这是相当快的.

所以我写了一个新版本,仿效INC和DEC,使用LEA和JECXZ,就像这样：

模拟代码的一部分：

@MainLoop:
        MOV     EAX,[ESI + EDX*climbSize]
        LEA     ECX,[ECX - 1]                   // Avoid INC and DEC,see above.
        ADC     EAX,[EDI + EDX*climbSize]
        MOV     [EBX + EDX*climbSize],EAX
        LEA     EDX,[EDX + 1]
        JECXZ   @DoRestLoop                     // LEA does not modify Zero flag,so JECXZ is used.
        JMP     @MainLoop
@DoRestLoop:
// similar code for the rest loop

这使得我的代码在“慢”机器上几乎是快三倍,但是在“更快”的机器上慢了20％.所以现在,作为初始化代码,我做一个简单的定时循环,并使用它来决定是否设置单元调用普通或仿真例程.这几乎总是正确的,但有时它选择(较慢的)普通例程,当它应该选择仿真例程.

但是我不知道这是否是最好的方法.

题

我给了我解决方案,但是在这里做asm的大师也许知道一个更好的方法来避免某些cpu的缓慢？

更新

彼得和尼尔斯的回答帮助我很多东西走上正轨.这是DEC版本的最终解决方案的主要部分：

普通代码：

class procedure BigInteger.PlainAdd(Left,RSize: Integer);
asm
        PUSH    ESI
        PUSH    EDI
        PUSH    EBX
        MOV     ESI,EAX                         // Left
        MOV     EDI,EDX                         // Right
        MOV     EBX,ECX                         // Result
        MOV     ECX,RSize
        MOV     EDX,LSize
        CMP     EDX,EDX
        XCHG    ESI,EDI
@SkipSwap:
        SUB     EDX,ECX
        PUSH    EDX
        XOR     EDX,EDX
        XOR     EAX,EAX
        MOV     EDX,ECX
        AND     EDX,$00000003
        SHR     ECX,2
        CLC
        JE      @MainTail
@MainLoop:
        // Unrolled 4 times. More times will not improve speed anymore.
        MOV     EAX,[ESI]
        ADC     EAX,[EDI]
        MOV     [EBX],EAX
        MOV     EAX,[ESI + climbSize]
        ADC     EAX,[EDI + climbSize]
        MOV     [EBX + climbSize],[ESI + 2*climbSize]
        ADC     EAX,[EDI + 2*climbSize]
        MOV     [EBX + 2*climbSize],[ESI + 3*climbSize]
        ADC     EAX,[EDI + 3*climbSize]
        MOV     [EBX + 3*climbSize],EAX
        // Update pointers.
        LEA     ESI,[ESI + 4*climbSize]
        LEA     EDI,[EDI + 4*climbSize]
        LEA     EBX,[EBX + 4*climbSize]
        // Update counter and loop if required.
        DEC     ECX                             
        JNE     @MainLoop
@MainTail:
        // Add index*climbSize so @MainX branches can fall through.
        LEA     ESI,[ESI + EDX*climbSize]
        LEA     EDI,[EDI + EDX*climbSize]
        LEA     EBX,[EBX + EDX*climbSize]
        // Indexed jump.
        LEA     ECX,[@JumpsMain]
        JMP     [ECX + EDX*TYPE Pointer]
        // Align jump table manually,with nops. Update if necessary.
        nop
// Jump table.
@JumpsMain:
        DD      @DoRestLoop
        DD      @Main1
        DD      @Main2
        DD      @Main3
@Main3:
        MOV     EAX,[ESI - 3*climbSize]
        ADC     EAX,[EDI - 3*climbSize]
        MOV     [EBX - 3*climbSize],EAX
@Main2:
        MOV     EAX,[ESI - 2*climbSize]
        ADC     EAX,[EDI - 2*climbSize]
        MOV     [EBX - 2*climbSize],EAX
@Main1:
        MOV     EAX,[ESI - climbSize]
        ADC     EAX,[EDI - climbSize]
        MOV     [EBX - climbSize],EAX
@DoRestLoop:

// etc...

我删除了很多空格,我猜读者可以得到其余的例程.它与主循环类似.速度提高约较大的BigInteger为20％,小型BigInteger为10％(仅限少数肢体).

64位版本现在在可能的情况下使用64位加法(在主循环中,在Main3和Main2中,它们不像上面那样是“fall-through”),而之前的64位比32位慢了很多,但现在它比32位快30％,是原始简单64位循环的两倍.

; Example 5.21. Partial flags stall when reading unmodified flag bits
cmp eax,ebx
inc ecx
jc xx
; Partial flags stall  (P6 / PIII / PM / Core2 / Nehalem)

; pure loads are always one uop,so we can still index it
        ; with no perf hit on SnB
        add     esi,ecx   ; point to end of src1
        neg     ecx

UNROLL equ 4
@MainLoop:
        MOV     EAX,[ESI + 0*climbSize + ECX*climbSize]
        ADC     EAX,[EDI + 0*climbSize]
        MOV     [EBX + 0*climbSize],EAX

        MOV     EAX,[ESI + 1*climbSize + ECX*climbSize]
        ADC     EAX,[EDI + 1*climbSize]
        MOV     [EBX + 1*climbSize],EAX

        ; ... repeated UNROLL times.  Use an assembler macro to repeat these 3 instructions with increasing offsets

        LEA     ECX,[ECX+UNROLL] ; loop counter

        LEA     EDI,[EDI+climbSize*UNROLL]  ; Unrolling makes it worth doing
        LEA     EBX,[EBX+climbSize*UNROLL]  ; a separate increment to save a uop for every ADC and store on SnB & later.

        JECXZ   @DoRestLoop                     // LEA does not modify Zero flag,so JECXZ is used.
        JMP     @MainLoop
@DoRestLoop:

lahf
# clobber flags
sahf              ; cheap on AMD and Intel.  This doesn't restore OF,but we only care about CF

# or

setc al
# clobber flags
add  al,255      ; generate a carry if al is non-zero