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<int> and std::disjunction_v<int> are both
ill-formed whereas __and_v<int>/__or_v<int> 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 <tuple>
>
> struct A { A(int); };
>
> #define M(x) x, x
>
> using ty1 = std::tuple<M(M(M(M(M(M(M(M(int)))))))), int>;
> using ty2 = std::tuple<M(M(M(M(M(M(M(M(int)))))))), A>;
>
> static_assert(std::is_constructible_v<ty2, ty1>);
>
> 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<bool, typename _Tp = void>
> + struct enable_if
> + { };
> +
> + // Partial specialization for true.
> + template<typename _Tp>
> + struct enable_if<true, _Tp>
> + { typedef _Tp type; };
> +
> + // __enable_if_t (std::enable_if_t for C++11)
> + template<bool _Cond, typename _Tp = void>
> + using __enable_if_t = typename enable_if<_Cond, _Tp>::type;
> +
> template<bool>
> struct __conditional
> {
> @@ -127,56 +142,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> template<typename _Tp>
> using __type_identity_t = typename __type_identity<_Tp>::type;
>
> - template<typename...>
> - struct __or_;
> -
> - template<>
> - struct __or_<>
> - : public false_type
> - { };
> + namespace __detail
> + {
> + // A variadic alias template that resolves to its first argument.
> + template<typename _Tp, typename...>
> + using __first_t = _Tp;
>
> - template<typename _B1>
> - struct __or_<_B1>
> - : public _B1
> - { };
> + // These are deliberately not defined.
> + template<typename... _Bn>
> + auto __or_fn(int) -> __first_t<false_type,
> + __enable_if_t<!bool(_Bn::value)>...>;
>
> - template<typename _B1, typename _B2>
> - struct __or_<_B1, _B2>
> - : public __conditional_t<_B1::value, _B1, _B2>
> - { };
> + template<typename... _Bn>
> + auto __or_fn(...) -> true_type;
>
> - template<typename _B1, typename _B2, typename _B3, typename... _Bn>
> - struct __or_<_B1, _B2, _B3, _Bn...>
> - : public __conditional_t<_B1::value, _B1, __or_<_B2, _B3, _Bn...>>
> - { };
> + template<typename... _Bn>
> + auto __and_fn(int) -> __first_t<true_type,
> + __enable_if_t<_Bn::value>...>;
>
> - template<typename...>
> - struct __and_;
> + template<typename... _Bn>
> + auto __and_fn(...) -> false_type;
> + } // namespace detail
>
> - template<>
> - struct __and_<>
> - : public true_type
> - { };
> -
> - template<typename _B1>
> - struct __and_<_B1>
> - : public _B1
> - { };
> -
> - template<typename _B1, typename _B2>
> - 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<typename... _Bn>
> + using __or_ = decltype(__detail::__or_fn<_Bn...>(0));
>
> - template<typename _B1, typename _B2, typename _B3, typename... _Bn>
> - struct __and_<_B1, _B2, _B3, _Bn...>
> - : public __conditional_t<_B1::value, __and_<_B2, _B3, _Bn...>, _B1>
> - { };
> + template<typename... _Bn>
> + using __and_ = decltype(__detail::__and_fn<_Bn...>(0));
>
> template<typename _Pp>
> - struct __not_
> - : public __bool_constant<!bool(_Pp::value)>
> - { };
> + using __not_ = __bool_constant<!bool(_Pp::value)>;
> /// @endcond
>
> #if __cplusplus >= 201703L
> @@ -186,18 +184,69 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> inline constexpr bool __or_v = __or_<_Bn...>::value;
> template<typename... _Bn>
> inline constexpr bool __and_v = __and_<_Bn...>::value;
> +
> + namespace __detail
> + {
> + template<typename...>
> + struct __disjunction_impl;
> +
> + template<>
> + struct __disjunction_impl<>
> + { using type = false_type; };
> +
> + template<typename _B1>
> + struct __disjunction_impl<_B1>
> + { using type = _B1; };
> +
> + template<typename _B1, typename _B2>
> + struct __disjunction_impl<_B1, _B2>
> + { using type = __conditional_t<_B1::value, _B1, _B2>; };
> +
> + template<typename _B1, typename _B2, typename _B3, typename... _Bn>
> + struct __disjunction_impl<_B1, _B2, _B3, _Bn...>
> + {
> + using type
> + = __conditional_t<_B1::value,
> + _B1,
> + typename __disjunction_impl<_B2, _B3,
> _Bn...>::type>;
> + };
> +
> + template<typename...>
> + struct __conjunction_impl;
> +
> + template<>
> + struct __conjunction_impl<>
> + { using type = true_type; };
> +
> + template<typename _B1>
> + struct __conjunction_impl<_B1>
> + { using type = _B1; };
> +
> + template<typename _B1, typename _B2>
> + struct __conjunction_impl<_B1, _B2>
> + { using type = __conditional_t<_B1::value, _B2, _B1>; };
> +
> + template<typename _B1, typename _B2, typename _B3, typename... _Bn>
> + 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<typename... _Bn>
> struct conjunction
> - : __and_<_Bn...>
> + : __detail::__conjunction_impl<_Bn...>::type
> { };
>
> template<typename... _Bn>
> struct disjunction
> - : __or_<_Bn...>
> + : __detail::__disjunction_impl<_Bn...>::type
> { };
>
> template<typename _Pp>
> @@ -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<bool, typename _Tp = void>
> - struct enable_if
> - { };
> -
> - // Partial specialization for true.
> - template<typename _Tp>
> - struct enable_if<true, _Tp>
> - { typedef _Tp type; };
> -
> /// @cond undocumented
>
> - // __enable_if_t (std::enable_if_t for C++11)
> - template<bool _Cond, typename _Tp = void>
> - using __enable_if_t = typename enable_if<_Cond, _Tp>::type;
> -
> // Helper for SFINAE constraints
> template<typename... _Cond>
> using _Require = __enable_if_t<__and_<_Cond...>::value>;
> --
> 2.37.2.382.g795ea8776b
>
>
