From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by sourceware.org (Postfix) with ESMTP id 9F50C3850434 for ; Wed, 4 Nov 2020 10:15:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 9F50C3850434 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-112-YS4eoN4vO0esP9p_slhmvQ-1; Wed, 04 Nov 2020 05:15:05 -0500 X-MC-Unique: YS4eoN4vO0esP9p_slhmvQ-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id C3F2A6414C; Wed, 4 Nov 2020 10:15:04 +0000 (UTC) Received: from localhost (unknown [10.33.36.7]) by smtp.corp.redhat.com (Postfix) with ESMTP id 2660A5D9EF; Wed, 4 Nov 2020 10:15:03 +0000 (UTC) Date: Wed, 4 Nov 2020 10:15:03 +0000 From: Jonathan Wakely To: Stephan Bergmann Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: Re: [committed] libstdc++: Allow Lemire's algorithm to be used in more cases Message-ID: <20201104101503.GA503596@redhat.com> References: <20201029145934.GA2368280@redhat.com> <05082673-9d71-116e-2ad8-d86e8b96e87f@redhat.com> <20201103222525.GZ503596@redhat.com> <51c2aa0b-7a1c-8174-6492-fdee634ef8e0@redhat.com> MIME-Version: 1.0 In-Reply-To: <51c2aa0b-7a1c-8174-6492-fdee634ef8e0@redhat.com> X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=iso-8859-1; format=flowed Content-Disposition: inline Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 04 Nov 2020 10:15:16 -0000 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 >>>>void f(std::default_random_engine e) { >>>>std::uniform_int_distribution{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::operator()>>>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::operator()>>>long, 16807, 0, 2147483647>>' requested here >>>>void f(std::default_random_engine e) { >>>>std::uniform_int_distribution{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::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