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 [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 89E043858427 for ; Fri, 26 Aug 2022 13:44:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 89E043858427 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1661521493; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=+sFIsBo6dsckx0o3Aq+UsiwQCj7gpjBxwlt6idYTcuo=; b=SwTxrBP5gC3lzbetRSag7mtK0hIf+FYZOdMfF/wVolD/r1bx/ZUqE5Gm9BFysigmtjXO43 Gwr+BLpVyrXShv5TIy1tEQXrmSK+wY4YQQetPyzwSjzYQ0By8ZGll62Q7LFCUHmUU4aNEI mhHtUnW71kqfPatz+8Ruju/os5+0wdY= Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-610-mC4hrc9jPVuNyGlAq2WkuQ-1; Fri, 26 Aug 2022 09:44:52 -0400 X-MC-Unique: mC4hrc9jPVuNyGlAq2WkuQ-1 Received: by mail-qk1-f197.google.com with SMTP id n15-20020a05620a294f00b006b5768a0ed0so1259722qkp.7 for ; Fri, 26 Aug 2022 06:44:52 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:references:message-id:in-reply-to:subject:cc:to:date :from:x-gm-message-state:from:to:cc; bh=+sFIsBo6dsckx0o3Aq+UsiwQCj7gpjBxwlt6idYTcuo=; b=BqC2ahwts26az6Y1kHuqnZRtWLsgvsaOt0J06vAA7pK2a8IUTlOSfKrLEn0C7sXP0s jGFq7ErcGEpsaOz8hPN+0AbbP06GstcfNHlSZl531t+R7jHC1A15u8pRvON4L8PKWC/o gao5RjBNzoJB2lp19Ea5gYL8FyE24CCRh1+U/G514vFaVHNvbQQ7Y+qqbfjYM849fntz 5aiE5R9OkMpNP4tgw2uLrSeXw8pQhx3kQu4oHsrJTvWX9hKYx7IBRMR/ZMVAjaUocjAV WXR/tkmxIvdZjIngjmw0Ue8d8jvHfIaWL0ChmX3LsKCpOR94auKFPhkbQXQyOgXqTdmC B7kw== X-Gm-Message-State: ACgBeo1J8fVJWt2wr/z7tV3MRU5uh3v2TQTOx9+RdyejP955aMV96iMY Ubu8XxXlEicCBrJT4jPxlJ5hnGnOwYFyONl/mJHLYaoiTqHj+qYa/sRRqw0FwbLXh5JGi+NuEua 3ot5YQ4bw1VG7bRY= X-Received: by 2002:ac8:570e:0:b0:344:88d7:5ee3 with SMTP id 14-20020ac8570e000000b0034488d75ee3mr7716906qtw.522.1661521491594; Fri, 26 Aug 2022 06:44:51 -0700 (PDT) X-Google-Smtp-Source: AA6agR4cx4Qd1E4i4Ool28x9POtEVK97lckvYwyJ1lXHTiMV57s1pu7Q5fqSm8oETFr8WRNtMKT9Qw== X-Received: by 2002:ac8:570e:0:b0:344:88d7:5ee3 with SMTP id 14-20020ac8570e000000b0034488d75ee3mr7716891qtw.522.1661521491266; Fri, 26 Aug 2022 06:44:51 -0700 (PDT) Received: from [192.168.1.130] (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id i8-20020a05620a150800b006b928ba8989sm1663750qkk.23.2022.08.26.06.44.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 26 Aug 2022 06:44:50 -0700 (PDT) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Fri, 26 Aug 2022 09:44:50 -0400 (EDT) To: Patrick Palka cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Subject: Re: [PATCH] libstdc++: Optimize std::con/disjunction, __and_/__or_, etc In-Reply-To: <20220824194013.2035464-1-ppalka@redhat.com> Message-ID: <1096f2fe-28df-ad54-8f74-95a12a32c79d@idea> References: <20220824194013.2035464-1-ppalka@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-14.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Wed, 24 Aug 2022, Patrick Palka wrote: > The internal type-level logical operations __and_ and __or_ are > currently quite slow to compile for a couple of reasons: > > 1. They are drop-in replacements for std::con/disjunction, which > are rigidly specified to form a type that derives from the first > type argument that caused the overall computation to short-circuit. > In practice this inheritance property seems to be rarely needed; > usually all we care about is the value of the overall expression. > 2. Their recursive implementations instantiate up to ~N class templates > and form up to a depth ~N inheritance chain. > > This patch does away with this inheritance property of __and_ and __or_ > (which seems to be unneeded in the library except indirectly by > std::con/disjunction) and redefines them as alias templates that yield > either false_type or true_type via SFINAE and overload resolution of a > pair of function templates. Another difference between this implementation of __and_/__or_ and std::con/disjunction is the handling of invalid/non-"truthy" operands. The standard makes this ill-formed ([meta.logical]/4), whereas this implementation of __and_/__or_ silently treats such an operand as if it were false_type/true_type respectively. Thus e.g. std::conjunction_v and std::disjunction_v are both ill-formed whereas __and_v/__or_v are false/true respectively with this implementation (somewhat nonsensically). Though I'm not sure if this corner case is relevant for our current internal uses of __and_/__or_, which all seem to pass in "truthy" operands. > > As for std::con/disjunction, it seems we need to keep defining them in > terms of recursive class templates for sake of the inheritance property. > But in the recursive step, instead of using inheritance which would > yield a depth ~N inheritance chain, use a recursive member typedef which > gets immediately flattened. Thus a specialization of conjunction and > disjunction now has depth ~1 instead of up to ~N. > > In passing, redefine __not_ as an alias template for consistency with > __and_ and __or_, and to remove a layer of indirection. > > Together these changes have a substantial effect on compile time and > memory usage for code that indirectly makes heavy use of these internal > type traits. For example, for the following which tests constructibility > between two compatible 257-element tuple types > > #include > > struct A { A(int); }; > > #define M(x) x, x > > using ty1 = std::tuple; > using ty2 = std::tuple; > > static_assert(std::is_constructible_v); > > memory usage improves by ~27% from 440MB to 320M and compile time > improves by ~20% from ~2s to ~1.6s (with -std=c++23). > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for > trunk? > > libstdc++-v3/ChangeLog: > > * include/std/type_traits (enable_if, __enable_if_t): Move up > their definitions. > (__detail::__first_t): Define. > (__detail::__or_fn, __detail::__and_fn): Declare. > (__or_, __and_): Redefine as alias templates in terms of __or_fn > and __and_fn. > (__not_): Redefine as an alias template. > (__detail::__disjunction_impl, __detail::__conjunction_impl): > Define. > (conjuction, disjunction): Redefine in terms of __disjunction_impl > and __conjunction_impl. > --- > libstdc++-v3/include/std/type_traits | 152 ++++++++++++++++----------- > 1 file changed, 93 insertions(+), 59 deletions(-) > > diff --git a/libstdc++-v3/include/std/type_traits b/libstdc++-v3/include/std/type_traits > index 14b029cec64..07a50a31e86 100644 > --- a/libstdc++-v3/include/std/type_traits > +++ b/libstdc++-v3/include/std/type_traits > @@ -100,6 +100,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > // Metaprogramming helper types. > > + // Primary template. > + /// Define a member typedef `type` only if a boolean constant is true. > + template > + struct enable_if > + { }; > + > + // Partial specialization for true. > + template > + struct enable_if > + { typedef _Tp type; }; > + > + // __enable_if_t (std::enable_if_t for C++11) > + template > + using __enable_if_t = typename enable_if<_Cond, _Tp>::type; > + > template > struct __conditional > { > @@ -127,56 +142,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > template > using __type_identity_t = typename __type_identity<_Tp>::type; > > - template > - struct __or_; > - > - template<> > - struct __or_<> > - : public false_type > - { }; > + namespace __detail > + { > + // A variadic alias template that resolves to its first argument. > + template > + using __first_t = _Tp; > > - template > - struct __or_<_B1> > - : public _B1 > - { }; > + // These are deliberately not defined. > + template > + auto __or_fn(int) -> __first_t + __enable_if_t...>; > > - template > - struct __or_<_B1, _B2> > - : public __conditional_t<_B1::value, _B1, _B2> > - { }; > + template > + auto __or_fn(...) -> true_type; > > - template > - struct __or_<_B1, _B2, _B3, _Bn...> > - : public __conditional_t<_B1::value, _B1, __or_<_B2, _B3, _Bn...>> > - { }; > + template > + auto __and_fn(int) -> __first_t + __enable_if_t<_Bn::value>...>; > > - template > - struct __and_; > + template > + auto __and_fn(...) -> false_type; > + } // namespace detail > > - template<> > - struct __and_<> > - : public true_type > - { }; > - > - template > - struct __and_<_B1> > - : public _B1 > - { }; > - > - template > - struct __and_<_B1, _B2> > - : public __conditional_t<_B1::value, _B2, _B1> > - { }; > + // Like C++17 std::dis/conjunction, but usable in C++11 and resolves > + // to either true_type or false_type which allows for a more efficient > + // implementation that avoids instantiating any class templates. > + template > + using __or_ = decltype(__detail::__or_fn<_Bn...>(0)); > > - template > - struct __and_<_B1, _B2, _B3, _Bn...> > - : public __conditional_t<_B1::value, __and_<_B2, _B3, _Bn...>, _B1> > - { }; > + template > + using __and_ = decltype(__detail::__and_fn<_Bn...>(0)); > > template > - struct __not_ > - : public __bool_constant > - { }; > + using __not_ = __bool_constant; > /// @endcond > > #if __cplusplus >= 201703L > @@ -186,18 +184,69 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > inline constexpr bool __or_v = __or_<_Bn...>::value; > template > inline constexpr bool __and_v = __and_<_Bn...>::value; > + > + namespace __detail > + { > + template > + struct __disjunction_impl; > + > + template<> > + struct __disjunction_impl<> > + { using type = false_type; }; > + > + template > + struct __disjunction_impl<_B1> > + { using type = _B1; }; > + > + template > + struct __disjunction_impl<_B1, _B2> > + { using type = __conditional_t<_B1::value, _B1, _B2>; }; > + > + template > + struct __disjunction_impl<_B1, _B2, _B3, _Bn...> > + { > + using type > + = __conditional_t<_B1::value, > + _B1, > + typename __disjunction_impl<_B2, _B3, _Bn...>::type>; > + }; > + > + template > + struct __conjunction_impl; > + > + template<> > + struct __conjunction_impl<> > + { using type = true_type; }; > + > + template > + struct __conjunction_impl<_B1> > + { using type = _B1; }; > + > + template > + struct __conjunction_impl<_B1, _B2> > + { using type = __conditional_t<_B1::value, _B2, _B1>; }; > + > + template > + struct __conjunction_impl<_B1, _B2, _B3, _Bn...> > + { > + using type > + = __conditional_t<_B1::value, > + typename __conjunction_impl<_B2, _B3, _Bn...>::type, > + _B1>; > + }; > + } // namespace __detail > /// @endcond > > #define __cpp_lib_logical_traits 201510L > > template > struct conjunction > - : __and_<_Bn...> > + : __detail::__conjunction_impl<_Bn...>::type > { }; > > template > struct disjunction > - : __or_<_Bn...> > + : __detail::__disjunction_impl<_Bn...>::type > { }; > > template > @@ -2219,23 +2268,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > using __decay_and_strip = __strip_reference_wrapper<__decay_t<_Tp>>; > /// @endcond > > - // Primary template. > - /// Define a member typedef `type` only if a boolean constant is true. > - template > - struct enable_if > - { }; > - > - // Partial specialization for true. > - template > - struct enable_if > - { typedef _Tp type; }; > - > /// @cond undocumented > > - // __enable_if_t (std::enable_if_t for C++11) > - template > - using __enable_if_t = typename enable_if<_Cond, _Tp>::type; > - > // Helper for SFINAE constraints > template > using _Require = __enable_if_t<__and_<_Cond...>::value>; > -- > 2.37.2.382.g795ea8776b > >