在某些CPU的紧密循环中出现ADC/SBB和INC/DEC问题

Question

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

要添加两个BigIntegers,我创建一个适当大小的新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.

这段代码工作得很好,我对此非常满意,直到我注意到,在我的开发设置(在iMac上的Parallels VM中的Win7)中,一个简单的PURE PASCAL添加例程,在模拟带变量的进位时执行相同操作一些if条款,比我简单直接的手工编译程序更快.

我花了一段时间才发现某些CPU(包括我的iMac和旧款笔记本电脑),DEC或者INC和ADC或者组合SBB可能非常慢.但是对于我的大多数其他人(我有五台其他PC来测试它,虽然其中有四台是完全一样的),但速度非常快.

所以我写了一个新版本,模仿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, 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...    

我删除了很多空白区域,我想读者可以完成剩下的日常工作.它类似于主循环.速度提高约.对于较大的BigIntegers,20%,对于小型BigIntegers,只有10%(只有几个肢体).

64位版本现在尽可能使用64位加法(在主循环和Main3和Main2中,它们不是像上面那样"直通")之前,64位比32位慢得多,但现在它比32位快30%,比原来的简单64位循环快两倍.

更新2

英特尔在其英特尔64和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,并通过MOVZX中EAX.它是通过ADD循环中的第一个添加的.然后ADC需要一个,因为ADD可能会生成一个进位.另见评论.

因为进位被保存EAX,我也可以ADD用来更新指针.ADD循环中的第一个也会更新所有标志,因此ADC不会受到部分标志寄存器停顿的影响.

Answer 1

你所看到的是一个部分旗帜摊位.

Intel CPU(P4除外)分别重命名每个标志位,因此JNE仅取决于设置它使用的所有标志的最后一条指令(在这种情况下,只是Z标志).事实上,最近的英特尔CPU甚至可以内部组合inc/jne成一个单独的分支uop(宏融合).但是,当读取更新任何标志的最后一条指令未修改的标志位时,会出现问题.

Agner Fog表示英特尔CPU(甚至PPro/PII)不会停滞不前inc / jnz.实际上并不是inc/jnz那种停滞,它是adc在下一次迭代中必须CF在inc写入其他标志之后读取标志但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使进位标志不变的事实." (适用于Pentium M/Core2/Nehalem).建议避免inc/ dec完全过时,仅适用于P4.其他CPU分别重命名EFLAGS的不同部分,并且只在需要合并时才会遇到麻烦(读取上一个insn未修改的标志以写入任何标志).

在它快速的机器上(Sandybridge及其后),当你读取未被最后一条修改它的指令写入的位时,它们会插入一个额外的uop来合并标志寄存器.这是很多比拖延7个周期快,但仍不理想.

P4总是跟踪整个寄存器,而不是重命名部分寄存器,甚至不是EFLAGS.因此,inc/jz对于在它之前写入标志的任何内容都有"假"依赖.这意味着循环条件在adcdep链的执行到达之前无法检测到循环的结束,因此无法及早检测到循环分支停止时可能发生的分支错误预测.但它确实可以防止任何部分标志停顿.

你lea / jecxz很好地避免了这个问题.它在SnB上较慢,后来因为你根本没有展开你的循环.你的LEA版本是11 uops(可以每3个周期发出一次迭代),而inc版本是7 uops(每2个周期可以发出一个iter),不计算它插入的标志合并uop而不是停止.

如果该loop指令是不慢,那就完美了这一点.它实际上在AMD Bulldozer系列上很快(1 m-op,融合比较和分支成本相同)和Via Nano3000.但是在所有Intel CPU上都很糟糕(SnB系列上有7个uop).

展开

展开时,使用指针而不是索引寻址模式可以获得另一个小增益,因为2-reg寻址模式不能在SnB上及以后微熔合.一组加载/ adc/存储指令是没有微融合的6个uop,但只有4个微融合.CPU可以发出4个融合域uops/clock.(有关此级别的详细信息,请参阅Agner Fog的CPU微架文档和指令表.)

保存uop,以确保CPU可以比执行更快地发出指令,以确保它可以在指令流中看得足够远,以吸收insn fetch中的任何气泡(例如,分支错误预测).安装在28uop环路缓冲器中也意味着省电(并且在Nehalem上,避免了指令解码瓶颈.)有些指令对齐和交叉uop缓存线边界使得很难在没有环路的情况下维持完整的4 uops/clock缓冲也是.

另一个技巧是保持指向缓冲区末尾的指针,并向上计数到零.(所以在你的循环开始时,你得到第一个项目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将使上述循环正好为英特尔CPU的14个融合域uops. adc是2 ALU(+1融合内存),jecxz是2,其余(包括LEA)都是1.在未融合的域中,10个ALU /分支和6个内存(如果你真的计算存储地址和存储,那么8个内存 -数据分开).

• 每次迭代14个融合域uops:每4个时钟发出一次迭代.(最后的奇数2个uop必须以2的一组形式发出,即使是从循环缓冲区发出的.)
• 10个ALU和分支uops:需要3.33c才能在预处理时执行所有操作.我认为任何一个端口都不会成为瓶颈:adcuops可以在任何端口lea上运行,并且可以在p0/p1上运行.跳转使用port5(并且jecx也使用p0/p1之一)
• 6个存储器操作:在Haswell以前的CPU上执行3c,每个时钟可以处理2个.Haswell为商店增加了一个专用的AGU,因此它可以维持2load + 1store/clock.

因此,对于使用LEA/JECXZ的预处理CPU,展开2将不会使ALU或加载/存储端口饱和.展开4将使其达到22个融合的uop(发布6个周期).14 ALU&branch:执行4.66c.12个内存:执行6个周期.所以4的展开将使Haswell CPU前期饱和,但只是勉强.CPU不会有任何指令缓冲区在分支错误预测上流失.

Haswell和后来将始终在前端瓶颈(每个时钟限制4个uop),因为加载/ adc/存储组合需要4个uop,并且每个时钟可以维持一个.因此,在没有削减adc吞吐量的情况下,循环开销从来没有任何"空间" .这是你必须知道不要过度和展开太多的地方.

在Broadwell/Skylake上,adc只有一个具有1c延迟的uop,并且加载/ adc r, m/存储似乎是最好的序列. adc m, r/i是4 uops.这应该支持每个时钟一个adc,如AMD.

在AMD CPU上,adc只有一个宏操作,因此如果CPU可以维持4的发布率(即没有解码瓶颈),那么他们也可以使用他们的2个load/1存储端口来击败Haswell.此外,jecxzAMD与其他任何分支一样高效:只有一个宏操作.多精度数学是AMD CPU擅长的少数几项工作之一.某些整数指令的较低延迟使它们在某些GMP例程中具有优势.

超过5的展开可能会损害Nehalem的性能,因为这会使循环比28uop循环缓冲区更大.然后,指令解码会限制每个时钟少于4个uop.甚至更早(Core2),有一个64B x86指令循环缓冲区(x86代码的64B,而不是uops),这有助于一些解码.

除非这个adc例程是你的应用程序中唯一的瓶颈,否则我会将展开因子保持在2或者甚至不展开,如果这样可以节省大量的序言/结尾代码,而且你的BigInts不会太大.当调用者调用许多不同的BigInteger函数(如add,sub,mul)并在其间执行其他操作时,您不希望过多地膨胀代码并创建缓存未命中.如果你的程序在你的内循环中没有花费很长时间来进行每次通话,那么展开太多以赢得微基准测试可能会让自己陷入困境.

如果你的BigInt值通常不是很大,那么它不仅仅是你必须调整的循环.较小的展开可能有助于简化序言/结语逻辑.当然,确保检查长度,以便ECX不会过零而不会为零.这是展开和向量的麻烦.:/

保存/恢复CF旧CPU,而不是无标记循环:

这可能是最有效的方式:

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

使用与adc dep链相同的寄存器实际上不是问题:eax将始终CF与最后一个输出同时准备就绪adc.(在AMD和P4/Silvermont上,部分注册写入对整个注册表有误判.它们不会单独重命名部分注册表).保存/恢复是adc dep链的一部分,而不是循环条件dep链.

循环条件只检查书面的标志cmp,sub或dec.保存/恢复它周围的标志并不会使它成为adcdep链的一部分,因此可以在adc执行到达之前检测循环结束时的分支错误预测.(这个答案的先前版本错了.)

几乎肯定有一些空间来削减设置代码中的指令,可能通过使用值开始的寄存器.你没有必要使用edi和esi作为指针,虽然我知道当你使用寄存器时,它会使初始开发变得更容易,这与他们的"传统"用法一致.(例如EDI中的目标指针).

Delphi是否允许您使用ebp？有第7个寄存器真好.

显然64位代码会使你的BigInt代码运行速度快两倍,即使你不得不担心adc在64位循环结束时做一个32b adc.它还会给你2倍的寄存器数量.

Answer 2

有很多x86芯片在使用时间上有很大差异,你无法真正拥有所有这些芯片的最佳代码.您在使用前获得两个已知良好功能和基准的方法已经相当先进.

但是,根据BigIntegers的大小,您可以通过简单的循环展开来改进代码.这将彻底消除循环开销.

例如,您可以执行一个专门的块,它会添加八个整数,如下所示:

@AddEight:
        MOV     EAX,[ESI + EDX*CLimbSize + 0*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 0*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 0*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 1*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 1*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 1*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 2*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 2*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 2*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 3*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 3*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 3*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 4*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 4*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 4*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 5*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 5*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 5*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 6*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 6*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 6*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 7*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 7*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 7*CLimbSize],EAX
        LEA     ECX,[ECX - 8]

现在重建循环,只要你有超过8个要处理的元素就执行上面的块,并使用你已经拥有的单个元素加法循环来完成其余的几个元素.

对于大型BitIntegers,您将花费大部分时间在展开的部分,现在应该执行得更快.

如果你想要它更快,那么写下七个专门用于剩余元素计数的块,并根据元素计数分支到它们.这可以通过将七个地址存储在查找表中,从中加载地址并直接跳转到专用代码来完成.

对于小元素计数,这完全消除了整个循环,对于大元素,您将获得展开循环的全部好处.