From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1888) id 183C138515CE; Fri, 26 Aug 2022 19:11:57 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 183C138515CE DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661541117; bh=tjzuXZuI88PNSt3ZBHRFJEWRIKlxuyZlbTvw8Flhtho=; h=From:To:Subject:Date:From; b=dc+iigVTTryRBmx5nLbDaBkxL+Ue2gQqPT+qxNrPORB2wiUtLbJdCRO4meidXU4mb PIYGOpYxiiaAp5EwsbbOHYJ9B5s8CsC+3dWrR19wQYDpDP4Hfs0Y2ZuFS8CFtGOPPI HtLBEEwvj7odqEF8Kvaii+0uIK27Pj+g2Im6OD70= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Patrick Palka To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r13-2230] libstdc++: Optimize std::con/disjunction, __and_/__or_, etc X-Act-Checkin: gcc X-Git-Author: Patrick Palka X-Git-Refname: refs/heads/master X-Git-Oldrev: 1d3145360f95910f0661da0364b91dc7962d44fa X-Git-Newrev: 390f94eee1ae694901f896ac45bfb148f8126baa Message-Id: <20220826191157.183C138515CE@sourceware.org> Date: Fri, 26 Aug 2022 19:11:57 +0000 (GMT) List-Id: https://gcc.gnu.org/g:390f94eee1ae694901f896ac45bfb148f8126baa commit r13-2230-g390f94eee1ae694901f896ac45bfb148f8126baa Author: Patrick Palka Date: Fri Aug 26 15:10:57 2022 -0400 libstdc++: Optimize std::con/disjunction, __and_/__or_, etc The internal type-level logical operator traits __and_ and __or_ seem to have high overhead 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 result. 2. Their recursive implementations instantiate O(N) class templates and form an inheritance chain of depth O(N). This patch gets rid of this inheritance property of __and_ and __or_ (which seems to be unneeded in the library except indirectly by std::con/disjunction) which allows us to redefine them non-recursively as alias templates that yield either false_type or true_type via enable_if_t and partial ordering of a pair of function templates (alternatively we could use an equivalent partially specialized class template, but using function templates appears to be slightly more efficient). As for std::con/disjunction, it seems we need to keep implementing them via a recursive class template for sake of the inheritance property. But instead of using inheritance recursion, use a recursive member typedef that gets immediately flattened, so that specializations thereof now have O(1) instead of O(N) inheritance depth. 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 heavily uses these internal type traits. For the following example (which tests constructibility between two compatible 257-element tuple types): #include #define M(x) x, x using ty1 = std::tuple; using ty2 = std::tuple; static_assert(std::is_constructible_v); memory usage improves ~27% from 440MB to 320MB and compile time improves ~20% from ~2s to ~1.6s (with -std=c++23). libstdc++-v3/ChangeLog: * include/std/type_traits (enable_if, __enable_if_t): Define them earlier. (__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. Diff: --- libstdc++-v3/include/std/type_traits | 130 +++++++++++++++++++---------------- 1 file changed, 71 insertions(+), 59 deletions(-) diff --git a/libstdc++-v3/include/std/type_traits b/libstdc++-v3/include/std/type_traits index 14b029cec64..c2f5cb9c806 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 - { }; - - template - struct __or_<_B1> - : public _B1 - { }; - - template - struct __or_<_B1, _B2> - : public __conditional_t<_B1::value, _B1, _B2> - { }; + namespace __detail + { + // A variadic alias template that resolves to its first argument. + template + using __first_t = _Tp; - template - struct __or_<_B1, _B2, _B3, _Bn...> - : public __conditional_t<_B1::value, _B1, __or_<_B2, _B3, _Bn...>> - { }; + // These are deliberately not defined. + template + auto __or_fn(int) -> __first_t...>; - template - struct __and_; + template + auto __or_fn(...) -> true_type; - template<> - struct __and_<> - : public true_type - { }; + template + auto __and_fn(int) -> __first_t...>; - template - struct __and_<_B1> - : public _B1 - { }; + template + auto __and_fn(...) -> false_type; + } // namespace detail - 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 recursive class template instantiation. + 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,47 @@ _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 + { using type = _B1; }; + + template + struct __disjunction_impl<__enable_if_t, _B1, _B2, _Bn...> + { using type = typename __disjunction_impl::type; }; + + template + struct __conjunction_impl + { using type = _B1; }; + + template + struct __conjunction_impl<__enable_if_t, _B1, _B2, _Bn...> + { using type = typename __conjunction_impl::type; }; + } // namespace __detail /// @endcond #define __cpp_lib_logical_traits 201510L template struct conjunction - : __and_<_Bn...> + : __detail::__conjunction_impl::type + { }; + + template<> + struct conjunction<> + : true_type { }; template struct disjunction - : __or_<_Bn...> + : __detail::__disjunction_impl::type + { }; + + template<> + struct disjunction<> + : false_type { }; template @@ -2219,23 +2246,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>;