[committed] libstdc++: Optimise GCD algorithms

Jonathan Wakely jwakely.gcc@gmail.com
Sat Sep 5 08:34:43 GMT 2020


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.


More information about the Libstdc++ mailing list