[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
>         }
>
>...