ADC / SBB和INC / DEC在某些CPU上的紧密环路中出现问题
我正在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的组合可能非常慢。 但在其他大多数人（我还有其他五台电脑进行测试，但其中四台完全相同）时，速度非常快。
于是我写了一个新版本，用LEA和JECXZ来代替INC和DEC ，如下所示：
模拟代码的一部分：
@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％。 所以现在，作为初始化代码，我做了一个简单的时序循环，并使用它来决定是否设置单元来调用plain或者仿真例程。 这几乎总是正确的，但有时当它选择仿真例程时，它会选择（较慢）简单例程。
但我不知道这是否是最好的方法。
题
我给了我的解决方案，但是在这里做专家大师可能知道避免某些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...
我删除了大量的空白空间，我想读者可以获得其余的例程。 它与主循环相似。 速度提高约。 对于较大的BigInteger来说，这个比例是20％，对于小型的则只有10％（只有很少的几个）。
64位版本现在在可能的情况下使用64位加法（在主循环和Main3和Main2中，它们不是像上面那样的“跌落”），之前64位比32位慢很多，但现在它比32位快30％，比原来简单的64位循环快两倍。
你看到的是一个部分旗帜的摊位。
英特尔CPU（P4除外）分别重命名每个标志位，因此JNE只取决于设置所用标志的最后一条指令（本例中只有Z标志）。 事实上，最近的英特尔CPU甚至可以在内部将inc/jne成一个单一的inc-and-branch uop（宏融合）。 然而，读取最后一条更新任何标志的指令未修改的标志位时会遇到麻烦。
Agner Fog表示，英特尔CPU（甚至PPro / PII）不会在inc / jnz上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对于之前写入标志的任何东西都有“错误”的依赖关系。 这意味着循环条件无法检测循环的结束，直到adc dep链的执行到达那里为止，所以当循环分支停止被采用时可能发生的分支误预测不能被提前检测到。 尽管如此，它确实可以防止任何部分标志失速。
你的lea / jecxz很好地避免了这个问题。 在SnB和之后的版本中速度较慢，因为你根本没有展开你的循环。 您的LEA版本是11个uops（可以每3个周期发布一个迭代），而inc版本是7个uops（每2个周期可发布一个），不包括插入的标志合并uop，而不是拖延。
如果loop指令不是很慢，那对于这一点来说是完美的。 它在AMD推土机系列（1 m-op，与熔融比较分支相同的成本）和Via Nano3000上实际上很快。 这对所有的英特尔CPU都是不利的，尽管（SnB系列有7个uop）。
展开
展开时，由于使用指针代替索引编址模式，您可以获得另一个小增益，因为2-reg寻址模式不能在SnB和更高版本上进行微熔丝。 一组load / adc / store指令是6个微操作而没有微融合，但只有4个微融合。 CPU可以发布4个融合域uops /时钟。 （有关此级别的详细信息，请参阅Agner Fog的CPU微型文档和指令表。）
确保CPU能够比执行更快地发出指令，以确保它能够在指令流中看到足够远的位置以吸收insn提取中的任何气泡（例如，分支错误预测）。 拟合28uop循环缓冲区也意味着节省功耗（在Nehalem上，避免指令解码瓶颈）。有些东西像指令对齐和跨越uop cache-line边界，这使得难以在没有环路的情况下维持全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将使上述循环精确地为英特尔CPU提供14个融合域uops。 adc是2 ALU（+1内存）， jecxz是2，其余（包括LEA）都是1.在未融合的域中，有10个ALU /分支和6个内存（好吧，8个内存，如果你真的统计存储地址和分别存储数据）。
adc的uops可以在任何端口上运行，并且lea可以在p0 / p1上运行。 跳转使用port5（并且jecx也使用p0 / p1中的一个） 因此，对于haswell前处理器，使用LEA / JECXZ，展开2将不会使ALU或加载/存储端口饱和。 4的展开将带来22个融合的uops（发布6个周期）。 14 ALU＆branch：4.66c执行。 12个内存：6个周期执行。 所以4的展开会使Haswell的前处理器饱和，但只是几乎没有。 CPU不会有任何指令缓冲区在分支mispredict上通过。
Haswell及其后续版本始终会成为前端瓶颈（每个时钟限制4个uops），因为load / adc / store组合需要4个uops，并且每个时钟可以保持一个。 因此，如果不削减adc吞吐量，就没有任何“空间”可以用于循环开销。 这是你必须知道不要过分和展开太多的地方。
在Broadwell / Skylake上， adc只有1c延迟的单个uop，而load / adc r, m / store似乎是最好的顺序。 adc m, r/i是4 uops。 这应该每个时钟支持一个adc，就像AMD一样。
在AMD CPU上， adc只是一个宏操作，所以如果CPU能够维持4的问题率（即没有解码瓶颈），那么他们也可以使用它们的2个加载/ 1存储端口来击败Haswell。 此外，AMD上的jecxz与其他任何分支一样高效：只有一个宏操作。 多精度数学是AMD CPU擅长的少数几件事之一。 在一些整数指令中较低的延迟使它们在一些GMP例程中具有优势。
超过5的展开可能会损害Nehalem的性能，因为这会使循环比28uop循环缓冲区大。 指令解码然后将您限制在每个时钟小于4个uops。 在更早的时候（Core2），有一个64B x86指令循环缓冲区（x86代码64B，而不是uops），这有助于一些解码。
除非这个adc例程是你应用程序中唯一的瓶颈，否则我会将展开因子降低到2。或者甚至可能不展开，如果这样可以节省大量的序言/尾声代码，并且你的BigInts不是太大。 当调用者调用大量不同的BigInteger函数时，您不希望过多地膨胀代码并创建缓存未命中，例如添加，添加，删除和执行其他操作。 如果您的程序在每次通话的内部循环中都没有花费很长时间，那么展开太多而无法在microbenchmarks上获得胜利的话，可能会在自己的脚下发生。
如果你的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将始终与来自最后一个adc的CF输出同时准备就绪。 （在AMD和P4 / Silvermont部分注册表中有一个关于整个注册表的错误解释，他们没有单独重新命名部分注册表）。 保存/恢复是adc dep链的一部分，而不是循环条件dep链。
循环条件仅检查由cmp ， sub或dec写入的标志。 保存/恢复周围的标志不会使它成为adc dep链的一部分，因此在adc执行到达之前可以检测到循环结尾处的分支预测错误。 （这个答案的以前的版本得到了这个错误。）
在设置代码中几乎可以肯定有一些空间可以削减指令，也许可以通过使用值开始的寄存器。 你不必使用edi和esi作为指针，尽管我知道当你使用符合其“传统”用法的寄存器时，初始开发更容易。 （例如EDI中的目标指针）。
Delphi让你使用ebp吗？ 拥有第7个寄存器真好。
很明显，64位代码会让你的BigInt代码运行速度快两倍，即使你不必担心在一个64位adc循环结束时做一个adc位的adc 。 它也会给你两倍的寄存器数量。
有很多x86芯片在使用时间上差别很大，因此您不可能为所有x86芯片提供最佳代码。 在使用之前，你有两个已知的好功能和基准测试方法已经非常先进。
但是，根据BigInteger的大小，可以通过简单的循环展开来改进代码。 这将彻底消除循环开销。
例如，你可以执行一个专门的块，添加如下的八个整数：
@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个元素需要处理，并使用已有的单元素添加循环来完成剩余的几个元素，就可以执行上述块。
对于大型的BitInteger，你大部分时间都会花在展开的部分上，而现在这个部分的执行速度要快很多。
如果你希望它更快，那么编写七个专门用于剩余元素计数的附加块，并根据元素计数对它们进行分支。 这可以通过将7个地址存储在查找表中，从中加载地址并直接跳入专用代码来完成。
对于小的元素数量，这完全消除了整个循环，对于大型元素，您将获得展开循环的全部好处。
链接地址: http://www.djcxy.com/p/28771.html上一篇: Problems with ADC/SBB and INC/DEC in tight loops on some CPUs
下一篇: Can x86's MOV really be "free"? Why can't I reproduce this at all?