Making GNU GCC choose_multiplier in expmed.c significantly faster

[colinb2 .]

Feel free to copy this email and attachment to anyone who might be interested.
I'm very happy to answer any questions anyone has.
The program can be compiled and run like this on Linux with GNU GCC:
gcc -O2 -o expmed2.exe expmed2.c
./expmed2.exe

This email deals with making part of the GNU GCC compiler - integer division
by a constant divisor - faster. (The calculation of the parameters for the
machine code will be faster; compiled programs won't run faster.)
Further down I mention inequality (1) which can be used to make the LLVM
compiler somewhat faster, because that currently uses code based on (2).
I don't know what - if anything - the Java JVM uses for this, or how other
compilers do this, but these ideas may be useful there.

By significantly faster I mean I have benchmarked alternative versions of
choose_multiplier which on my low specification netbook can take maybe less than
half the time the current version takes. Time saved in compilation is much less
important than time saved in running compiled programs, but the code for the
faster versions is about the same length as the code for the current version,
and is only a bit more complicated, so is worth considering?

A short summary of the following is that choose_multiplier currently uses an
elegant algorithm due to Granlund & Montgomery, but which as implemented seems
rather slow. We can make it faster while retaining the basic structure, and
using a different, mostly equivalent, algorithm, may be a bit faster than that.

Licencing: in Fractint people's words "Don't want money, want recognition!"
The version choose_multiplier_v2 is based - but improves - on what's in
the GCC choose_multiplier function in file expmed.c, so the GCC licence.
The version choose_multiplier_v4 is based - but improves - on magicu2 in
"Hacker's Delight", so the licence is you needn't acknowledge the source
but it would be nice to credit the code as from
magicu2 in "Hacker's Delight" by Henry S Warren http://hackersdelight.org
with improvements by Colin Bartlett <colinb2@gmail.com>.
This latter also applies to choose_multiplier_power2_divrem because that
is also an obvious (?) idea from magicu2 in "Hacker's Delight".  */

The idea is using "wide int" seems slow compared to "unsigned HOST_WIDE_INT",
so it makes sense to avoid using "wide int" as much as possible. We can easily
rewrite choose_multiplier to only use "wide int" to calculate the initial mlow;
this is choose_multiplier_v2. An alternative for choose_multiplier_v2 completely
avoids using "wide int" by iterating upwards for the initial mlow, but if that
benchmarks as faster than using "wide int" even once (I suspect it might) then
just iterating upwards may even be a bit faster; this is choose_multiplier_v4.

The attachment is self-contained, and I have checked that the values produced
agree with a "Hacker's Delight" table of M/2^s for small d and n=precision=32.

What follows is a short summary of the theory, applying it to choose_multiplier.

Problem: find M/2^s so that for 0<=i<=iMax>=d we have floor(i/d)=floor(i*M/2^s).
Let qc=floor((iMax+1)/d); nc=qc*d-1; lgup=ceiling(log2(d)).
Given s let M=floor(2^s/d)+1; delta=M*d-2^s.

For GCC choose_multiplier:

* equivalent necessary & sufficient conditions:
(1) 0<delta and qc*delta<M
(2) 0<delta and nc*delta<2^s
Proof of (1) if and only if (2):
qc*delta*d-delta=nc*delta<2^s==M*d-delta
(3) 1/d<M/2^s<(1+1/nc)*1/d

* equivalent sufficient conditions: we have nc<2^precision, so:
(4) 0<delta and 2^precision*delta<=2^s
(4.1) 0<delta and delta<=2^(s-precision)
(5) 1/d<M/2^s<=(1+1/2^precision)*1/d
(5.1) 2^s/d<M<=(2^s+2^(s-precision))/d

(1) seems to be new to the literature, but is equivalent to (2) which is in
"Hacker's Delight" (Chapter 10) by Henry S Warren. Both give upwards iterating
algorithms which give minimal M/2^s and which avoid needing to use "wide int",
but the algorithm code using (1) is simpler and faster than that using (2).

(4.1) is in "Hacker's Delight". It gives an upwards iterating algorithm which
avoids using "wide int", and the algorithm code is a bit simpler than using (1).
Mostly it gives the same result as GCC choose_multiplier which implements
(possibly slowly because it uses "wide int") the elegant algorithm due to
Granlund & Montgomery. (Which perhaps builds on work by Alverson.)

We can prove if iMax<2^precision then for 0<=i<2^(precision/2) inequality (4)
etc give the same M/2^s as inequality (1) etc. For n=precision=32
the smallest d for which (4) gives a non-minimal M is d=102807.

Rough not necessarily reliable statistics suggest that using (4) etc
we have that if n=precision the average post_shift=lgup-1.

So if we can *quickly" calculate M/2^s at s=n+lgup-1, then either that fails
and we need to use an extra "top" bit for M and use post_shift=lgup,
or it works and we can try reducing M.

The catch is *if* we can *quickly* calculate M/2^s at s=n+lgup-1;
it's easy to directly calculate M/2^s at that s using "wide int", but using
"wide int" seems slow, and it might actually be faster to iterate upwards
from s=n and completely avoid using "wide int".

In any case "wide int" seems slow compared with using "unsigned HOST_WIDE_INT",
so it makes sense to avoid "wide int" as far as possible.

So in the attachment choose_multiplier_v2 rewrites choose_multiplier to:
(a) only use "wide int" to calculate the initial mlow at s=n+lgup-1;
    all other calculations are made using "unsigned HOST_WIDE_INT";
or (b) avoid using "wide int" to calculate the initial mlow at s=n+lgup-1,
       by iterating upwards from s=n to find the initial mlow.
But if (b) benchmarks as faster than (a), which I suspect might be the case,
then it may even be on average a bit faster to use choose_multiplier_v4 which
iterates upwards to find M/2^s, and which would avoid needing to calculate lgup
unless that is useful as a return value of choose_multiplier.

Colin Bartlett
-------------- next part --------------
A non-text attachment was scrubbed...
Name: expmed2.c
Type: text/x-csrc
Size: 8948 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20180710/d682c0a9/attachment.bin>