Re: How to include "wide int" in code

["colinb2 ." <colinb2 at gmail dot com>]

On 7/12/18, U.Mutlu <um@mutluit.com> wrote:
> Ok, thx, got it now.
>
> So, you have an improved algorithm that could replace a slower one in gcc.
> It's this function in gcc_src/gcc/expmed.c :
>
> unsigned HOST_WIDE_INT
> choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision,
>                     unsigned HOST_WIDE_INT *multiplier_ptr,
>                     int *post_shift_ptr, int *lgup_ptr)
>
> The question is: have you tested it in practice? Ie. replacing the one
> in your local gcc source and building the new compiler and running the
> testsuite tests ("make -j -k check" etc).
I tested a previous version using the "hook" idea we've discussed, and
previous versions (the latest one is now a little different) matched
choose_multiplier, but were substantially faster. I even found a small
insignificant bug in the current choose_multiplier! (See below.)

> Or asked differently: what is the current status? Does it just need
> to be implemented (added to repo), or is your improvement still open
> for some discussion/debate and still needs some stress-testing by the
> people to show that it's indeed better?
I think it's almost ready to be implemented: it matches the output of magicu2
in a table of values in "Hacker's Delight". Because I'm having trouble using
GCC make what I'm going to do is test it exhaustively against the code
in "Hacker's Delight". Once it passes that (I think it will, but one can never
be sure with computer code?), I'd say that in my opinion it was ready to be
implemented (added to repo). I'm also confident that my general view that using
"wide int" is to be avoided as much as possible is correct, if only for speed.
(There is also the question of why use "wide int" if you don't need to?)

That said, some stress testing is needed, specifically:
* I can reduce using "wide int" to one call in choose_multiplier_v2;
* what's in question is whether it is significantly faster to use "wide int"
for that one call instead of eliminating using "wide int" altogether; this
latter is an alternate of choose_multiplier_v2, and choose_multiplier_v4.
That's what I wanted to benchmark, and what I was able to benchmark for myself
earlier this year, but apparently I can't now do that for myself. :-(

> Usually people submit a patch file (ie. a diff file) in the mailing list
> gcc-patches (s. https://gcc.gnu.org/lists.html ), so that others can
> automatically (by applying the patch) import the code into their local
> gcc source, review, rebuild the compiler and run the tests in the
> testsuite.
> Afterwards, if the tests are positive, one of the admins (s. MAINTAINERS
> file) needs to approve the patch to be checked-in into the repository.

This is where it gets tricky: I might find it difficult to do that. I am
confident that I have as good an understanding as anyone of the theory behind
how choose_multiplier works (or could work), and of how to actually implement
better ways to do that. What I have zero confidence about is whether I am
capable of submitting a patch in the way you suggest. When I reported the bug
I just quoted the line that had the bug together with the fix. (The bug was
using ">=" instead of the correct ">"; this only made a difference for a divisor
for which choose_multiplier was never called, so it only made a cosmetic
difference; however a maintainer changed the code to the correct ">".)

> So, as I'm not one of the MAINTAINERS myself yet, I would suggest that
> you should be clear about these procedures, and perhaps contact a
> MAINTAINER directly, or at least one of the developers who has worked
> on the said file(s) (expmed.c etc) and its functions; ie. do some
> (re)search in the mailing list archives, and maybe also in the bug
> tracking database at https://gcc.gnu.org/bugzilla/
All of these are helpful suggestions. Thank you.

> As can be seen: a better/faster algorithm alone is not sufficient enough;
> it must also be peer-reviewed, discussed, rigourosly tested, and hopefully
> finally get approval.
Sure: something that currently works is by definition preferable to something
that might or might not have advantages but will require all that you say.
In the (almost) words of the British businessman John Harvey-Jones: "The best
can be the enemy of the good." I think that's a judgment for the maintainers:
in my opinion my code is (almost) as clear as the existing choose_multiplier
but is substantially faster. But as a (I think) maintainer observed to me
after I found an insignificant bug in choose_multiplier
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86380
optimizing integer division by a constant divisor doesn't show up as a high
priority on profiles of GCC.

> Last but not least: all contributions must also conform to some
> Coding Standards, see details under "Contributing to GCC" at
> https://gcc.gnu.org/contribute.html
I used as my model the existing choose_multiplier, so possibly excepting one or
two lines, my replacement should fit in with the coding standards.

> --
> U.Mutlu

Thank you again for your kind assistance.