public inbox for libstdc++-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r11-2996] libstdc++: Optimise GCD algorithms
@ 2020-09-03 11:46 Jonathan Wakely
0 siblings, 0 replies; only message in thread
From: Jonathan Wakely @ 2020-09-03 11:46 UTC (permalink / raw)
To: gcc-cvs, libstdc++-cvs
https://gcc.gnu.org/g:3c219134152f645103f2fcd50735b177ccd76cde
commit r11-2996-g3c219134152f645103f2fcd50735b177ccd76cde
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Thu Sep 3 12:38:50 2020 +0100
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:
---
libstdc++-v3/include/std/chrono | 14 ++-
libstdc++-v3/include/std/numeric | 34 +++++-
libstdc++-v3/testsuite/26_numerics/gcd/1.cc | 17 ++-
libstdc++-v3/testsuite/26_numerics/gcd/2.cc | 133 ++++++++++++++++++++
libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc | 8 +-
libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc | 8 +-
libstdc++-v3/testsuite/experimental/numeric/gcd.cc | 136 ++++++++++++++++++++-
7 files changed, 332 insertions(+), 18 deletions(-)
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)
+ {
+ 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
diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric
index bd70a52019b..2de6aaf06ec 100644
--- a/libstdc++-v3/include/std/numeric
+++ b/libstdc++-v3/include/std/numeric
@@ -76,6 +76,7 @@
#if __cplusplus >= 201402L
#include <type_traits>
+#include <bit>
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -97,15 +98,40 @@ namespace __detail
template<typename _Up> void __absu(bool) = delete;
- // GCD implementation
+ // GCD implementation, using Stein's algorithm
template<typename _Tp>
constexpr _Tp
__gcd(_Tp __m, _Tp __n)
{
static_assert(is_unsigned<_Tp>::value, "type must be unsigned");
- return __m == 0 ? __n
- : __n == 0 ? __m
- : __detail::__gcd(__n, _Tp(__m % __n));
+
+ if (__m == 0)
+ return __n;
+ if (__n == 0)
+ return __m;
+
+ const int __i = std::__countr_zero(__m);
+ __m >>= __i;
+ const int __j = std::__countr_zero(__n);
+ __n >>= __j;
+ const int __k = __i < __j ? __i : __j; // min(i, j)
+
+ while (true)
+ {
+ if (__m > __n)
+ {
+ _Tp __tmp = __m;
+ __m = __n;
+ __n = __tmp;
+ }
+
+ __n -= __m;
+
+ if (__n == 0)
+ return __m << __k;
+
+ __n >>= std::__countr_zero(__n);
+ }
}
// LCM implementation
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/1.cc b/libstdc++-v3/testsuite/26_numerics/gcd/1.cc
index 042f0a9e2f0..dc43cda395c 100644
--- a/libstdc++-v3/testsuite/26_numerics/gcd/1.cc
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/1.cc
@@ -15,7 +15,6 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-// { dg-options "-std=gnu++17" }
// { dg-do compile { target c++17 } }
#include <numeric>
@@ -27,6 +26,7 @@
#endif
using std::gcd;
+using std::is_same_v;
static_assert( gcd(1071, 462) == 21, "" );
static_assert( gcd(2000, 20) == 20, "" );
@@ -34,11 +34,20 @@ static_assert( gcd(2011, 17) == 1, "GCD of two primes is 1" );
static_assert( gcd(200, 200) == 200, "GCD of equal numbers is that number" );
static_assert( gcd(0, 13) == 13, "GCD of any number and 0 is that number" );
static_assert( gcd(29, 0) == 29, "GCD of any number and 0 is that number" );
-static_assert( gcd(0, 0) == 0, "" );
+static_assert( gcd(0, 0) == 0, "Zarro Boogs found" );
static_assert(gcd(1u, 2) == 1, "unsigned and signed");
+static_assert(gcd(9, 6u) == 3, "unsigned and signed");
static_assert(gcd(3, 4u) == 1, "signed and unsigned");
+static_assert(gcd(32u, 24) == 8, "signed and unsigned");
+static_assert(gcd(1u, -2) == 1, "unsigned and negative");
+static_assert(gcd(-21, 28u) == 7, "unsigned and negative");
+static_assert(gcd(-3, 4u) == 1, "negative and unsigned");
+static_assert(gcd(33u, -44) == 11, "negative and unsigned");
static_assert(gcd(5u, 6u) == 1, "unsigned and unsigned");
+static_assert(gcd(54u, 36u) == 18, "unsigned and unsigned");
+static_assert(gcd(-5, -6) == 1, "negative and negative");
+static_assert(gcd(-50, -60) == 10, "negative and negative");
-static_assert( std::is_same_v<decltype(gcd(1l, 1)), long> );
-static_assert( std::is_same_v<decltype(gcd(1ul, 1ull)), unsigned long long> );
+static_assert( is_same_v<decltype(gcd(1l, 1)), long> );
+static_assert( is_same_v<decltype(gcd(1ul, 1ull)), unsigned long long> );
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/2.cc b/libstdc++-v3/testsuite/26_numerics/gcd/2.cc
new file mode 100644
index 00000000000..186dbac2425
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/2.cc
@@ -0,0 +1,133 @@
+// Copyright (C) 2015-2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++17 } }
+
+#include <numeric>
+#include <climits>
+#include <testsuite_hooks.h>
+
+constexpr struct testcase { unsigned long long p, q, r; } testcases[] = {
+ { 5, 8, 1 },
+ { 6, 35, 1 },
+ { 30, 42, 6 },
+ { 24, 60, 12 },
+ { 55, 144, 1 },
+ { 105, 252, 21 },
+ { 253, 22121, 11 },
+ { 1386, 3213, 63 },
+ { 2028, 2049, 3 },
+ { 46391, 62527, 2017 },
+ { 63245986, 39088169, 1 },
+ { 77160074263, 47687519812, 1 },
+ { 77160074264, 47687519812, 4 },
+};
+
+template<typename P, typename Q>
+constexpr bool
+check(P p, Q q, unsigned long long r)
+{
+ using R = std::common_type_t<P, Q>;
+ static_assert( std::is_same_v<decltype(std::gcd(p, q)), R> );
+ static_assert( std::is_same_v<decltype(std::gcd(q, p)), R> );
+ R r1 = std::gcd(p, q);
+ // Check non-negative, so conversion to unsigned long doesn't alter value.
+ VERIFY( r1 >= 0 );
+ // Check for expected result
+ VERIFY( (unsigned long long)r1 == r );
+ // Check reversing arguments doesn't change result
+ VERIFY( std::gcd(q, p) == r1 );
+
+ P pabs = p < 0 ? -p : p;
+ VERIFY( std::gcd(p, p) == pabs );
+ VERIFY( std::gcd(0, p) == pabs );
+ VERIFY( std::gcd(p, 0) == pabs );
+ VERIFY( std::gcd(1, p) == 1 );
+ VERIFY( std::gcd(p, 1) == 1 );
+ Q qabs = q < 0 ? -q : q;
+ VERIFY( std::gcd(q, q) == qabs );
+ VERIFY( std::gcd(0, q) == qabs );
+ VERIFY( std::gcd(q, 0) == qabs );
+ VERIFY( std::gcd(1, q) == 1 );
+ VERIFY( std::gcd(q, 1) == 1 );
+ VERIFY( std::gcd(r, r) == r );
+ VERIFY( std::gcd(0, r) == r );
+ VERIFY( std::gcd(r, 0) == r );
+ VERIFY( std::gcd(1, r) == 1 );
+ VERIFY( std::gcd(r, 1) == 1 );
+
+ return true;
+}
+
+constexpr bool
+test01()
+{
+ for (auto t : testcases)
+ {
+ check(t.p, t.q, t.r);
+
+ if (t.p <= LONG_MAX && t.q <= LONG_MAX)
+ {
+ check( (long)t.p, (long)t.p, t.p);
+ check(-(long)t.p, (long)t.p, t.p);
+ check(-(long)t.p, -(long)t.p, t.p);
+
+ check( (long)t.p, t.q, t.r);
+ check(-(long)t.p, t.q, t.r);
+
+ check(t.p, (long)t.q, t.r);
+ check(t.p, -(long)t.q, t.r);
+
+ check( (long)t.p, (long)t.q, t.r);
+ check( (long)t.p, -(long)t.q, t.r);
+ check(-(long)t.p, (long)t.q, t.r);
+ check(-(long)t.p, -(long)t.q, t.r);
+ }
+
+ if (t.p <= INT_MAX && t.q <= INT_MAX)
+ {
+ check((long)t.p, (int)t.q, t.r);
+ check(-(int)t.p, (long)t.q, t.r);
+
+ check( (int)t.p, (unsigned)t.q, t.r);
+ check(-(int)t.p, (unsigned)t.q, t.r);
+
+ check(-(int)t.p, -(int)t.q, t.r);
+ check(-(int)t.p, -(long)t.q, t.r);
+ }
+
+ if (t.p <= SHRT_MAX && t.q <= SHRT_MAX)
+ {
+ check( (long)t.p, (short)t.q, t.r);
+ check(-(short)t.p, (long)t.q, t.r);
+
+ check( (short)t.p, (unsigned short)t.q, t.r);
+ check(-(short)t.p, (unsigned short)t.q, t.r);
+
+ check(-(short)t.p, -(short)t.q, t.r);
+ check(-(short)t.p, -(long)t.q, t.r);
+ }
+ }
+ return true;
+}
+
+
+int main()
+{
+ static_assert( test01() ); // constexpr
+ VERIFY( test01() ); // non-constexpr
+}
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
index 2e56bc650a7..fa559b6f475 100644
--- a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
@@ -46,9 +46,9 @@ test01()
std::gcd<const int&, const int&>(0.1, 0.1); // { dg-error "from here" }
}
-// { dg-error "must be integers" "" { target *-*-* } 134 }
-// { dg-error "must be integers" "" { target *-*-* } 135 }
-// { dg-error "must not be bool" "" { target *-*-* } 136 }
-// { dg-error "must not be bool" "" { target *-*-* } 137 }
+// { dg-error "must be integers" "" { target *-*-* } 160 }
+// { dg-error "must be integers" "" { target *-*-* } 161 }
+// { dg-error "must not be bool" "" { target *-*-* } 162 }
+// { dg-error "must not be bool" "" { target *-*-* } 163 }
// { dg-prune-output "deleted function" }
// { dg-prune-output "incomplete type .*make_unsigned" }
diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
index 9e83fdcae0b..7e36c2654b0 100644
--- a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
@@ -46,9 +46,9 @@ test01()
std::lcm<const int&, const int&>(0.1, 0.1); // { dg-error "from here" }
}
-// { dg-error "must be integers" "" { target *-*-* } 148 }
-// { dg-error "must be integers" "" { target *-*-* } 149 }
-// { dg-error "must not be bool" "" { target *-*-* } 150 }
-// { dg-error "must not be bool" "" { target *-*-* } 151 }
+// { dg-error "must be integers" "" { target *-*-* } 174 }
+// { dg-error "must be integers" "" { target *-*-* } 175 }
+// { dg-error "must not be bool" "" { target *-*-* } 176 }
+// { dg-error "must not be bool" "" { target *-*-* } 177 }
// { dg-prune-output "deleted function" }
// { dg-prune-output "incomplete type .*make_unsigned" }
diff --git a/libstdc++-v3/testsuite/experimental/numeric/gcd.cc b/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
index 33568cb1f3e..8555421b118 100644
--- a/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
+++ b/libstdc++-v3/testsuite/experimental/numeric/gcd.cc
@@ -18,8 +18,16 @@
// { dg-do compile { target c++14 } }
#include <experimental/numeric>
+#include <experimental/type_traits>
+
+#ifndef __cpp_lib_experimental_gcd_lcm
+# error "Feature-test macro for gcd missing"
+#elif __cpp_lib_experimental_gcd_lcm != 201411
+# error "Feature-test macro for gcd has wrong value"
+#endif
using std::experimental::fundamentals_v2::gcd;
+using std::experimental::is_same_v;
static_assert( gcd(1071, 462) == 21, "" );
static_assert( gcd(2000, 20) == 20, "" );
@@ -27,8 +35,134 @@ static_assert( gcd(2011, 17) == 1, "GCD of two primes is 1" );
static_assert( gcd(200, 200) == 200, "GCD of equal numbers is that number" );
static_assert( gcd(0, 13) == 13, "GCD of any number and 0 is that number" );
static_assert( gcd(29, 0) == 29, "GCD of any number and 0 is that number" );
-static_assert( gcd(0, 0) == 0, "" );
+static_assert( gcd(0, 0) == 0, "Zarro Boogs found" );
static_assert(gcd(1u, 2) == 1, "unsigned and signed");
+static_assert(gcd(9, 6u) == 3, "unsigned and signed");
static_assert(gcd(3, 4u) == 1, "signed and unsigned");
+static_assert(gcd(32u, 24) == 8, "signed and unsigned");
+static_assert(gcd(1u, -2) == 1, "unsigned and negative");
+static_assert(gcd(-21, 28u) == 7, "unsigned and negative");
+static_assert(gcd(-3, 4u) == 1, "negative and unsigned");
+static_assert(gcd(33u, -44) == 11, "negative and unsigned");
static_assert(gcd(5u, 6u) == 1, "unsigned and unsigned");
+static_assert(gcd(54u, 36u) == 18, "unsigned and unsigned");
+static_assert(gcd(-5, -6) == 1, "negative and negative");
+static_assert(gcd(-50, -60) == 10, "negative and negative");
+
+static_assert( is_same_v<decltype(gcd(1l, 1)), long>, "" );
+static_assert( is_same_v<decltype(gcd(1ul, 1ull)), unsigned long long>, "" );
+
+#include <climits>
+#include <testsuite_hooks.h>
+
+constexpr struct testcase { unsigned long long p, q, r; } testcases[] = {
+ { 5, 8, 1 },
+ { 6, 35, 1 },
+ { 30, 42, 6 },
+ { 24, 60, 12 },
+ { 55, 144, 1 },
+ { 105, 252, 21 },
+ { 253, 22121, 11 },
+ { 1386, 3213, 63 },
+ { 2028, 2049, 3 },
+ { 46391, 62527, 2017 },
+ { 63245986, 39088169, 1 },
+ { 77160074263, 47687519812, 1 },
+ { 77160074264, 47687519812, 4 },
+};
+
+template<typename P, typename Q>
+constexpr bool
+check(P p, Q q, unsigned long long r)
+{
+ using R = std::common_type_t<P, Q>;
+ static_assert( is_same_v<decltype(gcd(p, q)), R>, "" );
+ static_assert( is_same_v<decltype(gcd(q, p)), R>, "" );
+ R r1 = gcd(p, q);
+ // Check non-negative, so conversion to unsigned long doesn't alter value.
+ VERIFY( r1 >= 0 );
+ // Check for expected result
+ VERIFY( (unsigned long long)r1 == r );
+ // Check reversing arguments doesn't change result
+ VERIFY( gcd(q, p) == r1 );
+
+ P pabs = p < 0 ? -p : p;
+ VERIFY( gcd(p, p) == pabs );
+ VERIFY( gcd(0, p) == pabs );
+ VERIFY( gcd(p, 0) == pabs );
+ VERIFY( gcd(1, p) == 1 );
+ VERIFY( gcd(p, 1) == 1 );
+ Q qabs = q < 0 ? -q : q;
+ VERIFY( gcd(q, q) == qabs );
+ VERIFY( gcd(0, q) == qabs );
+ VERIFY( gcd(q, 0) == qabs );
+ VERIFY( gcd(1, q) == 1 );
+ VERIFY( gcd(q, 1) == 1 );
+ VERIFY( gcd(r, r) == r );
+ VERIFY( gcd(0, r) == r );
+ VERIFY( gcd(r, 0) == r );
+ VERIFY( gcd(1, r) == 1 );
+ VERIFY( gcd(r, 1) == 1 );
+
+ return true;
+}
+
+constexpr bool
+test01()
+{
+ for (auto t : testcases)
+ {
+ check(t.p, t.q, t.r);
+
+ if (t.p <= LONG_MAX && t.q <= LONG_MAX)
+ {
+ check( (long)t.p, (long)t.p, t.p);
+ check(-(long)t.p, (long)t.p, t.p);
+ check(-(long)t.p, -(long)t.p, t.p);
+
+ check( (long)t.p, t.q, t.r);
+ check(-(long)t.p, t.q, t.r);
+
+ check(t.p, (long)t.q, t.r);
+ check(t.p, -(long)t.q, t.r);
+
+ check( (long)t.p, (long)t.q, t.r);
+ check( (long)t.p, -(long)t.q, t.r);
+ check(-(long)t.p, (long)t.q, t.r);
+ check(-(long)t.p, -(long)t.q, t.r);
+ }
+
+ if (t.p <= INT_MAX && t.q <= INT_MAX)
+ {
+ check((long)t.p, (int)t.q, t.r);
+ check(-(int)t.p, (long)t.q, t.r);
+
+ check( (int)t.p, (unsigned)t.q, t.r);
+ check(-(int)t.p, (unsigned)t.q, t.r);
+
+ check(-(int)t.p, -(int)t.q, t.r);
+ check(-(int)t.p, -(long)t.q, t.r);
+ }
+
+ if (t.p <= SHRT_MAX && t.q <= SHRT_MAX)
+ {
+ check( (long)t.p, (short)t.q, t.r);
+ check(-(short)t.p, (long)t.q, t.r);
+
+ check( (short)t.p, (unsigned short)t.q, t.r);
+ check(-(short)t.p, (unsigned short)t.q, t.r);
+
+ check(-(short)t.p, -(short)t.q, t.r);
+ check(-(short)t.p, -(long)t.q, t.r);
+ }
+ }
+ return true;
+}
+
+
+int main()
+{
+ static_assert( test01() ); // constexpr
+ VERIFY( test01() ); // non-constexpr
+}
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2020-09-03 11:46 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-09-03 11:46 [gcc r11-2996] libstdc++: Optimise GCD algorithms Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).