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

[Jonathan Wakely <jwakely@redhat.com>]

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.