From 3c219134152f645103f2fcd50735b177ccd76cde Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Thu, 3 Sep 2020 12:38:50 +0100 Subject: 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. --- libstdc++-v3/include/std/chrono | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) (limited to 'libstdc++-v3/include/std/chrono') diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index 1682263..0e2efb2 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) + { + intmax_t __rem = __m % __n; + __m = __n; + __n = __rem; + } + return __m + __n; +#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 } // _GLIBCXX_RESOLVE_LIB_DEFECTS -- cgit v1.1