From patchwork Wed Aug 24 19:40:13 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 745 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:ecc5:0:0:0:0:0 with SMTP id s5csp1575785wro; Wed, 24 Aug 2022 12:41:22 -0700 (PDT) X-Google-Smtp-Source: AA6agR7vUVvh9U+yTHKTuZ7SttQUkJ5mDHoa3iqTBLXX1ThTPcetYUuxf/D1cWvFkSj/hp5qw4Bi X-Received: by 2002:a05:6402:3585:b0:446:9d7b:2e38 with SMTP id y5-20020a056402358500b004469d7b2e38mr464899edc.248.1661370082749; Wed, 24 Aug 2022 12:41:22 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1661370082; cv=none; d=google.com; s=arc-20160816; b=dcOpdcgPwHS2RrzT4MT4OEzGLeYFEgw/c8gKUhrSRccCJhWKr3BTffWGWy7P1UxlxK wPLhDiV2xhMKSr5C8XXWjiKz2ASn+OiEl9AeIcPZuXB1XcHvizsT90RvmBEkH8Ez9zag WdknxGHqSQU2Krhs/NviZnbQhQ7EHSa4/y6oqAkW1mv/7y5/La2IshC4SoTfkJCaNtxi wGmuq5gZ6IvExcKhcUR6WkWOmqS6rnLihJ6R/qgX4wHsdblF9NTWcd4HCANzJuTt6EvB 0VQlQTdsqo7xQWKLfG416nn3jeGncuCO78UprUifqjzoiFWHd+/gQJIG0MKvf5DgI5/u oQvQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:message-id:date:subject:to :dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=X0YVNdK41c4VPfy9SgcmbXouJF0D02El6OVizrISSY0=; b=so9b3IALIWqugNdnqnWoP80nJvgb2sqggqYkJPYSiQ8Ge7yxb2ZeiZ8LUq+ExcKerJ J/d3vzYhoPf4A/WvFbI0b3wE4+y8TEa9cW5CLF1SRHfpaBHuFlM86d4RBnDDRXDtSIlR MzA4aigbLyBNsSAZg2J0De3IYiyEluC1LiUpyxuDJfahBHrqPoIOkLBe8a/Rkw/T+qZg za7uaVaBrToGapvxxmobiSkHkgovhXRG1mayvdVE2+LPhmgcsyAnqgIrBuDOwSlavOve ZvTU4Szv+ET4McCwAujculKmGbwMaTgdpWRQvw23RNB67tWtZRSNqCw9UT+b/IvNfuSU 7X3g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=Xn4RtvDL; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id bg14-20020a170906a04e00b00731646a574esi2331435ejb.839.2022.08.24.12.41.22 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 24 Aug 2022 12:41:22 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=Xn4RtvDL; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 81B5938515D0 for ; Wed, 24 Aug 2022 19:41:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 81B5938515D0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661370065; bh=X0YVNdK41c4VPfy9SgcmbXouJF0D02El6OVizrISSY0=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=Xn4RtvDLtIY1U4RYTuGkHIyVQ8lilGI1hs1DqQbXTWI8o79KPawfz1TPlR92sWRYx nqi6KkP8TMn4Jqrk8k/MHAhYndfMbXIWglJMk2b+Y2aeF7yyv9mHhJQMKK8PrTZmrv 1LEINc4ddV8PI4zd+niJGZLd7+yLLiAszl3oZTAk= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 30F5C3858C33 for ; Wed, 24 Aug 2022 19:40:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 30F5C3858C33 Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-118-HeiVlTG3PYSIForrQwwK_w-1; Wed, 24 Aug 2022 15:40:19 -0400 X-MC-Unique: HeiVlTG3PYSIForrQwwK_w-1 Received: by mail-qt1-f197.google.com with SMTP id y12-20020ac8708c000000b00342f1bb8428so13512395qto.5 for ; Wed, 24 Aug 2022 12:40:19 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc; bh=X0YVNdK41c4VPfy9SgcmbXouJF0D02El6OVizrISSY0=; b=oum4U9Byb/vtF/l5toO2vwf6MEHQt/XRIU9oslbfcX7G3DGrbrbyCf0prak7V7zT8j XjV+pXij2ayw5BQTaiuXmLCPsSbcf4Y7mTU99fEDxPJDMmIm5a9TSFj8YWyyjlIsPleN QlwYfqWyxhLH5+h62Gb9BDeTVz+R4JGFvT2NDteGrS3ymRbVVvSeLiPIwFsoKSbZD2Oo yFMl9L29LJGmDz8j5g/ey63QPzMQ0QYZMjNTGkR0b2jqicsFT/359cfQlxwoXxsaQjZO OdGWpENcvcAdbttIJRI1iUsK6xXNvtPvYwlD3NtUrnJ5rz1fzGanzY/Hl6gqgAzoiUks JaOg== X-Gm-Message-State: ACgBeo35RH9ClNE0VHF9jNBhGzmarf2bh252eh3UyvhLvulk9oHYPOav DJWvRp0pP4A6InUrPjTHFQftiXOgRwlqAx+uZO5Vw5nAxK9JDKC5OL3JJ3pbGZuCsT0QJaJsO+l u0YrAVBH3ZY3hthIcVJZCoBzHdhc7ze5afyjto3Hput4yD55KRiq4y4dNUYGO0Gg9P9Q= X-Received: by 2002:a05:620a:46a2:b0:6bb:29c9:57e0 with SMTP id bq34-20020a05620a46a200b006bb29c957e0mr628451qkb.621.1661370019004; Wed, 24 Aug 2022 12:40:19 -0700 (PDT) X-Received: by 2002:a05:620a:46a2:b0:6bb:29c9:57e0 with SMTP id bq34-20020a05620a46a200b006bb29c957e0mr628430qkb.621.1661370018554; Wed, 24 Aug 2022 12:40:18 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id hg17-20020a05622a611100b0034359fc348fsm12846369qtb.73.2022.08.24.12.40.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 24 Aug 2022 12:40:18 -0700 (PDT) To: gcc-patches@gcc.gnu.org Subject: [PATCH] libstdc++: Optimize std::con/disjunction, __and_/__or_, etc Date: Wed, 24 Aug 2022 15:40:13 -0400 Message-Id: <20220824194013.2035464-1-ppalka@redhat.com> X-Mailer: git-send-email 2.37.2.382.g795ea8776b MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.9 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 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-Patchwork-Original-From: Patrick Palka via Gcc-patches From: Patrick Palka Reply-To: Patrick Palka Cc: libstdc++@gcc.gnu.org Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1742072795676769432?= X-GMAIL-MSGID: =?utf-8?q?1742072795676769432?= 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. 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...>; - 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...>; - 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>;