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

Question

我在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.

这段代码很好用，我对此非常满意，直到我注意到，在我的开发设置（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变慢的更好方法吗？

更新资料

彼得和尼尔斯（Peter and Nils）的回答对我帮助很大，使他们走上了正确的道路。这是我对 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标志）。实际上，最近的Intel CPU甚至可以internally combine an inc/jne into a single inc-and-branch uop（宏融合）。然而，麻烦的是，读取最后一条更新任何标志的指令未修改的标志位。

Agner Fog说Intel 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保持进位标志不变的事实的代码。” （用于奔腾M / Core2 / Nehalem）。完全避免使用 inc / dec的建议已过时，仅适用于P4。其他CPU分别重命名EFLAGS的不同部分，并且仅在需要合并时才会遇到麻烦（读取最后一个insn未修改的标志以写入任何标志）。

在运行速度较快的计算机（Sandybridge及更高版本）上，当您读取修改它的最后一条指令未写入的位时，它们将插入额外的uop来合并标志寄存器。这比停转7个周期要快得多，但仍不理想。

P4始终跟踪整个寄存器，而不是重命名部分寄存器，甚至不重命名EFLAGS。因此 inc/jz对其之前写入标志的内容具有“假”依赖性。这意味着直到 adc dep链的执行到达那里时，循环条件才能检测到循环的结束，因此无法及早检测到循环分支停止时可能发生的分支错误预测。但是，它确实可以防止任何部分标志停止。

您的 lea / jecxz很好地避免了该问题。在SnB上，它的运行速度要慢一些，在以后的版本中，因为您根本没有展开循环。您的LEA版本为11微码（每3个周期可以发出一个迭代），而 inc版本为7微码（每2个周期可以发出一个迭代），这不包括它插入的标志合并的uop而不是停顿。

如果 the loop instruction wasn't slow，则非常适合。实际上，在AMD Bulldozer系列（1 m-op，成本与融合比较与分支相同）和Via Nano3000上，它的运行速度很快。不过，这在所有Intel CPU上都是不好的（在SnB系列上为7微秒）。



展开

展开时，通过使用指针而不是索引寻址模式 because 2-reg addressing modes can't micro-fuse on SnB and later，可以获得另一小的收益。一组加载/ adc /存储指令在无微融合的情况下为6 oups，在有微融合的情况下仅为4。 CPU可以发出4个融合域uops /时钟。 （有关此级别的详细信息，请参阅Agner Fog的CPU microarch文档和说明表。）

请保存uops，以确保CPU发出指令的速度比执行速度快，以确保在指令流中可以看到足够远的距离，以吸收insn fetch中的气泡（例如，分支预测错误）。装入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应该会很好。既然您很可能，就不必过度操作。只需3或4，甚至2的展开，就能使Haswell之前的加载/存储端口饱和。

展开2将使上述循环对于Intel CPU而言恰好是14个融合域。 adc是2个ALU（+1个已融合的内存）， jecxz是2个，其余（包括LEA）都是1。在未融合域中，10个ALU /分支和6个内存（如果真的算的话，有8个内存）分别存储地址和存储数据）。


每次迭代14个融合域指令：每4个时钟发出一次迭代。 （即使从循环缓冲区，最后的奇数2微码也必须以2为一组发出）。
10个ALU和分支uops：花费3.33c才能在haswell之前执行所有操作。我也不认为任何端口都会成为瓶颈，或者： adc的uops可以在任何端口上运行，而 lea可以在p0 / p1上运行。跳转使用端口5（而jecx也使用p0 / p1之一）
6个内存操作：需要3c才能在Haswell之前的CPU上执行，每个时钟可以处理2个。 Haswell为商店添加了专用的AGU，因此它可以维持2load + 1store / clock。


因此，对于使用ha-well的CPU，使用LEA / JECXZ，展开2不会使ALU或加载/存储端口完全饱和。展开4将使其达到22融合uops（发出6个周期）。 14 ALU＆branch：4.66c执行。 12个内存：6个周期执行。因此，展开4个操作将使Haswell之前的CPU饱和，但几乎没有。 CPU将不会有任何指令缓冲区来处理分支错误预测。

Haswell及其以后的版本始终会在前端出现瓶颈（每个时钟限制为4 uups），因为load / adc / store组合需要4 uop，并且每个时钟可以维持1 uop。因此，在不减少 adc吞吐量的情况下，绝没有任何“空间”可用于循环开销。这是您必须知道不要过度使用和展开太多的地方。

在Broadwell / Skylake上， adc is only a single uop with 1c latency, and load / adc r, m / store appears to be the best sequence. adc m, r/i为4 oups。像AMD这样，每个时钟应维持一个adc。

在AMD CPU上， adc只是一个宏操作，因此如果CPU可以维持4的发行率（即没有解码瓶颈），那么他们还可以使用其2加载/ 1存储端口来击败Haswell。同样，AMD上的 jecxz与其他任何分支一样有效：只有一个macro-op。多精度数学是AMD CPU擅长的少数功能之一。一些整数指令的较低延迟使它们在某些GMP例程中具有优势。



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

除非此 adc例程是您应用程序中的唯一瓶颈，否则我会将展开系数降低到2。或者甚至不展开，如果这样可以节省大量的序言/结语代码，而您的BigInts也不太合适大。当调用者调用许多不同的BigInteger函数（如add，sub，mul和介于两者之间的其他事情）时，您不想过多地夸大代码并造成高速缓存未命中。如果您的程序在每次调用时都没有花费很长时间在您的内部循环中，那么展开过多的工作就无法赢得微基准测试。

如果您的BigInt值通常不是巨大的，则不仅仅是您必须调整的循环。较小的展开可能会简化序言/结尾逻辑。当然，请确保检查长度，以使ECX不会过零而不为零。这是展开和向量的麻烦。 ：/



保存/恢复旧CPU的 CF，而不是无标志循环：

这可能是最有效的方法：

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上，部分规范的写入在整个reg上具有错误的dep。它们不会分别重命名部分reg）。保存/恢复是adc dep链的一部分，而不是循环条件dep链的一部分。

循环条件仅检查由 cmp， sub或 dec写入的标志。在其周围保存/恢复标志不会使其成为 adc dep链的一部分，因此可以在 adc执行到达之前检测到循环末尾的分支错误预测。 （此答案的先前版本有此错误。）



几乎肯定有一些余地可以整理设置代码中的指令，也许可以使用值开始的寄存器。尽管我知道当您以与寄存器的“传统”用法一致的方式使用寄存器时，它使初始开发更加容易，但您不必对指针使用edi和esi。 （例如EDI中的目标指针）。

Delphi是否允许您使用 ebp？拥有第七个寄存器真是太好了。

显然，即使您必须担心在64位 adc循环的末尾执行单个32b adc时，64位代码也可以使您的BigInt代码运行速度提高大约一倍。它也会给您2倍的寄存器数量。