问题：

某些CPU上紧循环中ADC/SBB和INC/DEC的问题

劳韬

2023-03-14

我正在用Delphi编写一个简单的BigInteger类型。它主要由一个动态TLimb数组和一个32位大小的字段组成，其中TLimb是一个32位无符号整数，该字段还保存biginteger的符号位。

要添加两个BigInteger，我创建一个大小合适的新BigInteger，然后在进行一些簿记后，调用以下过程，向它传递三个指针，分别指向左和右操作数组的起始点和结果，以及左和右html" target="_blank">操作数组的分支数。

明码：

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.

这段代码运行得很好，我对它非常满意，直到我注意到，在我的开发设置中（在iMac上的Parallels VM中的Win7)，一个简单的纯PASCAL加法例程，在用一个变量和几个if子句模拟进位时做同样的事情，比我简单、直接的手工汇编例程要快。

我花了一段时间才发现，在某些CPU上（包括我的iMac和一台旧的笔记本电脑），dec或inc和adc或sbb的组合可能非常慢。但在我的大多数其他电脑上（我还有五台电脑要测试它，尽管其中四台完全一样），它相当快。

模拟代码的一部分：

@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%。所以现在，作为初始化代码，我做了一个简单的定时循环，并用它来决定是将单元设置为调用普通例程还是模拟例程。这几乎总是正确的，但有时它选择了（较慢的）普通例程，而它应该选择模拟例程。

但我不知道这是不是最好的办法。

class procedure BigInteger.PlainAdd(Left, Right, Result: PLimb; LSize, 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,ECX
        JAE     @SkipSwap
        XCHG    ECX,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],EAX
        MOV     EAX,[ESI + 2*CLimbSize]
        ADC     EAX,[EDI + 2*CLimbSize]
        MOV     [EBX + 2*CLimbSize],EAX
        MOV     EAX,[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...

64位版本现在在可能的情况下使用64位加法（在main循环以及Main3和Main2中，它们不像上面那样是“fall-through”），以前，64位比32位慢得多，但现在比32位快30%，是最初简单的64位循环的两倍。

Intel在其Intel64和IA-32体系结构优化参考手册中建议3.5.2.6部分标志寄存器停顿--示例3-29：

        XOR     EAX,EAX

        .ALIGN  16

@MainLoop:

        ADD     EAX,[ESI]       // Sets all flags, so no partial flag register stall
        ADC     EAX,[EDI]       // ADD added in previous carry, so its result might have carry
        MOV     [EBX],EAX
        MOV     EAX,[ESI + CLimbSize]
        ADC     EAX,[EDI + CLimbSize]
        MOV     [EBX + CLimbSize],EAX
        MOV     EAX,[ESI + 2*CLimbSize]
        ADC     EAX,[EDI + 2*CLimbSize]
        MOV     [EBX + 2*CLimbSize],EAX
        MOV     EAX,[ESI + 3*CLimbSize]
        ADC     EAX,[EDI + 3*CLimbSize]
        MOV     [EBX + 3*CLimbSize],EAX
        SETC    AL              // Save carry for next iteration
        MOVZX   EAX,AL
        ADD     ESI,CUnrollIncrement*CLimbSize  // LEA has slightly worse latency
        ADD     EDI,CUnrollIncrement*CLimbSize
        ADD     EBX,CUnrollIncrement*CLimbSize
        DEC     ECX
        JNZ     @MainLoop

该标志保存在al中，并通过eax中的movzx保存。它是通过循环中的第一个add添加的。然后需要ADC，因为add可能会生成进位。另见评论。

因为进位保存在EAX中，所以我也可以使用add来更新指针。循环中的第一个add还会更新所有标志，因此ADC不会出现部分标志寄存器停滞。

云俊名

2023-03-14

您在旧的P6系列CPU上看到的是部分标志停滞。
早期的SandyBridge系列处理合并的效率更高，而后来的SNB系列（例如Skylake）则完全没有合并成本：同时需要CF和SPAZO组的一些标志的UOP将它们作为两个独立的输入读取。

Intel CPU（不包括P4)单独重命名每个标志位，因此jne仅依赖于设置其使用的所有标志的最后一条指令（在本例中，仅为z标志）。事实上，最近的Intel CPU甚至可以在内部将inc/jne组合成单个inc-and-branch uop（宏融合）。然而，当读取上一条更新了任何标志的指令未修改的标志位时，麻烦就来了。

Agner Fog说Intel CPU（甚至是PPro/PII）不会在inc/jnz上停滞不前。实际上并不是inc/jnz停滞不前，而是adc在下一次迭代中必须在inc写了其他标志但未修改cf之后读取cf标志。

; 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)

Agner Fog还更笼统地说：“避免依赖于INC或DEC保留carry标志不变的事实的代码。”（对于奔腾M/Core2/Nehalem）。完全避免inc/dec的建议已经过时，只适用于P4。其他CPU单独重命名EFLAGS的不同部分，只有在需要合并时才会遇到麻烦（读取上次insn未修改的标志以写入任何标志）。

在速度快的机器上（Sandybridge和更高的版本），当您读取上一条修改它的指令没有写入的位时，他们会插入额外的uop来合并标志寄存器。这比熄火7个循环要快得多，但仍不理想。

P4总是跟踪整个寄存器，而不是重命名部分寄存器，甚至不是eFlags。因此，inc/jz对之前编写标志的内容有一个“false”依赖关系。这意味着循环条件在ADCdep链的执行到达那里之前无法检测到循环的结束，因此不能及早检测到当循环分支停止被采取时可能发生的分支误预测。不过，它确实防止了任何部分标志停滞。

如果循环指令不慢，它将非常适合于此。它实际上在AMD推土机家族上速度很快（100万，与融合的比较和分支相同的成本），并通过nano3000。不过，它在所有英特尔CPU上都很糟糕（在SNB系列上有7个UOP）。

当您展开时，您可以从使用指针而不是索引寻址模式中获得另一个小好处，因为2-REG寻址模式不能在SnB和以后的时间内微融合。一组加载/ADC/store指令在没有微融合的情况下为6个uops，而在微融合的情况下仅为4个uops。CPU可以发出4个融合域UOPS/时钟。（请参见Agner Fog的CPU microarch文档和指令表，了解这一级别的详细信息。）

尽可能保存uops，以确保CPU可以比执行更快地发出指令，确保它可以在指令流中看到足够远的前面，以吸收insn提取中的任何气泡（例如分支错误预测）。安装在28UOP循环缓冲区中也意味着节省功耗（在Nehalem上，避免指令解码瓶颈）还有一些事情，比如指令对齐和跨越uop缓存线边界，这也使得在没有循环缓冲区的情况下很难维持完整的4 uops/时钟。

另一个技巧是将指针保持在缓冲区的末尾，并向零计数。（因此，在循环开始时，第一个项是end[-idx]。）

        ; 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:

4的展开应该不错。没必要做过头，因为你是个问题。将能够饱和预Haswell的加载/存储端口，只有3或4个展开，甚至可能是2个。

2的展开将使上述循环正好14个Intel CPU的融合域UOP。ADC为2个ALU(+1个融合内存），JECXZ为2，其余（包括LEA）均为1。在未使用的域中，10个ALU/Branch和6个内存（如果您真的分别计算存储地址和存储数据，则为8个内存）。

null

在Broadwell/Skylake上，ADC只是一个具有1C延迟的uop，而load/ADC r,m/store似乎是最佳序列。ADC m,r/i为4 UOPS。这应该维持一个adc每时钟，像AMD。

在AMD CPU上，ADC只是一个宏操作，所以如果CPU可以维持4的发布率（即没有解码瓶颈），那么它们也可以使用2 load/1存储端口来击败Haswell。而且，AMD上的jecxz与其他分支一样高效：只有一个宏操作。多精度数学是AMD CPU擅长的少数事情之一。一些整数指令的较低延迟使它们在一些GMP例程中具有优势。

展开超过5可能会损害Nehalem上的性能，因为这会使循环大于28uop循环缓冲区。指令解码将限制您在每个时钟少于4个uops。在更早的版本(Core2)中，有一个64B的x86指令循环缓冲区(64B的x86代码，而不是uops)，这有助于解码。

除非这个ADC例程是应用程序中唯一的瓶颈，否则我会将展开因子降低到2。或者甚至可以不展开，如果这节省了大量的序言/尾声代码，并且您的BigInts不太大。当调用者调用许多不同的BigInteger函数（如add、sub、mul）并在两者之间执行其他操作时，您不希望代码膨胀太多并造成缓存丢失。如果程序没有在每次调用的内循环中花费很长时间，那么在微基准测试中展开太多而无法获胜可能会搬起石头砸自己的脚。

如果您的BigInt值通常不是很大，那么您要调优的不仅仅是循环。较小的展开可能有助于简化序幕/尾声逻辑。当然，要确保检查长度，这样ECX就不会在不为零的情况下过零。这就是展开和向量的麻烦。：/

这可能是最有效的方法：

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

显然，64bit代码将使BigInt代码的运行速度提高大约一倍，尽管您必须担心在64bitADC循环结束时执行一个32bADC。它还会给你2倍的寄存器数量。

某些CPU上紧循环中ADC/SBB和INC/DEC的问题

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档