I am writing a simple BigInteger type in Delphi. It mainly consists of a dynamic array of TLimb, where a TLimb is a 32 bit unsigned integer, and a 32 bit size field, which also holds the sign bit for the BigInteger.
To add two BigIntegers, I create a new BigInteger of the appropriate size and then, after some bookkeeping, call the following procedure, passing it three pointers to the respective starts of the arrays for the left and right operand and the result, as well as the numbers of limbs for left and right, respectively.
Plain code:
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.
This code worked well, and I was pretty satisified with it, until I noticed that, on my development setup (Win7 in a Parallels VM on an iMac) a simple PURE PASCAL addition routine, doing the same while emulating the carry with a variable and a few if clauses, was faster than my plain, straightforward handcrafted assembler routine.
It took me a while to find out that on certain CPUs (including my iMac and an older laptop), the combination of DEC or INC and ADC or SBB could be extremely slow. But on most of my others (I have five other PCs to test it on, although four of these are exactly the same), it was quite fast.
So I wrote a new version, emulating INC and DEC using LEA and JECXZ instead, like so:
Part of emulating code:
@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
That made my code on the "slow" machines almost three times as fast, but some 20% slower on the "faster" machines. So now, as initialzation code, I do a simple timing loop and use that to decide if I'll set up the unit to call the plain or the emulated routine(s). This is almost always correct, but sometimes it chooses the (slower) plain routines when it should have chosen the emulating routines.
But I don't know if this is the best way to do this.
Question
I gave my solution, but do the asm gurus here perhaps know a better way to avoid the slowness on certain CPUs?
Update
Peter and Nils' answers helped me a lot to get on the right track. This is the main part of my final solution for the DEC version:
Plain code:
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...
I removed a lot of white space, and I guess the reader can get the rest of the routine. It is similar to the main loop. A speed improvement of approx. 20% for larger BigIntegers, and some 10% for small ones (only a few limbs).
The 64 bit version now uses 64 bit addition where possible (in the main loop and in Main3 and Main2, which are not "fall-through" like above) and before, 64 bit was quite a lot slower than 32 bit, but now it is 30% faster than 32 bit and twice as fast as the original simple 64 bit loop.
Update 2
Intel proposes, in its Intel 64 and IA-32 Architectures Optimization Reference Manual, 3.5.2.6 Partial Flag Register Stalls -- Example 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
The flag is saved in AL, and through MOVZX in EAX. It is added in through the first ADD in the loop. Then an ADC is needed, because the ADD might generate a carry. Also see comments.
Because the carry is saved in EAX, I can also use ADD to update the pointers. The first ADD in the loop also updates all flags, so ADC won't suffer from a partial flag register stall.
jecxzis only 2 uops on Intel, vs. 1 for a macro-fused test&branch. It's only one total macro-op on AMD. It's not nearly as slow as theLOOPinstruction. This looks like a case where it's justified, since you need to loop without affecting flags. Nils' unrolled version amortizes the cost nicely. – Peter Cordes