Re: [PATCH] libstdc++: Optimize std::con/disjunction, __and_/__or_, etc

[Patrick Palka <ppalka@redhat.com>]

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
> 
>