From: Sam James <sam@gentoo.org>
To: Stephen Face <shpface@gmail.com>
Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] libstdc++: Optimize std::gcd
Date: Fri, 07 Jun 2024 09:57:01 +0100 [thread overview]
Message-ID: <87wmn1m8pu.fsf@gentoo.org> (raw)
In-Reply-To: <9e5636e8-224f-4dde-9c60-489b4aad6534@gmail.com> (Stephen Face's message of "Thu, 6 Jun 2024 22:29:23 -0700")
Stephen Face <shpface@gmail.com> writes:
> This patch is to optimize the runtime execution of gcd. Mathematically,
> it computes with the same algorithm as before, but subtractions and
> branches are rearranged to encourage generation of code that can use
> flags from the subtractions for conditional moves. Additionally, most
> pairs of integers are coprime, so this patch also includes a check for
> one of the integers to be equal to 1, and then it will exit the loop
> early in this case.
Is it worth filing a bug for the missed optimisation? You shouldn't have
to write things in a specific order. Thanks.
>
> libstdc++-v3/ChangeLog:
>
> * include/std/numeric(__gcd): Optimize.
> ---
> I have tested this on x86_64-linux and aarch64-linux. I have tested the
> timing with random distributions of small inputs and large inputs on a
> couple of machines with -O2 and found decreases in execution time from
> 20% to 60% depending on the machine and distribution of inputs.
>
> libstdc++-v3/include/std/numeric | 21 +++++++++++----------
> 1 file changed, 11 insertions(+), 10 deletions(-)
>
> diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric
> index c912db4a519..3c9e8387a0e 100644
> --- a/libstdc++-v3/include/std/numeric
> +++ b/libstdc++-v3/include/std/numeric
> @@ -148,19 +148,20 @@ namespace __detail
>
> while (true)
> {
> - if (__m > __n)
> - {
> - _Tp __tmp = __m;
> - __m = __n;
> - __n = __tmp;
> - }
> + _Tp __m_minus_n = __m - __n;
> + if (__m_minus_n == 0)
> + return __m << __k;
>
> - __n -= __m;
> + _Tp __next_m = __m < __n ? __m : __n;
>
> - if (__n == 0)
> - return __m << __k;
> + if (__next_m == 1)
> + return __next_m << __k;
> +
> + _Tp __n_minus_m = __n - __m;
> + __n = __n < __m ? __m_minus_n : __n_minus_m;
> + __m = __next_m;
>
> - __n >>= std::__countr_zero(__n);
> + __n >>= std::__countr_zero(__m_minus_n);
> }
> }
> } // namespace __detail
next prev parent reply other threads:[~2024-06-07 8:57 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-06-07 5:29 Stephen Face
2024-06-07 8:57 ` Sam James [this message]
2024-06-07 9:30 ` Jonathan Wakely
2024-06-07 18:42 ` Stephen Face
2024-06-07 18:48 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87wmn1m8pu.fsf@gentoo.org \
--to=sam@gentoo.org \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
--cc=shpface@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).