libstdc++: Optimize std::con/disjunction, __and_/__or_, etc
authorPatrick Palka <ppalka@redhat.com>
Fri, 26 Aug 2022 19:10:57 +0000 (15:10 -0400)
committerPatrick Palka <ppalka@redhat.com>
Fri, 26 Aug 2022 19:10:57 +0000 (15:10 -0400)
commit390f94eee1ae694901f896ac45bfb148f8126baa
tree563ba23364843bdc1aa9aae98490a45da484d1ee
parent1d3145360f95910f0661da0364b91dc7962d44fa
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 <tuple>

  #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)))))))), long>;

  static_assert(std::is_constructible_v<ty2, ty1>);

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.
libstdc++-v3/include/std/type_traits