[libc++] Implement std::gcd using the binary version

[serge-sans-paille]

Summary

This implementation is ~two times faster than current implementation in my setup

Code inspired by https://en.algorithmica.org/hpc/algorithms/gcd/
which itself is inspired by https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

[serge-sans-paille]

First time contribution to libc++, I apologize in advance if the style / conformance is not correct.

[serge-sans-paille]

+ constexpr version
+ check for ub in bitwise shift.

[serge-sans-paille]

Still get a

# command output:
*** /home/ssp/sources/llvm-project/libcxx/test/libcxx/transitive_includes/cxx2b.csv
--- /home/ssp/sources/llvm-project/_build/runtimes/runtimes-bins/test/libcxx/Output/transitive_includes.sh.cpp.dir/t.tmp/transitive_includes.csv
***************
*** 432,437 ****
--- 432,438 ----
  numbersversion
  numericcmath
// -*- C++ -*-
  numericcstddef
+ numericinitializer_list
  numericlimits
  numericversion
  optionalcompare

error: command failed with exit status: 1
********************
Failed Tests (1):
  llvm-libc++-shared.cfg.in :: libcxx/transitive_includes.sh.cpp

[cjdb]

Thanks for working on this. I haven't contributed to libc++ in a very long time, so the project's policies may be different to what I'm asking for. Having said that, the following things would be good to do:

• Please add a description to your commit message explaining why this change is valuable. If there's a GitHub issue, please also link to that (just add something like Closes #1234).
• If this is a functional change, please add a test. If this is a non-functional change, please add [NFC] to the commit message.
• It may be worth moving the #ifdef to the body of the function, rather than creating two identical overloads whose interfaces might accidentally diverge over time.

libcxx/include/__numeric/gcd_lcm.h

62

Please fully qualify all the function calls.

[serge-sans-paille]

Take review into account.

[serge-sans-paille]

Fix test

[serge-sans-paille]

Fix ADL

[serge-sans-paille]

@cjdb : should be good now :-)

[serge-sans-paille]

Fix variable naming.

[serge-sans-paille]

rebased + fix intermediate type

[philnik]

Thanks for working on this!
Could you add the benchmark you used to libcxx/benchmarks and give us the exact results you get?

libcxx/include/__numeric/gcd_lcm.h

17

These should be included unconditionally.

63

Same throughout

64

Is there anything C++20-specific other than countr_zero? If no, then I think it would make sense to add a __countr_zero to older language modes and forward the countr_zero implementation.

66

[serge-sans-paille]

Associated benchmark: https://quick-bench.com/q/MpH_u9y6pjBes9p3MFiElANDHXI

[philnik]

Neither quick bench nor I on my local system can reproduce a 4x speedup. In fact, the naive version is significantly faster than your version. Are you sure everything works as expected?

libcxx/include/__bit/countr.h

34–35

This doesn't work pre-C++20.

35–36

libcxx/include/__numeric/gcd_lcm.h

64

Same for other places.

libcxx/test/libcxx/transitive_includes/cxx26.csv

191–211

This shouldn't be in here anymore. Did you maybe use an older version to generate this?

[serge-sans-paille]

Updated benchmark that doesn't focus on a single value: https://quick-bench.com/q/XEb2zlF7cpb_gSjUB2f71X4Hbw8

[philnik]

libcxx/include/__bit/countr.h

28

Please add the benchmarks under libcxx/benchmarks/.

libcxx/include/__numeric/gcd_lcm.h

54

Could you add a short comment explaining how the algorithm works?

libcxx/include/__bit/countr.h

 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 int __libcpp_ctz(unsigned __x)           _NOEXCEPT { return __builtin_ctz(__x); }
 
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 int __libcpp_ctz(unsigned long __x)      _NOEXCEPT { return __builtin_ctzl(__x); }
 
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { return __builtin_ctzll(__x); }
 
-#if _LIBCPP_STD_VER >= 20
-
-template <__libcpp_unsigned_integer _Tp>
-_LIBCPP_HIDE_FROM_ABI constexpr int countr_zero(_Tp __t) noexcept {
+template <typename _Tp>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int __countr_zero(_Tp __t) noexcept {
   if (__t == 0)
     return numeric_limits<_Tp>::digits;
 
   if (sizeof(_Tp) <= sizeof(unsigned int))
     return std::__libcpp_ctz(static_cast<unsigned int>(__t));
   else if (sizeof(_Tp) <= sizeof(unsigned long))
     return std::__libcpp_ctz(static_cast<unsigned long>(__t));
   else if (sizeof(_Tp) <= sizeof(unsigned long long))
     return std::__libcpp_ctz(static_cast<unsigned long long>(__t));
   else {
     int __ret = 0;
     const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
     while (static_cast<unsigned long long>(__t) == 0uLL) {
       __ret += __ulldigits;
       __t >>= __ulldigits;
     }
     return __ret + std::__libcpp_ctz(static_cast<unsigned long long>(__t));
   }
 }
 
+#if _LIBCPP_STD_VER >= 20
+
+template <__libcpp_unsigned_integer _Tp>
+_LIBCPP_HIDE_FROM_ABI constexpr int countr_zero(_Tp __t) noexcept {
+  return __countr_zero(__t);
+}
+
 template <__libcpp_unsigned_integer _Tp>
 _LIBCPP_HIDE_FROM_ABI constexpr int countr_one(_Tp __t) noexcept {
   return __t != numeric_limits<_Tp>::max() ? std::countr_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits;
 }
 
 #endif // _LIBCPP_STD_VER >= 20
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___BIT_COUNTR_H

libcxx/include/__numeric/gcd_lcm.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___NUMERIC_GCD_LCM_H
 #define _LIBCPP___NUMERIC_GCD_LCM_H
 
+#include <__algorithm/min.h>
 #include <__assert>
+#include <__bit/countr.h>
 #include <__config>
 #include <__type_traits/common_type.h>
 #include <__type_traits/is_integral.h>
 #include <__type_traits/is_same.h>
 #include <__type_traits/is_signed.h>
 #include <__type_traits/make_unsigned.h>
 #include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header

 };
 
 template <typename _Result, typename _Source>
 struct __ct_abs<_Result, _Source, false> {
     _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
     _Result operator()(_Source __t) const noexcept { return __t; }
 };
 
-
-template<class _Tp>
-_LIBCPP_CONSTEXPR _LIBCPP_HIDDEN
-_Tp __gcd(_Tp __m, _Tp __n)
-{
+template <class _Tp>
+_LIBCPP_CONSTEXPR _LIBCPP_HIDDEN _Tp __gcd(_Tp __a, _Tp __b) {
     static_assert((!is_signed<_Tp>::value), "");
-    return __n == 0 ? __m : _VSTD::__gcd<_Tp>(__n, __m % __n);
+    if (__a == 0)
+        return __b;
+    if (__b == 0)
+        return __a;
+
+    int __az    = std::__countr_zero(__a);
+    int __bz    = std::__countr_zero(__b);
+    int __shift = std::min(__az, __bz);
+    __b >>= __bz;
+    while (__a != 0) {
+        __a >>= __az;
+        _Tp __absdiff = __a > __b ? __a - __b : __b - __a;
+        __b           = std::min(__a, __b);
+        __a           = __absdiff;
+        __az          = std::__countr_zero(__absdiff);
+    }
+    return __b << __shift;
 }
 
 template<class _Tp, class _Up>
 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
 common_type_t<_Tp,_Up>
 gcd(_Tp __m, _Up __n)
 {
     static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types");

libcxx/test/libcxx/transitive_includes/cxx23.csv

 mutex typeinfo
 mutex version
 new cstddef
 new cstdlib
 new version
 numbers version
 numeric cmath
 numeric cstddef
+numeric initializer_list
 numeric limits
 numeric version
 optional compare
 optional cstddef
 optional cstdint
 optional cstring
 optional initializer_list
 optional limits

libcxx/test/libcxx/transitive_includes/cxx26.csv

 experimental/type_traits type_traits
 experimental/unordered_map experimental/memory_resource
 experimental/unordered_map unordered_map
 experimental/unordered_set experimental/memory_resource
 experimental/unordered_set unordered_set
 experimental/utility utility
 experimental/vector experimental/memory_resource
 experimental/vector vector
+ext/hash_map algorithm
+ext/hash_map cmath
+ext/hash_map cstddef
+ext/hash_map cstdint
+ext/hash_map cstring
+ext/hash_map functional
+ext/hash_map initializer_list
+ext/hash_map limits
+ext/hash_map new
+ext/hash_map stdexcept
+ext/hash_map string
+ext/hash_set algorithm
+ext/hash_set cmath
+ext/hash_set cstddef
+ext/hash_set cstdint
+ext/hash_set cstring
+ext/hash_set functional
+ext/hash_set initializer_list
+ext/hash_set limits
+ext/hash_set new
+ext/hash_set string
 filesystem compare
 filesystem cstddef
 filesystem cstdint
 filesystem ctime
 filesystem iomanip
 filesystem iosfwd
 filesystem limits
 filesystem locale

 mutex typeinfo
 mutex version
 new cstddef
 new cstdlib
 new version
 numbers version
 numeric cmath
 numeric cstddef
+numeric initializer_list
 numeric limits
 numeric version
 optional compare
 optional cstddef
 optional cstdint
 optional cstring
 optional initializer_list
 optional limits