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 3ACCF38708B2 for ; Wed, 4 Nov 2020 08:45:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 3ACCF38708B2 Received: from mail-wm1-f71.google.com (mail-wm1-f71.google.com [209.85.128.71]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-430-Ek1LSr4VM3ykQjOswfgdmw-1; Wed, 04 Nov 2020 03:45:23 -0500 X-MC-Unique: Ek1LSr4VM3ykQjOswfgdmw-1 Received: by mail-wm1-f71.google.com with SMTP id t201so942727wmt.1 for ; Wed, 04 Nov 2020 00:45:23 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=10Pu5CoGCDdXpnsJFqCayD1ZIgDjQ03z2JXDhydQXOQ=; b=ptZuStQgxpBv4PUcreaZyu7EW05wC2r4db9CmCs7WjD/npkZl0/cD6PxrvbWiQqFmO 0giWlJQ+wW+OnEIWZ7POqTJBbjg7z19pQ9KjgzsTe9CeiYKXgyXmVznVgTP2vCDJce78 AmMUAxnQR2h9axzDHPM2SZI3brivGR6Lcs5+rIPOx1wqoItpBLkG95bGTZWQbt3Kf50q cMeqj4XFglrwKUVGkx6Q6cl/NTlJyD0mrsncuHvDlkiP0FwG5/9TDylpZfgsHGxzX+aG +UXlJtFtvp5A3Nf2wTkAEup+ieIg0JnjSLXDbV/doBQ4lGNzP7Hjdcgec8nqdDG2rr9W hY9A== X-Gm-Message-State: AOAM532giid/9+GQL/X/Vq/RmuWk77bIFC3bofEexMNKtZMfoTOKRBXx 0UlVSQ0tNlhAlxQ0DD8Vy+HanwAuIn+/lEqtZ3sl2AtPTyTVzOcG716BkZGlnpZzIF8P4NXFIIu oZ5J7HIOscLoe/Rw= X-Received: by 2002:a5d:61c9:: with SMTP id q9mr31219376wrv.395.1604479522155; Wed, 04 Nov 2020 00:45:22 -0800 (PST) X-Google-Smtp-Source: ABdhPJwfZxcw3VhA0bzrg/mWlmGVJO4F7JudcA9m/1kOoL+uqxb7YnrCZKmbXScNbIHjJuJpF1r8hQ== X-Received: by 2002:a5d:61c9:: with SMTP id q9mr31219340wrv.395.1604479521746; Wed, 04 Nov 2020 00:45:21 -0800 (PST) Received: from [192.168.188.47] (dynamic-077-008-045-072.77.8.pool.telefonica.de. [77.8.45.72]) by smtp.gmail.com with ESMTPSA id e7sm1624958wrm.6.2020.11.04.00.45.20 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 04 Nov 2020 00:45:21 -0800 (PST) Subject: Re: [committed] libstdc++: Allow Lemire's algorithm to be used in more cases To: Jonathan Wakely Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org References: <20201029145934.GA2368280@redhat.com> <05082673-9d71-116e-2ad8-d86e8b96e87f@redhat.com> <20201103222525.GZ503596@redhat.com> From: Stephan Bergmann Message-ID: <51c2aa0b-7a1c-8174-6492-fdee634ef8e0@redhat.com> Date: Wed, 4 Nov 2020 09:45:20 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.3.1 MIME-Version: 1.0 In-Reply-To: <20201103222525.GZ503596@redhat.com> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-10.4 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, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=unavailable autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 04 Nov 2020 08:45:34 -0000 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 [...]" (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?)