[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