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

Wed, 04 Nov 2020 02:16:02 -0800 

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
(By the way, when looking into the original issue, what puzzles me is: IIUC, `_UniformRandomBitGenerator& __urng` must meet the uniform random big generator requirements, [rand.req.urng]: a table of requirements in C++17, concept uniform_random_bit_generator in C++20. For one, that only requires G::min() but not g.min(). What if G::min is defined as `using min = result_type`? For another, what guarantees that G::min() is a constant expression? The C++17 table mentions "Complexity: compile-time", and the C++20 concept contains `requires bool_constant<(G::min() < G::max())>::value;`. Is each of those enough to imply the constant expression requirement?) 

The C++20 requirement is exactly requiring constant expressions,
otherwise you can't use them as template arguments. It wasn't clear in
C++17 but the intent was always to require them to be constant
expressions.

I mentioned this in the commit log of the commit that broke clang:

    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).

See https://cplusplus.github.io/LWG/issue2154

Reply via email to