Big Integer Subtraction
Subtracting B from A on the Power architecture is easy when both A and B fit in a single machine word:
subf[c] rt, B, A. Much more interesting is the case where they do not fit, as is often the case in big number libraries and cryptographic code. In order to make this fast, this needs to be implemented directly in assembly for the target architecture. This exercise, and the code in it, arose from optimizing hot spots in the Go
math/big library as it is used by the crypto packages.
Big integers are (in our case) stored as an array of words and a sign. The function being implemented,
subVV (subtract-vector-vector) has several conditions to the API in order to call it: the arguments all have the same length, (This is a fine assumption - to do subtraction of numbers that don't have the same number of words, truncate them to length of the shorter array and handle the case of needing to borrow once more at the end; this is handled at the call site) and function must return 1 if there was a borrow and 0 otherwise. Thus, the subtraction algorithm can be outlined in psuedocode (or actual code):
var c = 0 for i from 0 to length: result[i] = A[i] - B[i] - c c = 1 if that borrowed, 0 if it didn't return c
The ideal instruction to implement this will handle both of these steps. To understand how this ideal instruction should work, it pays off to examine what the subtraction instruction does.
According to the Power ISA manual (version 2.07, p. 68), subtraction performs "the sum ¬B + A + 1" and places it in rt. This works due to the nature of two's complement numbers: namely, that addition of numbers represented in two's complement form works identically to addition of unsigned numbers. This allows performing A + (-B). -B, in two's complement, is ¬B+1.
The desired instruction takes a possible borrow into account, and so would look like ¬B + A + 1 - c, where c is 1 if there was a borrow and 0 otherwise.
The difference between
subfc on POWER is that the
subfc version sets the carry bit, CA, in the processor. When will subtraction carry? This is easiest to examine on a single bit:
|a||b||¬b||a + ¬b + 1||CA||Borrowed? (b > a)|
The CA bit is set to 1 when a ≥ b, and 0 when a < b: CA serves as a not-borrow flag. This allows rewriting the expression ¬B + A + 1 - c in terms of CA by noting that CA = 1 - c *(Proof left as an exercise to the reader), giving ¬B + A + CA.
A quick browse of the ISA, and we find the instruction we're looking for: Subtract From Extended,
subfe sets the CA bit. Exactly as required, "the sum ¬B + A + CA" is placed in rt.
This can be explored by considering an example of 9-bit subtraction on a 3-bit computer.
368 101 110 000 - 123 - 001 111 011 ----- ------------- 245 011 110 101
Beginning with the least significant words,
000 - 011 = 000 + ¬011 + CA = 000 + 100 + 1 = 101
For the first subtraction, there was no previous borrow and so CA must be 1. This does not overflow, and so CA is 0 for the next word:
110 - 111 - c = 110 + ¬111 + 1 - c = 110 + 000 + CA = 110
This leads to our final word of the subtraction, again with CA = 0:
101 - 001 - c = 101 + ¬001 + 1 - c = 101 + 110 + CA = 011
This just leaves a couple loose ends. First, to use
subfe for the loop, CA needs to have an initial value. As this is a normal subtraction without a borrow, that initial value must be 1. Additionally, this implementation is being written targeting the Go assembler which uses its own assembly syntax.
// func subVV(r, a, b Word) c Word TEXT ·subVV, NOSPLIT, $0 MOVD res_len+8(FP), R7 // length of result MOVD a+24(FP), R8 // address of subtrahend MOVD b+48(FP), R9 // address of minuend MOVD r+0(FP), R10 // address of result MOVD $0, R5 // i = 0 MOVD $8, R28 // unaware of mulli equivalent in go asm SUBC R0, R0 // R0 always contains 0, so this sets CA JMP END LOOP: MULLD R5, R28, R6 // offset in bytes by i MOVD (R8)(R6), R11 // a[i] MOVD (R9)(R6), R12 // b[b] SUBE R12, R11, R15 // same as subfe r15, r12, r11 MOVD R15, (R10)(R6) // store result in r[i] ADD $1, R5 // i++ END: CMP R5, R7 // if i < len(r): BLT LOOP // goto LOOP MOVD $0, R4 ADDZE R4 // R4 += CA XOR $1, R4 // return value is !CA MOVD R4, r+72(FP) // Go passes return values on the stack RET
How much faster is this assembly than the generic implementation? The benchmark for addVV is easily modified to benchmark subVV, giving the following results:
benchmark old ns/op new ns/op delta BenchmarkSubVV/1 16.1 6.76 -58.01% BenchmarkSubVV/2 18.2 9.59 -47.31% BenchmarkSubVV/3 20.5 9.32 -54.54% BenchmarkSubVV/4 22.9 11.3 -50.66% BenchmarkSubVV/5 25.5 13.3 -47.84% BenchmarkSubVV/10 42.6 27.1 -36.38% BenchmarkSubVV/100 259 198 -23.55% BenchmarkSubVV/1000 2408 1910 -20.68% BenchmarkSubVV/10000 23853 19037 -20.19% BenchmarkSubVV/100000 244542 190399 -22.14% benchmark old MB/s new MB/s speedup BenchmarkSubVV/1 3968.14 9460.99 2.38x BenchmarkSubVV/2 7045.22 13347.39 1.89x BenchmarkSubVV/3 9357.28 20609.20 2.20x BenchmarkSubVV/4 11156.85 22688.51 2.03x BenchmarkSubVV/5 12556.21 24002.40 1.91x BenchmarkSubVV/10 15007.22 23583.03 1.57x BenchmarkSubVV/100 24693.65 32217.26 1.30x BenchmarkSubVV/1000 26575.40 33492.23 1.26x BenchmarkSubVV/10000 26830.29 33617.69 1.25x BenchmarkSubVV/100000 26171.33 33613.55 1.28x