Re: [committed] libstdc++: Allow Lemire's algorithm to be used in more cases

[Jonathan Wakely via Gcc-patches]

On 04/11/20 10:15 +0000, Jonathan Wakely wrote:

On 04/11/20 09:45 +0100, Stephan Bergmann via Libstdc++ wrote:

On 03/11/2020 23:25, Jonathan Wakely wrote:

On 03/11/20 22:28 +0100, Stephan Bergmann via Libstdc++ wrote:

On 29/10/2020 15:59, Jonathan Wakely via Gcc-patches wrote:

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.

At least with recent Clang trunk, this causes e.g.

$ cat test.cc
#include <random>

void f(std::default_random_engine e) { std::uniform_int_distribution<int>{0, 1}(e); }

to fail with

$ clang++ --gcc-toolchain=~/gcc/trunk/inst -std=c++17 -fsyntax-only test.cc

In file included from test.cc:1:
In file included from 
~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/random:40:

In file included from 
~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/string:52:

In file included from 
~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/stl_algo.h:66:

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:281:17: error: static_assert expression is not an integral constant expression

       static_assert( __urng.min() < __urng.max(),
                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:190:24: note: in instantiation of function template specialization 'std::uniform_int_distribution<int>::operator()<std::linear_congruential_engine<unsigned long, 16807, 0, 2147483647>>' requested here

       { return this->operator()(__urng, _M_param); }
                      ^

test.cc:2:80: note: in instantiation of function template specialization 'std::uniform_int_distribution<int>::operator()<std::linear_congruential_engine<unsigned long, 16807, 0, 2147483647>>' requested here void f(std::default_random_engine e) { std::uniform_int_distribution<int>{0, 1}(e); }

^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:281:17: note: function parameter '__urng' with unknown value cannot be used in a constant expression

       static_assert( __urng.min() < __urng.max(),
                      ^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:194:41: note: declared here

       operator()(_UniformRandomBitGenerator& __urng,
                                        
      ^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:284:21: error: constexpr variable '__urngmin' must be initialized by a constant expression

       constexpr __uctype __urngmin = __urng.min();
                          ^           
~~~~~~~~~~~~

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:284:33: note: function parameter '__urng' with unknown value cannot be used in a constant expression

       constexpr __uctype __urngmin = __urng.min();
                                      ^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:194:41: note: declared here

       operator()(_UniformRandomBitGenerator& __urng,
                                        
      ^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:285:21: error: constexpr variable '__urngmax' must be initialized by a constant expression

       constexpr __uctype __urngmax = __urng.max();
                          ^           
~~~~~~~~~~~~

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:285:33: note: function parameter '__urng' with unknown value cannot be used in a constant expression

       constexpr __uctype __urngmax = __urng.max();
                                      ^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:194:41: note: declared here

       operator()(_UniformRandomBitGenerator& __urng,
                                        
      ^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:286:21: error: constexpr variable '__urngrange' must be initialized by a constant expression

       constexpr __uctype __urngrange = __urngmax - __urngmin;
                          ^             
~~~~~~~~~~~~~~~~~~~~~

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:286:35: note: initializer of '__urngmax' is not a constant expression

       constexpr __uctype __urngrange = __urngmax - __urngmin;
                                        ^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:285:21: note: declared here

       constexpr __uctype __urngmax = __urng.max();
                          ^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:299:31: error: constexpr if condition is not a constant expression

           if _GLIBCXX17_CONSTEXPR (__urngrange == __UINT64_MAX__)
                                    
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:299:31: note: initializer of '__urngrange' is not a constant expression ~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:286:21: note: declared here

       constexpr __uctype __urngrange = __urngmax - __urngmin;
                          ^

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:308:31: error: constexpr if condition is not a constant expression

           if _GLIBCXX17_CONSTEXPR (__urngrange == __UINT32_MAX__)
                                    
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:308:31: note: initializer of '__urngrange' is not a constant expression ~/gcc/trunk/inst/lib/gcc/x86_64-pc-linux-gnu/11.0.0/../../../../include/c++/11.0.0/bits/uniform_int_dist.h:286:21: note: declared here

       constexpr __uctype __urngrange = __urngmax - __urngmin;
                          ^
6 errors generated.

which would be fixed by something like

diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h b/libstdc++-v3/include/bits/uniform_int_dist.h

index 524593bb984..d9c7ea96fda 100644
--- a/libstdc++-v3/include/bits/uniform_int_dist.h
+++ b/libstdc++-v3/include/bits/uniform_int_dist.h
@@ -278,11 +278,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef typename make_unsigned<result_type>::type __utype;

       typedef typename common_type<_Gresult_type, __utype>::type __uctype;

-       static_assert( __urng.min() < __urng.max(),

+       static_assert( _UniformRandomBitGenerator::min() < _UniformRandomBitGenerator::max(),

           "Uniform random bit generator must define min() < max()");
-       constexpr __uctype __urngmin = __urng.min();
-       constexpr __uctype __urngmax = __urng.max();

+       constexpr __uctype __urngmin = _UniformRandomBitGenerator::min(); +       constexpr __uctype __urngmax = _UniformRandomBitGenerator::max();

       constexpr __uctype __urngrange = __urngmax - __urngmin;
       const __uctype __urange
         = __uctype(__param.b()) - __uctype(__param.a());

(and I think there are further similar issues in this change).

I think this is a Clang bug, but I'll change the code anyway.

To me it looks like it boils down to disagreement between g++ and clang++ over

struct S { static constexpr int f() { return 0; } };
void f(S & s) { static_assert(s.f(), ""); }

where I think Clang might be right in rejecting it based on [expr.const] "An expression e is a core constant expression unless [...] an id-expression that refers to a variable or data member of reference type unless the reference has a preceding initialization [...]"

GCC, Intel icc and MSVC all accept it:

 https://godbolt.org/z/hTsT96

But EDG rejects it without the --g++ option (which is the mode icc
uses on GNU/Linux, I believe).

I've pushed a slightly different fix (I didn't see your patch at the
bottom of the first email until after I'd already done this version).

Tested powerpc64le-linux, committed to trunk.


commit 24366207b77481bceebb425569932297c441e04e
Author: Jonathan Wakely <jwak...@redhat.com>
Date:   Wed Nov 4 10:36:45 2020

    libstdc++: Fix constant expressions in std::uniform_int_distribution
    
    Clang and EDG say the class member access expressions __urng.min() and
    __urng.max() are not constant expressions, because the object expression
    __urng is not usable in a constant expresion. Use a qualified-id to call
    those static member functions instead.
    
    Co-authored-by: Stephan Bergmann <sberg...@redhat.com>
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/uniform_int_dist.h (uniform_int_distribution::_S_nd):
            Use qualified-id to refer to static member functions.

diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h b/libstdc++-v3/include/bits/uniform_int_dist.h
index 524593bb9847..8f02b85c9bb0 100644
--- a/libstdc++-v3/include/bits/uniform_int_dist.h
+++ b/libstdc++-v3/include/bits/uniform_int_dist.h
@@ -278,12 +278,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	typedef typename make_unsigned<result_type>::type __utype;
 	typedef typename common_type<_Gresult_type, __utype>::type __uctype;
 
-	static_assert( __urng.min() < __urng.max(),
+	constexpr __uctype __urngmin = _UniformRandomBitGenerator::min();
+	constexpr __uctype __urngmax = _UniformRandomBitGenerator::max();
+	static_assert( __urngmin < __urngmax,
 	    "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());