On 05/09/20 09:34 +0100, Jonathan Wakely via Libstdc++ wrote:
On Sat, 5 Sep 2020 at 01:35, Sidney Marshall <sidn...@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 <jwak...@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.
commit ec5096f48bbd7db83cbe94bdd3235c5808a5979a
Author: Jonathan Wakely <jwak...@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
}
