Remove DoubleLimb abstraction in favor of overflow builtins about zig-bn HOT 5 CLOSED

It might be worth double checking to make sure that it would actually be a performance win to do so. I probably don't know what I'm talking about, but I've heard stories of things like SIMD being a surefire performance boost until it's tested and it turns out cache misses were the bottleneck all along. But i like the idea of using the biggest primitives possible just on principle, even if the performance boost is negligible.

from zig-bn.

Definitely right in that profiling would be beneficial to actually determine the improvement.

As some consolation GMP seems to be using the native word size in their code so I would expect it has some worthwhile benefits.

https://github.com/omco/gmp/blob/f7a8037df5b01f4e40a9d2e71ab6fdda749a7df9/mpn/x86_64/gmp-mparam.h

from zig-bn.

I've implemented an initial version here 7bdf5a3.

There is a minor performance improvement on add -> sub ~10% improvement simply on using the overflow on a 32-bit limb. However, the real gain is had when we now switch to 64-bit limbs where we get the expected doubled performance improvement!

This is really impressive. Given that we are only 2x slower than gmp without any assembly is a really good result. Over twice as fast as a native rust version using the same algorithm. Who needs assembly, right?

Will need to do #4 before I switch the limb size formally but it should compile out of the box as is, simply using 128-bit integers for any existing double limbs requirements (will be needed in lldivN).

------ fibonacci (lladd, llsub) 
fib-zig: 0:00.34 real, 0.34 user, 0.00 sys
  debug: 0:01.93 real, 1.92 user, 0.00 sys

fib-c:   0:00.17 real, 0.17 user, 0.00 sys

fib-go:  0:00.20 real, 0.20 user, 0.00 sys

fib-py:  0:00.75 real, 0.74 user, 0.00 sys

fib-rs:  0:00.81 real, 0.80 user, 0.00 sys

from zig-bn.

We'll still keep the DoubleLimb abstraction where required (mul and probably in div, too). This isn't too bad since we have arbitrary fixed integer types provided by LLVM so any word-size will still work and the generated code is likely to be as good as we would write otherwise.

from zig-bn.

Wow! This is exciting.

from zig-bn.