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

[Jonathan Wakely <jwakely@redhat.com>]

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

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.


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

commit 24366207b77481bceebb425569932297c441e04e
Author: Jonathan Wakely <jwakely@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 <sbergman@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());