Improved binvert algorithm

[marco.bodrato at tutanota.com]

Ciao,

2 lug 2026, 10:48 da tg at gmplib.org:

> Niels Möller <nisse at lysator.liu.se> writes:
>
>  E.g., the decade old Intel Atom processors seem to lack mul pipelining
>  (if I read https://gmplib.org/~tege/x86-timing.pdf correctly, 18
>  cycles). Looks like there's at least one atom machine, "glm", in the gmp
>  farm that could be used to test performance. Any other examples?
>
I have an Atom:
$ ./config.guess
atom-pc-linux-gnu
$ cat /proc/cpuinfo |grep name|head -n 1
model name      : Intel(R) Atom(TM) CPU N570   @ 1.66GHz

In 2022 I wrote some lines of code to be added into tune/modlinv.c,
I also wrote a binvert_limb_pipe somehow similar to what David proposes.
So, I changed binvert_limb_pipe to the new proposal and I pushed the patch.
On that atom processor I get$ build/tune/speed -c -r -s1 -p1000000000 binvert_limb binvert_limb_sec binvert_limb_pipe binvert_limb_uintfast
overhead 8.05 cycles, precision 1000000000 units of 6.52e-10 secs, CPU freq 1534.49 MHz
         binvert_limb binvert_limb_sec binvert_limb_pipe binvert_limb_uintfast
1              108.62        0.8056        1.2223       #0.7040

This means that on that CPU, the new sequence is slower (time+22%) than the current,
the fastest option (-30%) is the current, but using initially UHWtype instead of mp_limb_t.The _sec_ option (with fewer multiplications) is reasonably fast
because of the use of UHWtype there too.

On a low end ARM64 processor I have
$ ./config.guess 
armcortexa53-unknown-linux-gnu
$ cat /proc/cpuinfo|grep -E Hardware\|Processor
Processor       : AArch64 Processor rev 4 (aarch64)
Hardware        : sun50iw1p1

$ tune/speed -r -s1 -p100000000 binvert_limb binvert_limb_sec binvert_limb_pipe binvert_limb_uintfast
overhead 0.000000007 secs, precision 100000000 units of 1.00e-09 secs, CPU freq unknown
         binvert_limb binvert_limb_sec binvert_limb_pipe binvert_limb_uintfast
1         0.000000031        1.0277        1.1353       #0.8056

But on my (quite old anyway) laptop, the proposed sequence is the fastest.
$ build/tune/speed -r -c -s1 -p1000000000 binvert_limb binvert_limb_sec binvert_limb_pipe binvert_limb_uintfast
overhead 5.26 cycles, precision 1000000000 units of 5.28e-10 secs, CPU freq 1895.52 MHz
         binvert_limb binvert_limb_sec binvert_limb_pipe binvert_limb_uintfast
1               29.25        1.0809       #0.6998        0.9984

and on shell too:
$ /var/tmp/bodrato/gmp/hg/build/tune/speed -r -c -s1 -p1000000000 binvert_limb binvert_limb_sec binvert_limb_pipe binvert_limb_uintfast
overhead 4.87 cycles, precision 1000000000 units of 2.86e-10 secs, CPU freq 3500.17 MHz
         binvert_limb binvert_limb_sec binvert_limb_pipe binvert_limb_uintfast
1               28.39        1.0919       #0.6940        1.0000
 
Anyway, it seems like a good idea to get rid of the table
Ĝis,m