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