[committed] libstdc++: Optimise GCD algorithms

[committed] libstdc++: Optimise GCD algorithms

[Sidney Marshall]

Jonathan

I don't know if the following comments are useful or not but here goes:


>The current std::gcd and std::chrono::duration::_S_gcd algorithms are
>both recursive. This is potentially expensive to evaluate in constant
>expressions, because each level of recursion makes a new copy of the
>function to evaluate. The maximum number of steps is bounded
>(proportional to the number of decimal digits in the smaller value) and
>so unlikely to exceed the limit for constexpr nesting, but the memory
>usage is still suboptimal. By using an iterative algorithm we avoid
>that compile-time cost. Because looping in constexpr functions is not
>allowed until C++14, we need to keep the recursive implementation in
>duration::_S_gcd for C++11 mode.
>
>For std::gcd we can also optimise runtime performance by using the
>binary GCD algorithm.
>
>libstdc++-v3/ChangeLog:
>
>         * include/std/chrono (duration::_S_gcd): Use iterative algorithm
>         for C++14 and later.
>         * include/std/numeric (__detail::__gcd): Replace recursive
>         Euclidean algorithm with iterative version of binary GCD algorithm.
>         * testsuite/26_numerics/gcd/1.cc: Test additional inputs.
>         * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
>         * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
>         * testsuite/experimental/numeric/gcd.cc: Test additional inputs.
>         * testsuite/26_numerics/gcd/2.cc: New test.
>
>Tested powerpc64le-linux. Committed to trunk.
>
>-------------- next part --------------
>commit 3c219134152f645103f2fcd50735b177ccd76cde
>Author: Jonathan Wakely <jwakely@redhat.com>
>Date:   Thu Sep 3 12:38:50 2020
>
>     libstdc++: Optimise GCD algorithms
>
>     The current std::gcd and std::chrono::duration::_S_gcd algorithms are
>     both recursive. This is potentially expensive to evaluate in constant
>     expressions, because each level of recursion makes a new copy of the
>     function to evaluate. The maximum number of steps is bounded
>     (proportional to the number of decimal digits in the smaller value) and
>     so unlikely to exceed the limit for constexpr nesting, but the memory
>     usage is still suboptimal. By using an iterative algorithm we avoid
>     that compile-time cost. Because looping in constexpr functions is not
>     allowed until C++14, we need to keep the recursive implementation in
>     duration::_S_gcd for C++11 mode.
>
>     For std::gcd we can also optimise runtime performance by using the
>     binary GCD algorithm.
>
>     libstdc++-v3/ChangeLog:
>
>             * include/std/chrono (duration::_S_gcd): Use iterative algorithm
>             for C++14 and later.
>             * include/std/numeric (__detail::__gcd): Replace recursive
>             Euclidean algorithm with iterative version of binary 
> GCD algorithm.
>             * testsuite/26_numerics/gcd/1.cc: Test additional inputs.
>             * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
>             * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
>             * testsuite/experimental/numeric/gcd.cc: Test additional inputs.
>             * testsuite/26_numerics/gcd/2.cc: New test.
>
>diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
>index 1682263fd9f..0e2efb2522b 100644
>--- a/libstdc++-v3/include/std/chrono
>+++ b/libstdc++-v3/include/std/chrono
>@@ -428,8 +428,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>         _S_gcd(intmax_t __m, intmax_t __n) noexcept
>         {
>           // Duration only allows positive periods so we don't need to
>-         // support negative values here (unlike __static_gcd and std::gcd).
>+         // handle negative values here (unlike __static_gcd and std::gcd).
>+#if __cplusplus >= 201402L
>+         while (__m != 0 && __n != 0)

Why are you testing for both __m != 0 && __n != 0 in the loop. Only 
__n can be zero. A test for __m == 0 can be made out side of the loop 
to save a possible division. Or is there something special about 
compile time execution?

>+           {
>+             intmax_t __rem = __m % __n;
>+             __m = __n;
>+             __n = __rem;
>+           }
>+         return __m + __n;

If __n is zero then why not just return __m? Or, again, is there 
something special about compile time execution?

>+#else
>+         // C++11 doesn't allow loops in constexpr functions, but this
>+         // recursive version can be more expensive to evaluate.
>           return (__m == 0) ? __n : (__n == 0) ? __m : _S_gcd(__n, 
> __m % __n);
>+#endif
>         }
>
>...

Re: [committed] libstdc++: Optimise GCD algorithms

[Jonathan Wakely]

On Sat, 5 Sep 2020 at 01:35, Sidney Marshall <sidneym@frontiernet.net> wrote:
>
> Jonathan
>
> I don't know if the following comments are useful or not but here goes:

Reviews of my patches are always welcome, thanks.


> >The current std::gcd and std::chrono::duration::_S_gcd algorithms are
> >both recursive. This is potentially expensive to evaluate in constant
> >expressions, because each level of recursion makes a new copy of the
> >function to evaluate. The maximum number of steps is bounded
> >(proportional to the number of decimal digits in the smaller value) and
> >so unlikely to exceed the limit for constexpr nesting, but the memory
> >usage is still suboptimal. By using an iterative algorithm we avoid
> >that compile-time cost. Because looping in constexpr functions is not
> >allowed until C++14, we need to keep the recursive implementation in
> >duration::_S_gcd for C++11 mode.
> >
> >For std::gcd we can also optimise runtime performance by using the
> >binary GCD algorithm.
> >
> >libstdc++-v3/ChangeLog:
> >
> >         * include/std/chrono (duration::_S_gcd): Use iterative algorithm
> >         for C++14 and later.
> >         * include/std/numeric (__detail::__gcd): Replace recursive
> >         Euclidean algorithm with iterative version of binary GCD algorithm.
> >         * testsuite/26_numerics/gcd/1.cc: Test additional inputs.
> >         * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
> >         * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
> >         * testsuite/experimental/numeric/gcd.cc: Test additional inputs.
> >         * testsuite/26_numerics/gcd/2.cc: New test.
> >
> >Tested powerpc64le-linux. Committed to trunk.
> >
> >-------------- next part --------------
> >commit 3c219134152f645103f2fcd50735b177ccd76cde
> >Author: Jonathan Wakely <jwakely@redhat.com>
> >Date:   Thu Sep 3 12:38:50 2020
> >
> >     libstdc++: Optimise GCD algorithms
> >
> >     The current std::gcd and std::chrono::duration::_S_gcd algorithms are
> >     both recursive. This is potentially expensive to evaluate in constant
> >     expressions, because each level of recursion makes a new copy of the
> >     function to evaluate. The maximum number of steps is bounded
> >     (proportional to the number of decimal digits in the smaller value) and
> >     so unlikely to exceed the limit for constexpr nesting, but the memory
> >     usage is still suboptimal. By using an iterative algorithm we avoid
> >     that compile-time cost. Because looping in constexpr functions is not
> >     allowed until C++14, we need to keep the recursive implementation in
> >     duration::_S_gcd for C++11 mode.
> >
> >     For std::gcd we can also optimise runtime performance by using the
> >     binary GCD algorithm.
> >
> >     libstdc++-v3/ChangeLog:
> >
> >             * include/std/chrono (duration::_S_gcd): Use iterative algorithm
> >             for C++14 and later.
> >             * include/std/numeric (__detail::__gcd): Replace recursive
> >             Euclidean algorithm with iterative version of binary
> > GCD algorithm.
> >             * testsuite/26_numerics/gcd/1.cc: Test additional inputs.
> >             * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
> >             * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
> >             * testsuite/experimental/numeric/gcd.cc: Test additional inputs.
> >             * testsuite/26_numerics/gcd/2.cc: New test.
> >
> >diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
> >index 1682263fd9f..0e2efb2522b 100644
> >--- a/libstdc++-v3/include/std/chrono
> >+++ b/libstdc++-v3/include/std/chrono
> >@@ -428,8 +428,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >         _S_gcd(intmax_t __m, intmax_t __n) noexcept
> >         {
> >           // Duration only allows positive periods so we don't need to
> >-         // support negative values here (unlike __static_gcd and std::gcd).
> >+         // handle negative values here (unlike __static_gcd and std::gcd).
> >+#if __cplusplus >= 201402L
> >+         while (__m != 0 && __n != 0)
>
> Why are you testing for both __m != 0 && __n != 0 in the loop. Only
> __n can be zero. A test for __m == 0 can be made out side of the loop
> to save a possible division. Or is there something special about
> compile time execution?

It was adapted (maybe too hastily) from the general purpose std::gcd
function, which does need to handle zeros. I didn't consider how to
improve it using extra knowledge about non-zero inputs (I only
considered that they can't be negative).

Neither value can be zero initially (duration only allows positive
ratios, and ratio doesn't allow zero denominators) so I suppose it
could be:

      do
        {
          intmax_t __rem = __m % __n;
          __m = __n;
          __n = __rem;
        } while (__n != 0)
      return __m;



> >+           {
> >+             intmax_t __rem = __m % __n;
> >+             __m = __n;
> >+             __n = __rem;
> >+           }
> >+         return __m + __n;
>
> If __n is zero then why not just return __m? Or, again, is there
> something special about compile time execution?

If n is zero it *does* just return m, because m+n is zero. The loop
exits when one or both is zero, so m+n returns whichever is non-zero
(if any).

I wasn't considered that the loop can only exit when m is zero.

Re: [committed] libstdc++: Optimise GCD algorithms

[Jonathan Wakely]

On Sat, 5 Sep 2020 at 09:34, Jonathan Wakely wrote:
>
> On Sat, 5 Sep 2020 at 01:35, Sidney Marshall <sidneym@frontiernet.net> wrote:
> >
> > Jonathan
> >
> > I don't know if the following comments are useful or not but here goes:
>
> Reviews of my patches are always welcome, thanks.
>
>
> > >The current std::gcd and std::chrono::duration::_S_gcd algorithms are
> > >both recursive. This is potentially expensive to evaluate in constant
> > >expressions, because each level of recursion makes a new copy of the
> > >function to evaluate. The maximum number of steps is bounded
> > >(proportional to the number of decimal digits in the smaller value) and
> > >so unlikely to exceed the limit for constexpr nesting, but the memory
> > >usage is still suboptimal. By using an iterative algorithm we avoid
> > >that compile-time cost. Because looping in constexpr functions is not
> > >allowed until C++14, we need to keep the recursive implementation in
> > >duration::_S_gcd for C++11 mode.
> > >
> > >For std::gcd we can also optimise runtime performance by using the
> > >binary GCD algorithm.
> > >
> > >libstdc++-v3/ChangeLog:
> > >
> > >         * include/std/chrono (duration::_S_gcd): Use iterative algorithm
> > >         for C++14 and later.
> > >         * include/std/numeric (__detail::__gcd): Replace recursive
> > >         Euclidean algorithm with iterative version of binary GCD algorithm.
> > >         * testsuite/26_numerics/gcd/1.cc: Test additional inputs.
> > >         * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
> > >         * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
> > >         * testsuite/experimental/numeric/gcd.cc: Test additional inputs.
> > >         * testsuite/26_numerics/gcd/2.cc: New test.
> > >
> > >Tested powerpc64le-linux. Committed to trunk.
> > >
> > >-------------- next part --------------
> > >commit 3c219134152f645103f2fcd50735b177ccd76cde
> > >Author: Jonathan Wakely <jwakely@redhat.com>
> > >Date:   Thu Sep 3 12:38:50 2020
> > >
> > >     libstdc++: Optimise GCD algorithms
> > >
> > >     The current std::gcd and std::chrono::duration::_S_gcd algorithms are
> > >     both recursive. This is potentially expensive to evaluate in constant
> > >     expressions, because each level of recursion makes a new copy of the
> > >     function to evaluate. The maximum number of steps is bounded
> > >     (proportional to the number of decimal digits in the smaller value) and
> > >     so unlikely to exceed the limit for constexpr nesting, but the memory
> > >     usage is still suboptimal. By using an iterative algorithm we avoid
> > >     that compile-time cost. Because looping in constexpr functions is not
> > >     allowed until C++14, we need to keep the recursive implementation in
> > >     duration::_S_gcd for C++11 mode.
> > >
> > >     For std::gcd we can also optimise runtime performance by using the
> > >     binary GCD algorithm.
> > >
> > >     libstdc++-v3/ChangeLog:
> > >
> > >             * include/std/chrono (duration::_S_gcd): Use iterative algorithm
> > >             for C++14 and later.
> > >             * include/std/numeric (__detail::__gcd): Replace recursive
> > >             Euclidean algorithm with iterative version of binary
> > > GCD algorithm.
> > >             * testsuite/26_numerics/gcd/1.cc: Test additional inputs.
> > >             * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
> > >             * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
> > >             * testsuite/experimental/numeric/gcd.cc: Test additional inputs.
> > >             * testsuite/26_numerics/gcd/2.cc: New test.
> > >
> > >diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
> > >index 1682263fd9f..0e2efb2522b 100644
> > >--- a/libstdc++-v3/include/std/chrono
> > >+++ b/libstdc++-v3/include/std/chrono
> > >@@ -428,8 +428,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > >         _S_gcd(intmax_t __m, intmax_t __n) noexcept
> > >         {
> > >           // Duration only allows positive periods so we don't need to
> > >-         // support negative values here (unlike __static_gcd and std::gcd).
> > >+         // handle negative values here (unlike __static_gcd and std::gcd).
> > >+#if __cplusplus >= 201402L
> > >+         while (__m != 0 && __n != 0)
> >
> > Why are you testing for both __m != 0 && __n != 0 in the loop. Only
> > __n can be zero. A test for __m == 0 can be made out side of the loop
> > to save a possible division. Or is there something special about
> > compile time execution?
>
> It was adapted (maybe too hastily) from the general purpose std::gcd
> function, which does need to handle zeros. I didn't consider how to
> improve it using extra knowledge about non-zero inputs (I only
> considered that they can't be negative).
>
> Neither value can be zero initially (duration only allows positive
> ratios, and ratio doesn't allow zero denominators) so I suppose it
> could be:
>
>       do
>         {
>           intmax_t __rem = __m % __n;
>           __m = __n;
>           __n = __rem;
>         } while (__n != 0)
>       return __m;
>
>
>
> > >+           {
> > >+             intmax_t __rem = __m % __n;
> > >+             __m = __n;
> > >+             __n = __rem;
> > >+           }
> > >+         return __m + __n;
> >
> > If __n is zero then why not just return __m? Or, again, is there
> > something special about compile time execution?
>
> If n is zero it *does* just return m, because m+n is zero. The loop
> exits when one or both is zero, so m+n returns whichever is non-zero
> (if any).
>
> I wasn't considered that the loop can only exit when m is zero.

N.B. this code is not expected to last long, because my plan is to
replace the definition of std::ratio_divide with a SFINAE-friendly
one, so that we can get rid of duration::__divide and
duration::_S_gcd. The more general purpose __ratio::__gcd function
that will be used instead will need to handle zero inputs, because
std::ratio_divide<std::ratio<0,1>, std::ratio<1,1>> is valid.

Re: [committed] libstdc++: Optimise GCD algorithms

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 5699 bytes --]

On 05/09/20 09:34 +0100, Jonathan Wakely via Libstdc++ wrote:
>On Sat, 5 Sep 2020 at 01:35, Sidney Marshall <sidneym@frontiernet.net> wrote:
>>
>> Jonathan
>>
>> I don't know if the following comments are useful or not but here goes:
>
>Reviews of my patches are always welcome, thanks.
>
>
>> >The current std::gcd and std::chrono::duration::_S_gcd algorithms are
>> >both recursive. This is potentially expensive to evaluate in constant
>> >expressions, because each level of recursion makes a new copy of the
>> >function to evaluate. The maximum number of steps is bounded
>> >(proportional to the number of decimal digits in the smaller value) and
>> >so unlikely to exceed the limit for constexpr nesting, but the memory
>> >usage is still suboptimal. By using an iterative algorithm we avoid
>> >that compile-time cost. Because looping in constexpr functions is not
>> >allowed until C++14, we need to keep the recursive implementation in
>> >duration::_S_gcd for C++11 mode.
>> >
>> >For std::gcd we can also optimise runtime performance by using the
>> >binary GCD algorithm.
>> >
>> >libstdc++-v3/ChangeLog:
>> >
>> >         * include/std/chrono (duration::_S_gcd): Use iterative algorithm
>> >         for C++14 and later.
>> >         * include/std/numeric (__detail::__gcd): Replace recursive
>> >         Euclidean algorithm with iterative version of binary GCD algorithm.
>> >         * testsuite/26_numerics/gcd/1.cc: Test additional inputs.
>> >         * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
>> >         * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
>> >         * testsuite/experimental/numeric/gcd.cc: Test additional inputs.
>> >         * testsuite/26_numerics/gcd/2.cc: New test.
>> >
>> >Tested powerpc64le-linux. Committed to trunk.
>> >
>> >-------------- next part --------------
>> >commit 3c219134152f645103f2fcd50735b177ccd76cde
>> >Author: Jonathan Wakely <jwakely@redhat.com>
>> >Date:   Thu Sep 3 12:38:50 2020
>> >
>> >     libstdc++: Optimise GCD algorithms
>> >
>> >     The current std::gcd and std::chrono::duration::_S_gcd algorithms are
>> >     both recursive. This is potentially expensive to evaluate in constant
>> >     expressions, because each level of recursion makes a new copy of the
>> >     function to evaluate. The maximum number of steps is bounded
>> >     (proportional to the number of decimal digits in the smaller value) and
>> >     so unlikely to exceed the limit for constexpr nesting, but the memory
>> >     usage is still suboptimal. By using an iterative algorithm we avoid
>> >     that compile-time cost. Because looping in constexpr functions is not
>> >     allowed until C++14, we need to keep the recursive implementation in
>> >     duration::_S_gcd for C++11 mode.
>> >
>> >     For std::gcd we can also optimise runtime performance by using the
>> >     binary GCD algorithm.
>> >
>> >     libstdc++-v3/ChangeLog:
>> >
>> >             * include/std/chrono (duration::_S_gcd): Use iterative algorithm
>> >             for C++14 and later.
>> >             * include/std/numeric (__detail::__gcd): Replace recursive
>> >             Euclidean algorithm with iterative version of binary
>> > GCD algorithm.
>> >             * testsuite/26_numerics/gcd/1.cc: Test additional inputs.
>> >             * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
>> >             * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
>> >             * testsuite/experimental/numeric/gcd.cc: Test additional inputs.
>> >             * testsuite/26_numerics/gcd/2.cc: New test.
>> >
>> >diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
>> >index 1682263fd9f..0e2efb2522b 100644
>> >--- a/libstdc++-v3/include/std/chrono
>> >+++ b/libstdc++-v3/include/std/chrono
>> >@@ -428,8 +428,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>> >         _S_gcd(intmax_t __m, intmax_t __n) noexcept
>> >         {
>> >           // Duration only allows positive periods so we don't need to
>> >-         // support negative values here (unlike __static_gcd and std::gcd).
>> >+         // handle negative values here (unlike __static_gcd and std::gcd).
>> >+#if __cplusplus >= 201402L
>> >+         while (__m != 0 && __n != 0)
>>
>> Why are you testing for both __m != 0 && __n != 0 in the loop. Only
>> __n can be zero. A test for __m == 0 can be made out side of the loop
>> to save a possible division. Or is there something special about
>> compile time execution?
>
>It was adapted (maybe too hastily) from the general purpose std::gcd
>function, which does need to handle zeros. I didn't consider how to
>improve it using extra knowledge about non-zero inputs (I only
>considered that they can't be negative).
>
>Neither value can be zero initially (duration only allows positive
>ratios, and ratio doesn't allow zero denominators) so I suppose it
>could be:
>
>      do
>        {
>          intmax_t __rem = __m % __n;
>          __m = __n;
>          __n = __rem;
>        } while (__n != 0)
>      return __m;
>
>
>
>> >+           {
>> >+             intmax_t __rem = __m % __n;
>> >+             __m = __n;
>> >+             __n = __rem;
>> >+           }
>> >+         return __m + __n;
>>
>> If __n is zero then why not just return __m? Or, again, is there
>> something special about compile time execution?
>
>If n is zero it *does* just return m, because m+n is zero. The loop
>exits when one or both is zero, so m+n returns whichever is non-zero
>(if any).
>
>I wasn't considered that the loop can only exit when m is zero.

I've committed this simplification for duration::_S_gcd.

Thanks for the review and the suggestions.

Tested powerpc64le-linux, committed to trunk.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 1373 bytes --]

commit ec5096f48bbd7db83cbe94bdd3235c5808a5979a
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Sep 7 20:09:17 2020

    libstdc++: Simplify chrono::duration::_S_gcd
    
    We can simplify this constexpr function further because we know that
    period::num >= 1 and period::den >= 1 so only the remainder can ever be
    zero.
    
    libstdc++-v3/ChangeLog:
    
            * include/std/chrono (duration::_S_gcd): Use invariant that
            neither value is zero initially.

diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
index 0e2efb2522b..afee7859c6d 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -430,17 +430,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  // Duration only allows positive periods so we don't need to
 	  // handle negative values here (unlike __static_gcd and std::gcd).
 #if __cplusplus >= 201402L
-	  while (__m != 0 && __n != 0)
+	  do
 	    {
 	      intmax_t __rem = __m % __n;
 	      __m = __n;
 	      __n = __rem;
 	    }
-	  return __m + __n;
+	  while (__n != 0);
+	  return __m;
 #else
 	  // C++11 doesn't allow loops in constexpr functions, but this
 	  // recursive version can be more expensive to evaluate.
-	  return (__m == 0) ? __n : (__n == 0) ? __m : _S_gcd(__n, __m % __n);
+	  return (__n == 0) ? __m : _S_gcd(__n, __m % __n);
 #endif
 	}
 

[committed] libstdc++: Optimise GCD algorithms

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1318 bytes --]

The current std::gcd and std::chrono::duration::_S_gcd algorithms are
both recursive. This is potentially expensive to evaluate in constant
expressions, because each level of recursion makes a new copy of the
function to evaluate. The maximum number of steps is bounded
(proportional to the number of decimal digits in the smaller value) and
so unlikely to exceed the limit for constexpr nesting, but the memory
usage is still suboptimal. By using an iterative algorithm we avoid
that compile-time cost. Because looping in constexpr functions is not
allowed until C++14, we need to keep the recursive implementation in
duration::_S_gcd for C++11 mode.

For std::gcd we can also optimise runtime performance by using the
binary GCD algorithm.

libstdc++-v3/ChangeLog:

	* include/std/chrono (duration::_S_gcd): Use iterative algorithm
	for C++14 and later.
	* include/std/numeric (__detail::__gcd): Replace recursive
	Euclidean algorithm with iterative version of binary GCD algorithm.
	* testsuite/26_numerics/gcd/1.cc: Test additional inputs.
	* testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
	* testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
	* testsuite/experimental/numeric/gcd.cc: Test additional inputs.
	* testsuite/26_numerics/gcd/2.cc: New test.

Tested powerpc64le-linux. Committed to trunk.


[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 16762 bytes --]

commit 3c219134152f645103f2fcd50735b177ccd76cde
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Sep 3 12:38:50 2020

    libstdc++: Optimise GCD algorithms
    
    The current std::gcd and std::chrono::duration::_S_gcd algorithms are
    both recursive. This is potentially expensive to evaluate in constant
    expressions, because each level of recursion makes a new copy of the
    function to evaluate. The maximum number of steps is bounded
    (proportional to the number of decimal digits in the smaller value) and
    so unlikely to exceed the limit for constexpr nesting, but the memory
    usage is still suboptimal. By using an iterative algorithm we avoid
    that compile-time cost. Because looping in constexpr functions is not
    allowed until C++14, we need to keep the recursive implementation in
    duration::_S_gcd for C++11 mode.
    
    For std::gcd we can also optimise runtime performance by using the
    binary GCD algorithm.
    
    libstdc++-v3/ChangeLog:
    
            * include/std/chrono (duration::_S_gcd): Use iterative algorithm
            for C++14 and later.
            * include/std/numeric (__detail::__gcd): Replace recursive
            Euclidean algorithm with iterative version of binary GCD algorithm.
            * testsuite/26_numerics/gcd/1.cc: Test additional inputs.
            * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
            * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
            * testsuite/experimental/numeric/gcd.cc: Test additional inputs.
            * testsuite/26_numerics/gcd/2.cc: New test.

diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
index 1682263fd9f..0e2efb2522b 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -428,8 +428,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_S_gcd(intmax_t __m, intmax_t __n) noexcept
 	{
 	  // Duration only allows positive periods so we don't need to
-	  // support negative values here (unlike __static_gcd and std::gcd).
+	  // handle negative values here (unlike __static_gcd and std::gcd).
+#if __cplusplus >= 201402L
+	  while (__m != 0 && __n != 0)
+	    {
+	      intmax_t __rem = __m % __n;
+	      __m = __n;
+	      __n = __rem;
+	    }
+	  return __m + __n;
+#else
+	  // C++11 doesn't allow loops in constexpr functions, but this
+	  // recursive version can be more expensive to evaluate.
 	  return (__m == 0) ? __n : (__n == 0) ? __m : _S_gcd(__n, __m % __n);
+#endif
 	}
 
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric
index bd70a52019b..2de6aaf06ec 100644
--- a/libstdc++-v3/include/std/numeric
+++ b/libstdc++-v3/include/std/numeric
@@ -76,6 +76,7 @@
 
 #if __cplusplus >= 201402L
 #include <type_traits>
+#include <bit>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -97,15 +98,40 @@ namespace __detail
 
   template<typename _Up> void __absu(bool) = delete;
 
-  // GCD implementation
+  // GCD implementation, using Stein's algorithm
   template<typename _Tp>
     constexpr _Tp
     __gcd(_Tp __m, _Tp __n)
     {
       static_assert(is_unsigned<_Tp>::value, "type must be unsigned");
-      return __m == 0 ? __n
-	: __n == 0 ? __m
-	: __detail::__gcd(__n, _Tp(__m % __n));
+
+      if (__m == 0)
+	return __n;
+      if (__n == 0)
+	return __m;
+
+      const int __i = std::__countr_zero(__m);
+      __m >>= __i;
+      const int __j = std::__countr_zero(__n);
+      __n >>= __j;
+      const int __k = __i < __j ? __i : __j; // min(i, j)
+
+      while (true)
+	{
+	  if (__m > __n)
+	    {
+	      _Tp __tmp = __m;
+	      __m = __n;
+	      __n = __tmp;
+	    }
+
+	  __n -= __m;
+
+	  if (__n == 0)
+	    return __m << __k;
+
+	  __n >>= std::__countr_zero(__n);
+	}
     }
 
   // LCM implementation
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/1.cc b/libstdc++-v3/testsuite/26_numerics/gcd/1.cc
index 042f0a9e2f0..dc43cda395c 100644
--- a/libstdc++-v3/testsuite/26_numerics/gcd/1.cc
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/1.cc
@@ -15,7 +15,6 @@
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-// { dg-options "-std=gnu++17" }
 // { dg-do compile { target c++17 } }
 
 #include <numeric>
@@ -27,6 +26,7 @@
 #endif
 
 using std::gcd;
+using std::is_same_v;
 
 static_assert( gcd(1071, 462) == 21, "" );
 static_assert( gcd(2000, 20) == 20, "" );
@@ -34,11 +34,20 @@ static_assert( gcd(2011, 17) == 1, "GCD of two primes is 1" );
 static_assert( gcd(200, 200) == 200, "GCD of equal numbers is that number" );
 static_assert( gcd(0, 13) == 13, "GCD of any number and 0 is that number" );
 static_assert( gcd(29, 0) == 29, "GCD of any number and 0 is that number" );
-static_assert( gcd(0, 0) == 0, "" );
+static_assert( gcd(0, 0) == 0, "Zarro Boogs found" );
 
 static_assert(gcd(1u, 2) == 1, "unsigned and signed");
+static_assert(gcd(9, 6u) == 3, "unsigned and signed");
 static_assert(gcd(3, 4u) == 1, "signed and unsigned");
+static_assert(gcd(32u, 24) == 8, "signed and unsigned");
+static_assert(gcd(1u, -2) == 1, "unsigned and negative");
+static_assert(gcd(-21, 28u) == 7, "unsigned and negative");
+static_assert(gcd(-3, 4u) == 1, "negative and unsigned");
+static_assert(gcd(33u, -44) == 11, "negative and unsigned");
 static_assert(gcd(5u, 6u) == 1, "unsigned and unsigned");
+static_assert(gcd(54u, 36u) == 18, "unsigned and unsigned");
+static_assert(gcd(-5, -6) == 1, "negative and negative");
+static_assert(gcd(-50, -60) == 10, "negative and negative");
 
-static_assert( std::is_same_v<decltype(gcd(1l, 1)), long> );
-static_assert( std::is_same_v<decltype(gcd(1ul, 1ull)), unsigned long long> );
+static_assert( is_same_v<decltype(gcd(1l, 1)), long> );
+static_assert( is_same_v<decltype(gcd(1ul, 1ull)), unsigned long long> );
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/2.cc b/libstdc++-v3/testsuite/26_numerics/gcd/2.cc
new file mode 100644
index 00000000000..186dbac2425
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/2.cc
@@ -0,0 +1,133 @@
+// Copyright (C) 2015-2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++17 } }
+
+#include <numeric>
+#include <climits>
+#include <testsuite_hooks.h>
+
+constexpr struct testcase { unsigned long long p, q, r; } testcases[] = {
+  { 5, 8, 1 },
+  { 6, 35, 1 },
+  { 30, 42, 6 },
+  { 24, 60, 12 },
+  { 55, 144, 1 },
+  { 105, 252, 21 },
+  { 253, 22121, 11 },
+  { 1386, 3213, 63 },
+  { 2028, 2049, 3 },
+  { 46391, 62527, 2017 },
+  { 63245986, 39088169, 1 },
+  { 77160074263, 47687519812, 1 },
+  { 77160074264, 47687519812, 4 },
+};
+
+template<typename P, typename Q>
+constexpr bool
+check(P p, Q q, unsigned long long r)
+{
+  using R = std::common_type_t<P, Q>;
+  static_assert( std::is_same_v<decltype(std::gcd(p, q)), R> );
+  static_assert( std::is_same_v<decltype(std::gcd(q, p)), R> );
+  R r1 = std::gcd(p, q);
+  // Check non-negative, so conversion to unsigned long doesn't alter value.
+  VERIFY( r1 >= 0 );
+  // Check for expected result
+  VERIFY( (unsigned long long)r1 == r );
+  // Check reversing arguments doesn't change result
+  VERIFY( std::gcd(q, p) == r1 );
+
+  P pabs = p < 0 ? -p : p;
+  VERIFY( std::gcd(p, p) == pabs );
+  VERIFY( std::gcd(0, p) == pabs );
+  VERIFY( std::gcd(p, 0) == pabs );
+  VERIFY( std::gcd(1, p) == 1 );
+  VERIFY( std::gcd(p, 1) == 1 );
+  Q qabs = q < 0 ? -q : q;
+  VERIFY( std::gcd(q, q) == qabs );
+  VERIFY( std::gcd(0, q) == qabs );
+  VERIFY( std::gcd(q, 0) == qabs );
+  VERIFY( std::gcd(1, q) == 1 );
+  VERIFY( std::gcd(q, 1) == 1 );
+  VERIFY( std::gcd(r, r) == r );
+  VERIFY( std::gcd(0, r) == r );
+  VERIFY( std::gcd(r, 0) == r );
+  VERIFY( std::gcd(1, r) == 1 );
+  VERIFY( std::gcd(r, 1) == 1 );
+
+  return true;
+}
+
+constexpr bool
+test01()
+{
+  for (auto t : testcases)
+  {
+    check(t.p, t.q, t.r);
+
+    if (t.p <= LONG_MAX && t.q <= LONG_MAX)
+    {
+      check( (long)t.p,  (long)t.p, t.p);
+      check(-(long)t.p,  (long)t.p, t.p);
+      check(-(long)t.p, -(long)t.p, t.p);
+
+      check( (long)t.p, t.q, t.r);
+      check(-(long)t.p, t.q, t.r);
+
+      check(t.p,  (long)t.q, t.r);
+      check(t.p, -(long)t.q, t.r);
+
+      check( (long)t.p,  (long)t.q, t.r);
+      check( (long)t.p, -(long)t.q, t.r);
+      check(-(long)t.p,  (long)t.q, t.r);
+      check(-(long)t.p, -(long)t.q, t.r);
+    }
+
+    if (t.p <= INT_MAX && t.q <= INT_MAX)
+    {
+      check((long)t.p,  (int)t.q, t.r);
+      check(-(int)t.p, (long)t.q, t.r);
+
+      check( (int)t.p, (unsigned)t.q, t.r);
+      check(-(int)t.p, (unsigned)t.q, t.r);
+
+      check(-(int)t.p,  -(int)t.q, t.r);
+      check(-(int)t.p, -(long)t.q, t.r);
+    }
+
+    if (t.p <= SHRT_MAX && t.q <= SHRT_MAX)
+    {
+      check(  (long)t.p, (short)t.q, t.r);
+      check(-(short)t.p,  (long)t.q, t.r);
+
+      check( (short)t.p, (unsigned short)t.q, t.r);
+      check(-(short)t.p, (unsigned short)t.q, t.r);
+
+      check(-(short)t.p, -(short)t.q, t.r);
+      check(-(short)t.p,  -(long)t.q, t.r);
+    }
+  }
+  return true;
+}
+
+
+int main()
+{
+  static_assert( test01() );  // constexpr
+  VERIFY( test01() );	      // non-constexpr
+}
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
index 2e56bc650a7..fa559b6f475 100644
--- a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
@@ -46,9 +46,9 @@ test01()
   std::gcd<const int&, const int&>(0.1, 0.1);   // { dg-error "from here" }
 }
 
-// { dg-error "must be integers" "" { target *-*-* } 134 }
-// { dg-error "must be integers" "" { target *-*-* } 135 }
-// { dg-error "must not be bool" "" { target *-*-* } 136 }
-// { dg-error "must not be bool" "" { target *-*-* } 137 }
+// { dg-error "must be integers" "" { target *-*-* } 160 }
+// { dg-error "must be integers" "" { target *-*-* } 161 }
+// { dg-error "must not be bool" "" { target *-*-* } 162 }
+// { dg-error "must not be bool" "" { target *-*-* } 163 }
 // { dg-prune-output "deleted function" }
 // { dg-prune-output "incomplete type .*make_unsigned" }
diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
index 9e83fdcae0b..7e36c2654b0 100644
--- a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
@@ -46,9 +46,9 @@ test01()
   std::lcm<const int&, const int&>(0.1, 0.1);   // { dg-error "from here" }
 }
 
-// { dg-error "must be integers" "" { target *-*-* } 148 }
-// { dg-error "must be integers" "" { target *-*-* } 149 }
-// { dg-error "must not be bool" "" { target *-*-* } 150 }
-// { dg-error "must not be bool" "" { target *-*-* } 151 }
+// { dg-error "must be integers" "" { target *-*-* } 174 }
+// { dg-error "must be integers" "" { target *-*-* } 175 }
+// { dg-error "must not be bool" "" { target *-*-* } 176 }
+// { dg-error "must not be bool" "" { target *-*-* } 177 }
 // { dg-prune-output "deleted function" }
 // { dg-prune-output "incomplete type .*make_unsigned" }
diff --git a/libstdc++-v3/testsuite/experimental/numeric/gcd.cc b/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
index 33568cb1f3e..8555421b118 100644
--- a/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
+++ b/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
@@ -18,8 +18,16 @@
 // { dg-do compile { target c++14 } }
 
 #include <experimental/numeric>
+#include <experimental/type_traits>
+
+#ifndef __cpp_lib_experimental_gcd_lcm
+# error "Feature-test macro for gcd missing"
+#elif __cpp_lib_experimental_gcd_lcm != 201411
+# error "Feature-test macro for gcd has wrong value"
+#endif
 
 using std::experimental::fundamentals_v2::gcd;
+using std::experimental::is_same_v;
 
 static_assert( gcd(1071, 462) == 21, "" );
 static_assert( gcd(2000, 20) == 20, "" );
@@ -27,8 +35,134 @@ static_assert( gcd(2011, 17) == 1, "GCD of two primes is 1" );
 static_assert( gcd(200, 200) == 200, "GCD of equal numbers is that number" );
 static_assert( gcd(0, 13) == 13, "GCD of any number and 0 is that number" );
 static_assert( gcd(29, 0) == 29, "GCD of any number and 0 is that number" );
-static_assert( gcd(0, 0) == 0, "" );
+static_assert( gcd(0, 0) == 0, "Zarro Boogs found" );
 
 static_assert(gcd(1u, 2) == 1, "unsigned and signed");
+static_assert(gcd(9, 6u) == 3, "unsigned and signed");
 static_assert(gcd(3, 4u) == 1, "signed and unsigned");
+static_assert(gcd(32u, 24) == 8, "signed and unsigned");
+static_assert(gcd(1u, -2) == 1, "unsigned and negative");
+static_assert(gcd(-21, 28u) == 7, "unsigned and negative");
+static_assert(gcd(-3, 4u) == 1, "negative and unsigned");
+static_assert(gcd(33u, -44) == 11, "negative and unsigned");
 static_assert(gcd(5u, 6u) == 1, "unsigned and unsigned");
+static_assert(gcd(54u, 36u) == 18, "unsigned and unsigned");
+static_assert(gcd(-5, -6) == 1, "negative and negative");
+static_assert(gcd(-50, -60) == 10, "negative and negative");
+
+static_assert( is_same_v<decltype(gcd(1l, 1)), long>, "" );
+static_assert( is_same_v<decltype(gcd(1ul, 1ull)), unsigned long long>, "" );
+
+#include <climits>
+#include <testsuite_hooks.h>
+
+constexpr struct testcase { unsigned long long p, q, r; } testcases[] = {
+  { 5, 8, 1 },
+  { 6, 35, 1 },
+  { 30, 42, 6 },
+  { 24, 60, 12 },
+  { 55, 144, 1 },
+  { 105, 252, 21 },
+  { 253, 22121, 11 },
+  { 1386, 3213, 63 },
+  { 2028, 2049, 3 },
+  { 46391, 62527, 2017 },
+  { 63245986, 39088169, 1 },
+  { 77160074263, 47687519812, 1 },
+  { 77160074264, 47687519812, 4 },
+};
+
+template<typename P, typename Q>
+constexpr bool
+check(P p, Q q, unsigned long long r)
+{
+  using R = std::common_type_t<P, Q>;
+  static_assert( is_same_v<decltype(gcd(p, q)), R>, "" );
+  static_assert( is_same_v<decltype(gcd(q, p)), R>, "" );
+  R r1 = gcd(p, q);
+  // Check non-negative, so conversion to unsigned long doesn't alter value.
+  VERIFY( r1 >= 0 );
+  // Check for expected result
+  VERIFY( (unsigned long long)r1 == r );
+  // Check reversing arguments doesn't change result
+  VERIFY( gcd(q, p) == r1 );
+
+  P pabs = p < 0 ? -p : p;
+  VERIFY( gcd(p, p) == pabs );
+  VERIFY( gcd(0, p) == pabs );
+  VERIFY( gcd(p, 0) == pabs );
+  VERIFY( gcd(1, p) == 1 );
+  VERIFY( gcd(p, 1) == 1 );
+  Q qabs = q < 0 ? -q : q;
+  VERIFY( gcd(q, q) == qabs );
+  VERIFY( gcd(0, q) == qabs );
+  VERIFY( gcd(q, 0) == qabs );
+  VERIFY( gcd(1, q) == 1 );
+  VERIFY( gcd(q, 1) == 1 );
+  VERIFY( gcd(r, r) == r );
+  VERIFY( gcd(0, r) == r );
+  VERIFY( gcd(r, 0) == r );
+  VERIFY( gcd(1, r) == 1 );
+  VERIFY( gcd(r, 1) == 1 );
+
+  return true;
+}
+
+constexpr bool
+test01()
+{
+  for (auto t : testcases)
+  {
+    check(t.p, t.q, t.r);
+
+    if (t.p <= LONG_MAX && t.q <= LONG_MAX)
+    {
+      check( (long)t.p,  (long)t.p, t.p);
+      check(-(long)t.p,  (long)t.p, t.p);
+      check(-(long)t.p, -(long)t.p, t.p);
+
+      check( (long)t.p, t.q, t.r);
+      check(-(long)t.p, t.q, t.r);
+
+      check(t.p,  (long)t.q, t.r);
+      check(t.p, -(long)t.q, t.r);
+
+      check( (long)t.p,  (long)t.q, t.r);
+      check( (long)t.p, -(long)t.q, t.r);
+      check(-(long)t.p,  (long)t.q, t.r);
+      check(-(long)t.p, -(long)t.q, t.r);
+    }
+
+    if (t.p <= INT_MAX && t.q <= INT_MAX)
+    {
+      check((long)t.p,  (int)t.q, t.r);
+      check(-(int)t.p, (long)t.q, t.r);
+
+      check( (int)t.p, (unsigned)t.q, t.r);
+      check(-(int)t.p, (unsigned)t.q, t.r);
+
+      check(-(int)t.p,  -(int)t.q, t.r);
+      check(-(int)t.p, -(long)t.q, t.r);
+    }
+
+    if (t.p <= SHRT_MAX && t.q <= SHRT_MAX)
+    {
+      check(  (long)t.p, (short)t.q, t.r);
+      check(-(short)t.p,  (long)t.q, t.r);
+
+      check( (short)t.p, (unsigned short)t.q, t.r);
+      check(-(short)t.p, (unsigned short)t.q, t.r);
+
+      check(-(short)t.p, -(short)t.q, t.r);
+      check(-(short)t.p,  -(long)t.q, t.r);
+    }
+  }
+  return true;
+}
+
+
+int main()
+{
+  static_assert( test01() );  // constexpr
+  VERIFY( test01() );	      // non-constexpr
+}