libstdc++: Optimize std::con/disjunction, __and_/__or_, etc

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

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

On Fri, 26 Aug 2022 at 14:45, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> 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

The standard probably *should* make it ill-formed, but currently it
makes it undefined, because it just says "shall be". Violating that
rule has undefined behaviour, so isn't required to be ill-formed. Our
implementations make it ill-formed, because that's just what happens
if we try to access Bi::value outside a SFINAE context, but I think

> whereas __and_v<int>/__or_v<int> are false/true respectively
> with this implementation (somewhat nonsensically).

Which is actually fine for something that the standard says is undefined.

Ill-formed is more user-friendly for the standardized
std::{con,dis}junction APIs than (potentially unbounded) UB, but
"somewhat nonsensical, but entirely well-defined" is perfectly fine
for our own internal helpers.

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

Yes, I *think* it's the case that we always pass sensible types into
them. There's a small risk in that I've sometimes used __and_ where
the standard requires conjunction, just because it saved one class
template instantiation to do so. But I think even in those cases, all
the type args are traits like is_assignable, which will always be
truthy. We should keep this edge case difference in mind for the
future though, and use std::{con,dis}junction if the difference might
matter.

The new implementations of __and_ and __or_ are very impressive. The
patch is OK for trunk, thanks!

Yesterday you mentioned changing conjunction_v to be defined in terms
of the cheaper __and_v in stead of conjunction::value. If we decide
there are some edge cases that would make that not equivalent, what we
could do is:

template<typename... B>
  inline constexpr conjunction_v = __detail::__conjunction_impl<B...>::value;

i.e. skip the step of instantiating std::conjunction::type and just
use that type directly.

But I think we should be able to just define it as __and_v<B...>
because [meta.logical]/4 makes that equivalent to
conjunction<B...>::value.