Improve codegen for carry/borrow

[mratsim]

The current code add/sub/mul can be tuned to help GCC/Clang significantly improve the assembly generated.

Next commit will bring the ADD code from this:

to this

This is unrolled, add is just add + adc now instead of leaq, addq, cmpq, adcq

Notice how the leaq (corresponding to the "tmp" and the cmpq were removed.

Multiplications deserve the same.

Test case:

import ../src/mpint, times

let a = 42.initMpUint(128)

let b = 1000.initMpUint(128)

var c = 0.initMpUint(128)

proc carry(foo: var MpUint[128], a: MpUint[128]) =
  for _ in 0 ..< 1_000_000_000:
    foo += a


proc borrow(foo: var MpUint[128], b: MpUint[128]) =
  for _ in 0 ..< 1_000_000_000:
    foo -= a


var start = cpuTime()
carry(c, a)
var stop = cpuTime()

echo "Carry: " & $(stop - start) & "s"

start = cpuTime()
borrow(c, b)
stop = cpuTime()

echo "Borrow: " & $(stop - start) & "s"

echo c
echo (c - 1.initMpUint(128))

[mratsim]

Todo: comprensive test suite.

Due to 2-complement the borrow test for x -= y should probably be x <= not y

i.e. with a 3-bit 0..8: a - b = a + (-b) +1 => 1 - 7 = 1 + 0 + 1 = 2

Small case with uint8

let a = 1'u8
let b = 255'u8


echo "a - b: " & $(a - b)
let c = not b

echo "c: " & $c
echo "borrow: " & $(c <= not b)

echo "################"

let x = 127'u8
let y = 128'u8

echo "x - y: " & $(x - y)
let z = not y

echo "z: " & $z
echo "borrow: " & $(z <= not y)

[mratsim]

Benchmarking, the new substraction code seems consistently 10% slower than Addition.

Also Clang manage the carry with xorl, cmpq, setbe, subq instead of just sbb.

10% less perf for truly portable code seems perfectly acceptable (provided the new version passes the future comprehensive test suite).

Previous ASM with a tmp. Notice how much time is spent on leaq (loading the value in register)

New version is spending time doing actual computation, xor, cmpq, setbe have negligible cost.

Furthermore, compiling with march=native brings more than 100% speed increase on both addition and substraction as GCC is vectorizing the loop and there are no vectorized ADC/SBB so we should not go down to assembly to leave the opportunity to vectorize code to the compiler (AVX2 on x86-64 or Neon on ARM)

Addition

Substraction

[mratsim]

Latest change from the code.

Previously:

proc `-=`*(x: var MpUintImpl, y: MpUintImpl) {.noSideEffect, inline.}=
  type SubTy = type x.lo
  let original = x.lo
  x.lo -= y.lo
  x.hi -= (original < x.lo).toSubtype(SubTy) + y.hi

x86_64:

AVX2:

New:

proc `-=`*(x: var MpUintImpl, y: MpUintImpl) {.noSideEffect, inline.}=
  type SubTy = type x.lo
  x.hi -= (x.lo < y.lo).toSubtype(SubTy) + y.hi
  x.lo -= y.lo

x86_64:

AVX2:

Notice how the generated AVX 2 code is shorter.

For reference instruction altency of LEAQ vs ADDQ: http://www.agner.org/optimize/instruction_tables.pdf