[committed] libstdc++: Optimise GCD algorithms

[Jonathan Wakely]

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.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.txt
Type: text/x-patch
Size: 1373 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200907/d479084c/attachment.bin>