public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [committed] libstdc++: Allow Lemire's algorithm to be used in more cases
@ 2020-10-29 14:59 Jonathan Wakely
  2020-11-03 21:28 ` Stephan Bergmann
  0 siblings, 1 reply; 7+ messages in thread
From: Jonathan Wakely @ 2020-10-29 14:59 UTC (permalink / raw)
  To: libstdc++, gcc-patches; +Cc: Daniel Lemire

[-- Attachment #1: Type: text/plain, Size: 1576 bytes --]

This extends the fast path to also work when the URBG's range of
possible values is not the entire range of its result_type. Previously,
the slow path would be used for engines with a uint_fast32_t result type
if that type is actually a typedef for uint64_t rather than uint32_t.
After this change, the generator's result_type is not important, only
the range of possible value that generator can produce. If the
generator's range is exactly UINT64_MAX then the calculation will be
done using 128-bit and 64-bit integers, and if the range is UINT32_MAX
it will be done using 64-bit and 32-bit integers.

In practice, this benefits most of the engines and engine adaptors
defined in [rand.predef] on x86_64-linux and other 64-bit targets. This
is because std::minstd_rand0 and std::mt19937 and others use
uint_fast32_t, which is a typedef for uint64_t.

The code now makes use of the recently-clarified requirement that the
generator's min() and max() functions are usable in constant
expressions (see LWG 2154).

libstdc++-v3/ChangeLog:

	* include/bits/uniform_int_dist.h (_Power_of_two): Add
	constexpr.
	(uniform_int_distribution::_S_nd): Add static_assert to ensure
	the wider type is twice as wide as the result type.
	(uniform_int_distribution::__generate_impl): Add static_assert
	and declare variables as constexpr where appropriate.
	(uniform_int_distribution:operator()): Likewise. Only consider
	the uniform random bit generator's range of possible results
	when deciding whether _S_nd can be used, not the __uctype type.

Tested x86_64-linux. Committed to trunk.


[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 6387 bytes --]

commit 822c1d21a3c710831af65a6e3bc83f558fb39044
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Oct 29 14:47:18 2020

    libstdc++: Allow Lemire's algorithm to be used in more cases
    
    This extends the fast path to also work when the URBG's range of
    possible values is not the entire range of its result_type. Previously,
    the slow path would be used for engines with a uint_fast32_t result type
    if that type is actually a typedef for uint64_t rather than uint32_t.
    After this change, the generator's result_type is not important, only
    the range of possible value that generator can produce. If the
    generator's range is exactly UINT64_MAX then the calculation will be
    done using 128-bit and 64-bit integers, and if the range is UINT32_MAX
    it will be done using 64-bit and 32-bit integers.
    
    In practice, this benefits most of the engines and engine adaptors
    defined in [rand.predef] on x86_64-linux and other 64-bit targets. This
    is because std::minstd_rand0 and std::mt19937 and others use
    uint_fast32_t, which is a typedef for uint64_t.
    
    The code now makes use of the recently-clarified requirement that the
    generator's min() and max() functions are usable in constant
    expressions (see LWG 2154).
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/uniform_int_dist.h (_Power_of_two): Add
            constexpr.
            (uniform_int_distribution::_S_nd): Add static_assert to ensure
            the wider type is twice as wide as the result type.
            (uniform_int_distribution::__generate_impl): Add static_assert
            and declare variables as constexpr where appropriate.
            (uniform_int_distribution:operator()): Likewise. Only consider
            the uniform random bit generator's range of possible results
            when deciding whether _S_nd can be used, not the __uctype type.

diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h b/libstdc++-v3/include/bits/uniform_int_dist.h
index cf6ba35c675..524593bb984 100644
--- a/libstdc++-v3/include/bits/uniform_int_dist.h
+++ b/libstdc++-v3/include/bits/uniform_int_dist.h
@@ -58,7 +58,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   {
     /* Determine whether number is a power of 2.  */
     template<typename _Tp>
-      inline bool
+      constexpr bool
       _Power_of_2(_Tp __x)
       {
 	return ((__x - 1) & __x) == 0;
@@ -242,9 +242,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	static _Up
 	_S_nd(_Urbg& __g, _Up __range)
 	{
-	  using __gnu_cxx::__int_traits;
-	  static_assert(!__int_traits<_Up>::__is_signed, "U must be unsigned");
-	  static_assert(!__int_traits<_Wp>::__is_signed, "W must be unsigned");
+	  using _Up_traits = __gnu_cxx::__int_traits<_Up>;
+	  using _Wp_traits = __gnu_cxx::__int_traits<_Wp>;
+	  static_assert(!_Up_traits::__is_signed, "U must be unsigned");
+	  static_assert(!_Wp_traits::__is_signed, "W must be unsigned");
+	  static_assert(_Wp_traits::__digits == (2 * _Up_traits::__digits),
+			"W must be twice as wide as U");
 
 	  // reference: Fast Random Integer Generation in an Interval
 	  // ACM Transactions on Modeling and Computer Simulation 29 (1), 2019
@@ -260,7 +263,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  __low = _Up(__product);
 		}
 	    }
-	  return __product >> __gnu_cxx::__int_traits<_Up>::__digits;
+	  return __product >> _Up_traits::__digits;
 	}
     };
 
@@ -275,9 +278,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	typedef typename make_unsigned<result_type>::type __utype;
 	typedef typename common_type<_Gresult_type, __utype>::type __uctype;
 
-	const __uctype __urngmin = __urng.min();
-	const __uctype __urngmax = __urng.max();
-	const __uctype __urngrange = __urngmax - __urngmin;
+	static_assert( __urng.min() < __urng.max(),
+	    "Uniform random bit generator must define min() < max()");
+
+	constexpr __uctype __urngmin = __urng.min();
+	constexpr __uctype __urngmax = __urng.max();
+	constexpr __uctype __urngrange = __urngmax - __urngmin;
 	const __uctype __urange
 	  = __uctype(__param.b()) - __uctype(__param.a());
 
@@ -288,21 +294,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	    const __uctype __uerange = __urange + 1; // __urange can be zero
 
-	    using __gnu_cxx::__int_traits;
+#if defined __UINT64_TYPE__ && defined __UINT32_TYPE__
 #if __SIZEOF_INT128__
-	    if (__int_traits<__uctype>::__digits == 64
-		&& __urngrange == __int_traits<__uctype>::__max)
+	    if _GLIBCXX17_CONSTEXPR (__urngrange == __UINT64_MAX__)
 	      {
-		__ret = _S_nd<unsigned __int128>(__urng, __uerange);
+		// __urng produces values that use exactly 64-bits,
+		// so use 128-bit integers to downscale to desired range.
+		__UINT64_TYPE__ __u64erange = __uerange;
+		__ret = _S_nd<unsigned __int128>(__urng, __u64erange);
 	      }
 	    else
 #endif
-	    if (__int_traits<__uctype>::__digits == 32
-		&& __urngrange == __int_traits<__uctype>::__max)
+	    if _GLIBCXX17_CONSTEXPR (__urngrange == __UINT32_MAX__)
 	      {
-		__ret = _S_nd<__UINT64_TYPE__>(__urng, __uerange);
+		// __urng produces values that use exactly 32-bits,
+		// so use 64-bit integers to downscale to desired range.
+		__UINT32_TYPE__ __u32erange = __uerange;
+		__ret = _S_nd<__UINT64_TYPE__>(__urng, __u32erange);
 	      }
 	    else
+#endif
 	      {
 		// fallback case (2 divisions)
 		const __uctype __scaling = __urngrange / __uerange;
@@ -361,9 +372,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	typedef typename make_unsigned<result_type>::type __utype;
 	typedef typename common_type<_Gresult_type, __utype>::type __uctype;
 
-	const __uctype __urngmin = __urng.min();
-	const __uctype __urngmax = __urng.max();
-	const __uctype __urngrange = __urngmax - __urngmin;
+	static_assert( __urng.min() < __urng.max(),
+	    "Uniform random bit generator must define min() < max()");
+
+	constexpr __uctype __urngmin = __urng.min();
+	constexpr __uctype __urngmax = __urng.max();
+	constexpr __uctype __urngrange = __urngmax - __urngmin;
 	const __uctype __urange
 	  = __uctype(__param.b()) - __uctype(__param.a());
 
@@ -417,7 +431,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      {
 		do
 		  {
-		    const __uctype __uerngrange = __urngrange + 1;
+		    constexpr __uctype __uerngrange = __urngrange + 1;
 		    __tmp = (__uerngrange * operator()
 			     (__urng, param_type(0, __urange / __uerngrange)));
 		    __ret = __tmp + (__uctype(__urng()) - __urngmin);

^ permalink raw reply	[flat|nested] 7+ messages in thread
end of thread, other threads:[~2020-11-04 10:38 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-29 14:59 [committed] libstdc++: Allow Lemire's algorithm to be used in more cases Jonathan Wakely
2020-11-03 21:28 ` Stephan Bergmann
2020-11-03 22:25   ` Jonathan Wakely
2020-11-04  8:45     ` Stephan Bergmann
2020-11-04  8:52       ` Ville Voutilainen
2020-11-04 10:15       ` Jonathan Wakely
2020-11-04 10:38         ` 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).