math/big: better multiply primitives

[griesemer]

Suggestions from Torbjörn Granlund (personal e-mail):

"
The multiply primitives, in particular addMulVVW surely deserves more
attention:

Offset the pointers so that you can index with a counter register
which goes from -n to 0, saving the CMPQ.

Unroll. You can save most of the ADCQ $0, R that way. Basically,
do one run with just MULQ where you sum the old highpart (DX) with
the new lowpart (AX). You will need some MOVQ to move DX
out-of-the-way too. Then do a new run over these sums where you
bring in the memory addend. This should double the speed on some
newer CPUs.

A good addMulVVW is probably really the first thing to write in
assembly; addition and subtraction is much less important, usually.
"

[vielmetti]

See also https://go-review.googlesource.com/c/go/+/76270 (for arm64) where it is reported:

The lack of proper addMulVVW implementation for arm64 hurts RSA
performance

This is an optimized implementation, it improves RSA2048 performance
by 10X to 15X on ARMv8 based server processors.

[odeke-em]

/cc @ericlagergren

[griesemer]

Pushing to next release. There are some discussions about other math/bits primitive operations; maybe we can write some of this code in Go rather than assembly at some point.

[andig]

Has this potentially been solved by https://go-review.googlesource.com/c/go/+/74851/ mentioned in #20058 (comment)?

Sorry if OT, I was researching around Go performance topics and stumbled here.

[griesemer]

I believe this was for ARMv8; there's more to do here. The Go team is pre-occupied with generics for 1.18, so this is unlikely to happen for 1.18 unless somebody else wants to step in, preferably with experience in performance-critical arithmetic routines.

[andig]

I believe this was for ARMv8; there's more to do here

CL mentioned is after issue was raised, fixes amd64 and has been merged ;)

[griesemer]

Indeed, I misread, my apologies. So what's left to do is porting this to other architectures?

[andig]

I read the issue as related to x86. addMulVVW as such already has special cases for amd64 and arm64 afaikt.