| Message ID | 20201029145934.GA2368280@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | [committed] libstdc++: Allow Lemire's algorithm to be used in more cases | expand |
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).
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.
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 [...]" (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?)
On Wed, 4 Nov 2020 at 10:46, Stephan Bergmann via Libstdc++ <libstdc++@gcc.gnu.org> wrote: > 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 [...]" There's more to it than that. It's a disagreement over [expr.ref]/1. For a static member call, gcc just plain doesn't evaluate the s in s.f(). But [expr.ref]/1 says it's evaluated, and since it's not a constant expression, clang rejects it, and gcc accepts it. That's why your fix works; it removes the use of the otherwise-mostly-ignored object expression for a call to a static member function. So, I think gcc is accepting-invalid here, and we should just apply the fix you suggested.
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
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.
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);
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. 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.