public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] libstdc++: Fix laziness of __and/or/not_
@ 2022-09-02 13:18 Patrick Palka
  2022-09-02 13:34 ` Patrick Palka
  0 siblings, 1 reply; 3+ messages in thread
From: Patrick Palka @ 2022-09-02 13:18 UTC (permalink / raw)
  To: gcc-patches; +Cc: libstdc++, Patrick Palka

r13-2230-g390f94eee1ae69 redefined the internal logical operator traits
__and_, __or_ and __not as alias templates that directly resolve to
true_type or false_type.  But it turns out using an alias template here
causes the traits to be less lazy than before because we now compute
the logical result immediately upon _specialization_ of the trait, and
not later upon _completion_ of the specialization.

Thus, for example, in

  using type = __and_<A, __not_<B>>;

we now compute the conjunction and thus instantiate A even though we're
in a context that doesn't require completion of the __and_.  What's
worse is that we now compute the negation and thus instantiate B as well
(for the same reason), independent of the __and_ and the value of A!
Thus the traits are now less lazy and composable than before.

Fortunately, the fix is cheap and simple: redefine these traits as class
templates instead of as alias templates so that completion not
specialization triggers computation of the logical result.  I added
comprehensive short circuiting tests for these internal logical operator
traits in short_circuit.cc guarded by __GLIBCXX__, not sure if
that's the best place for them.  (Note that before this fix, assert #5
and #10 guarded by __GLIBCXX__ would induce a hard error due to this
bug).

Tested on x86_64-pc-linux-gnu, does this look OK for trunk?

libstdc++-v3/ChangeLog:

	* include/std/type_traits (__or_, __and_, __not_): Redefine as a
	class template instead of an alias template.
	* testsuite/20_util/logical_traits/requirements/short_circuit.cc:
	Add more tests for conjunction and disjunction.  Add corresponding
	tests for __and_ and __or_v.
---
 libstdc++-v3/include/std/type_traits          | 12 ++++++--
 .../requirements/short_circuit.cc             | 29 +++++++++++++++++++
 2 files changed, 38 insertions(+), 3 deletions(-)

diff --git a/libstdc++-v3/include/std/type_traits b/libstdc++-v3/include/std/type_traits
index 615791f29c8..2feb4b145c5 100644
--- a/libstdc++-v3/include/std/type_traits
+++ b/libstdc++-v3/include/std/type_traits
@@ -168,13 +168,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // to either true_type or false_type which allows for a more efficient
   // implementation that avoids recursive class template instantiation.
   template<typename... _Bn>
-    using __or_ = decltype(__detail::__or_fn<_Bn...>(0));
+    struct __or_
+    : decltype(__detail::__or_fn<_Bn...>(0))
+    { };
 
   template<typename... _Bn>
-    using __and_ = decltype(__detail::__and_fn<_Bn...>(0));
+    struct __and_
+    : decltype(__detail::__and_fn<_Bn...>(0))
+    { };
 
   template<typename _Pp>
-    using __not_ = __bool_constant<!bool(_Pp::value)>;
+    struct __not_
+    : __bool_constant<!bool(_Pp::value)>
+    { };
   /// @endcond
 
 #if __cplusplus >= 201703L
diff --git a/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc b/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
index 86996b27fa5..ff90f8a47c3 100644
--- a/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
+++ b/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
@@ -14,6 +14,10 @@ static_assert(!std::conjunction_v<std::false_type, invalid>);
 static_assert(!std::conjunction_v<std::false_type, invalid, invalid>);
 static_assert(!std::conjunction_v<std::true_type, std::false_type, invalid>);
 static_assert(!std::conjunction_v<std::true_type, std::false_type, invalid, invalid>);
+static_assert(!std::conjunction_v<std::false_type,
+				  std::conjunction<invalid>,
+				  std::disjunction<invalid>,
+				  std::negation<invalid>>);
 
 // [meta.logical]/8: For a specialization disjunction<B_1, ..., B_n>, if
 // there is a template type argument B_i for which bool(B_i::value) is true,
@@ -24,3 +28,28 @@ static_assert(std::disjunction_v<std::true_type, invalid>);
 static_assert(std::disjunction_v<std::true_type, invalid, invalid>);
 static_assert(std::disjunction_v<std::false_type, std::true_type, invalid>);
 static_assert(std::disjunction_v<std::false_type, std::true_type, invalid, invalid>);
+static_assert(std::disjunction_v<std::true_type,
+				 std::conjunction<invalid>,
+				 std::disjunction<invalid>,
+				 std::negation<invalid>>);
+
+#if __GLIBCXX__
+// Also test the corresponding internal traits __and_, __or_ and __not_.
+static_assert(!std::__and_v<std::false_type, invalid>);
+static_assert(!std::__and_v<std::false_type, invalid, invalid>);
+static_assert(!std::__and_v<std::true_type, std::false_type, invalid>);
+static_assert(!std::__and_v<std::true_type, std::false_type, invalid, invalid>);
+static_assert(!std::__and_v<std::false_type,
+			    std::__and_<invalid>,
+			    std::__or_<invalid>,
+			    std::__not_<invalid>>);
+
+static_assert(std::__or_v<std::true_type, invalid>);
+static_assert(std::__or_v<std::true_type, invalid, invalid>);
+static_assert(std::__or_v<std::false_type, std::true_type, invalid>);
+static_assert(std::__or_v<std::false_type, std::true_type, invalid, invalid>);
+static_assert(std::__or_v<std::true_type,
+			  std::__and_<invalid>,
+			  std::__or_<invalid>,
+			  std::__not_<invalid>>);
+#endif
-- 
2.37.2.490.g6c8e4ee870


^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH] libstdc++: Fix laziness of __and/or/not_
  2022-09-02 13:18 [PATCH] libstdc++: Fix laziness of __and/or/not_ Patrick Palka
@ 2022-09-02 13:34 ` Patrick Palka
  2022-09-02 14:10   ` Jonathan Wakely
  0 siblings, 1 reply; 3+ messages in thread
From: Patrick Palka @ 2022-09-02 13:34 UTC (permalink / raw)
  To: Patrick Palka; +Cc: gcc-patches, libstdc++

On Fri, 2 Sep 2022, Patrick Palka wrote:

> r13-2230-g390f94eee1ae69 redefined the internal logical operator traits
> __and_, __or_ and __not as alias templates that directly resolve to
> true_type or false_type.  But it turns out using an alias template here
> causes the traits to be less lazy than before because we now compute
> the logical result immediately upon _specialization_ of the trait, and
> not later upon _completion_ of the specialization.
> 
> Thus, for example, in
> 
>   using type = __and_<A, __not_<B>>;
> 
> we now compute the conjunction and thus instantiate A even though we're
> in a context that doesn't require completion of the __and_.  What's
> worse is that we now compute the negation and thus instantiate B as well
> (for the same reason), independent of the __and_ and the value of A!
> Thus the traits are now less lazy and composable than before.
> 
> Fortunately, the fix is cheap and simple: redefine these traits as class
> templates instead of as alias templates so that completion not
> specialization triggers computation of the logical result.  I added
> comprehensive short circuiting tests for these internal logical operator
> traits in short_circuit.cc guarded by __GLIBCXX__, not sure if
> that's the best place for them.  (Note that before this fix, assert #5
> and #10 guarded by __GLIBCXX__ would induce a hard error due to this
> bug).

FWIW this change doesn't seem to have a measurable compile time/memory
impact on the stress test from r13-2230.  For std/ranges/adaptors/join.cc,
memory usage increases by around 1% and compile time decreases by around
1%.

> 
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
> 
> libstdc++-v3/ChangeLog:
> 
> 	* include/std/type_traits (__or_, __and_, __not_): Redefine as a
> 	class template instead of an alias template.
> 	* testsuite/20_util/logical_traits/requirements/short_circuit.cc:
> 	Add more tests for conjunction and disjunction.  Add corresponding
> 	tests for __and_ and __or_v.
> ---
>  libstdc++-v3/include/std/type_traits          | 12 ++++++--
>  .../requirements/short_circuit.cc             | 29 +++++++++++++++++++
>  2 files changed, 38 insertions(+), 3 deletions(-)
> 
> diff --git a/libstdc++-v3/include/std/type_traits b/libstdc++-v3/include/std/type_traits
> index 615791f29c8..2feb4b145c5 100644
> --- a/libstdc++-v3/include/std/type_traits
> +++ b/libstdc++-v3/include/std/type_traits
> @@ -168,13 +168,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>    // to either true_type or false_type which allows for a more efficient
>    // implementation that avoids recursive class template instantiation.
>    template<typename... _Bn>
> -    using __or_ = decltype(__detail::__or_fn<_Bn...>(0));
> +    struct __or_
> +    : decltype(__detail::__or_fn<_Bn...>(0))
> +    { };
>  
>    template<typename... _Bn>
> -    using __and_ = decltype(__detail::__and_fn<_Bn...>(0));
> +    struct __and_
> +    : decltype(__detail::__and_fn<_Bn...>(0))
> +    { };
>  
>    template<typename _Pp>
> -    using __not_ = __bool_constant<!bool(_Pp::value)>;
> +    struct __not_
> +    : __bool_constant<!bool(_Pp::value)>
> +    { };
>    /// @endcond
>  
>  #if __cplusplus >= 201703L
> diff --git a/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc b/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
> index 86996b27fa5..ff90f8a47c3 100644
> --- a/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
> +++ b/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
> @@ -14,6 +14,10 @@ static_assert(!std::conjunction_v<std::false_type, invalid>);
>  static_assert(!std::conjunction_v<std::false_type, invalid, invalid>);
>  static_assert(!std::conjunction_v<std::true_type, std::false_type, invalid>);
>  static_assert(!std::conjunction_v<std::true_type, std::false_type, invalid, invalid>);
> +static_assert(!std::conjunction_v<std::false_type,
> +				  std::conjunction<invalid>,
> +				  std::disjunction<invalid>,
> +				  std::negation<invalid>>);
>  
>  // [meta.logical]/8: For a specialization disjunction<B_1, ..., B_n>, if
>  // there is a template type argument B_i for which bool(B_i::value) is true,
> @@ -24,3 +28,28 @@ static_assert(std::disjunction_v<std::true_type, invalid>);
>  static_assert(std::disjunction_v<std::true_type, invalid, invalid>);
>  static_assert(std::disjunction_v<std::false_type, std::true_type, invalid>);
>  static_assert(std::disjunction_v<std::false_type, std::true_type, invalid, invalid>);
> +static_assert(std::disjunction_v<std::true_type,
> +				 std::conjunction<invalid>,
> +				 std::disjunction<invalid>,
> +				 std::negation<invalid>>);
> +
> +#if __GLIBCXX__
> +// Also test the corresponding internal traits __and_, __or_ and __not_.
> +static_assert(!std::__and_v<std::false_type, invalid>);
> +static_assert(!std::__and_v<std::false_type, invalid, invalid>);
> +static_assert(!std::__and_v<std::true_type, std::false_type, invalid>);
> +static_assert(!std::__and_v<std::true_type, std::false_type, invalid, invalid>);
> +static_assert(!std::__and_v<std::false_type,
> +			    std::__and_<invalid>,
> +			    std::__or_<invalid>,
> +			    std::__not_<invalid>>);
> +
> +static_assert(std::__or_v<std::true_type, invalid>);
> +static_assert(std::__or_v<std::true_type, invalid, invalid>);
> +static_assert(std::__or_v<std::false_type, std::true_type, invalid>);
> +static_assert(std::__or_v<std::false_type, std::true_type, invalid, invalid>);
> +static_assert(std::__or_v<std::true_type,
> +			  std::__and_<invalid>,
> +			  std::__or_<invalid>,
> +			  std::__not_<invalid>>);
> +#endif
> -- 
> 2.37.2.490.g6c8e4ee870
> 
> 


^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH] libstdc++: Fix laziness of __and/or/not_
  2022-09-02 13:34 ` Patrick Palka
@ 2022-09-02 14:10   ` Jonathan Wakely
  0 siblings, 0 replies; 3+ messages in thread
From: Jonathan Wakely @ 2022-09-02 14:10 UTC (permalink / raw)
  To: Patrick Palka; +Cc: libstdc++, gcc-patches

[-- Attachment #1: Type: text/plain, Size: 6685 bytes --]

On Fri, 2 Sep 2022, 14:35 Patrick Palka via Libstdc++, <
libstdc++@gcc.gnu.org> wrote:

> On Fri, 2 Sep 2022, Patrick Palka wrote:
>
> > r13-2230-g390f94eee1ae69 redefined the internal logical operator traits
> > __and_, __or_ and __not as alias templates that directly resolve to
> > true_type or false_type.  But it turns out using an alias template here
> > causes the traits to be less lazy than before because we now compute
> > the logical result immediately upon _specialization_ of the trait, and
> > not later upon _completion_ of the specialization.
> >
> > Thus, for example, in
> >
> >   using type = __and_<A, __not_<B>>;
> >
> > we now compute the conjunction and thus instantiate A even though we're
> > in a context that doesn't require completion of the __and_.  What's
> > worse is that we now compute the negation and thus instantiate B as well
> > (for the same reason), independent of the __and_ and the value of A!
> > Thus the traits are now less lazy and composable than before.
>

Ah good catch.

>
> > Fortunately, the fix is cheap and simple: redefine these traits as class
> > templates instead of as alias templates so that completion not
> > specialization triggers computation of the logical result.  I added
> > comprehensive short circuiting tests for these internal logical operator
> > traits in short_circuit.cc guarded by __GLIBCXX__, not sure if
> > that's the best place for them.  (Note that before this fix, assert #5
> > and #10 guarded by __GLIBCXX__ would induce a hard error due to this
> > bug).
>

I don't bother guarding libstdc++-specific checks, because LLVM and MSVC
folk are allergic to anything that's been anywhere near GPL code.

But doing so is a kindness for any users who do decide to use our tests.
Maybe I should go through tests where I've added a comment saying "GCC
extension" and guard them this way



> FWIW this change doesn't seem to have a measurable compile time/memory
> impact on the stress test from r13-2230.  For std/ranges/adaptors/join.cc,
> memory usage increases by around 1% and compile time decreases by around
> 1%.
>

Great.


> >
> > Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
>


OK, thanks


>
> > libstdc++-v3/ChangeLog:
> >
> >       * include/std/type_traits (__or_, __and_, __not_): Redefine as a
> >       class template instead of an alias template.
> >       * testsuite/20_util/logical_traits/requirements/short_circuit.cc:
> >       Add more tests for conjunction and disjunction.  Add corresponding
> >       tests for __and_ and __or_v.
> > ---
> >  libstdc++-v3/include/std/type_traits          | 12 ++++++--
> >  .../requirements/short_circuit.cc             | 29 +++++++++++++++++++
> >  2 files changed, 38 insertions(+), 3 deletions(-)
> >
> > diff --git a/libstdc++-v3/include/std/type_traits
> b/libstdc++-v3/include/std/type_traits
> > index 615791f29c8..2feb4b145c5 100644
> > --- a/libstdc++-v3/include/std/type_traits
> > +++ b/libstdc++-v3/include/std/type_traits
> > @@ -168,13 +168,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >    // to either true_type or false_type which allows for a more efficient
> >    // implementation that avoids recursive class template instantiation.
> >    template<typename... _Bn>
> > -    using __or_ = decltype(__detail::__or_fn<_Bn...>(0));
> > +    struct __or_
> > +    : decltype(__detail::__or_fn<_Bn...>(0))
> > +    { };
> >
> >    template<typename... _Bn>
> > -    using __and_ = decltype(__detail::__and_fn<_Bn...>(0));
> > +    struct __and_
> > +    : decltype(__detail::__and_fn<_Bn...>(0))
> > +    { };
> >
> >    template<typename _Pp>
> > -    using __not_ = __bool_constant<!bool(_Pp::value)>;
> > +    struct __not_
> > +    : __bool_constant<!bool(_Pp::value)>
> > +    { };
> >    /// @endcond
> >
> >  #if __cplusplus >= 201703L
> > diff --git
> a/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
> b/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
> > index 86996b27fa5..ff90f8a47c3 100644
> > ---
> a/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
> > +++
> b/libstdc++-v3/testsuite/20_util/logical_traits/requirements/short_circuit.cc
> > @@ -14,6 +14,10 @@ static_assert(!std::conjunction_v<std::false_type,
> invalid>);
> >  static_assert(!std::conjunction_v<std::false_type, invalid, invalid>);
> >  static_assert(!std::conjunction_v<std::true_type, std::false_type,
> invalid>);
> >  static_assert(!std::conjunction_v<std::true_type, std::false_type,
> invalid, invalid>);
> > +static_assert(!std::conjunction_v<std::false_type,
> > +                               std::conjunction<invalid>,
> > +                               std::disjunction<invalid>,
> > +                               std::negation<invalid>>);
> >
> >  // [meta.logical]/8: For a specialization disjunction<B_1, ..., B_n>, if
> >  // there is a template type argument B_i for which bool(B_i::value) is
> true,
> > @@ -24,3 +28,28 @@ static_assert(std::disjunction_v<std::true_type,
> invalid>);
> >  static_assert(std::disjunction_v<std::true_type, invalid, invalid>);
> >  static_assert(std::disjunction_v<std::false_type, std::true_type,
> invalid>);
> >  static_assert(std::disjunction_v<std::false_type, std::true_type,
> invalid, invalid>);
> > +static_assert(std::disjunction_v<std::true_type,
> > +                              std::conjunction<invalid>,
> > +                              std::disjunction<invalid>,
> > +                              std::negation<invalid>>);
> > +
> > +#if __GLIBCXX__
> > +// Also test the corresponding internal traits __and_, __or_ and __not_.
> > +static_assert(!std::__and_v<std::false_type, invalid>);
> > +static_assert(!std::__and_v<std::false_type, invalid, invalid>);
> > +static_assert(!std::__and_v<std::true_type, std::false_type, invalid>);
> > +static_assert(!std::__and_v<std::true_type, std::false_type, invalid,
> invalid>);
> > +static_assert(!std::__and_v<std::false_type,
> > +                         std::__and_<invalid>,
> > +                         std::__or_<invalid>,
> > +                         std::__not_<invalid>>);
> > +
> > +static_assert(std::__or_v<std::true_type, invalid>);
> > +static_assert(std::__or_v<std::true_type, invalid, invalid>);
> > +static_assert(std::__or_v<std::false_type, std::true_type, invalid>);
> > +static_assert(std::__or_v<std::false_type, std::true_type, invalid,
> invalid>);
> > +static_assert(std::__or_v<std::true_type,
> > +                       std::__and_<invalid>,
> > +                       std::__or_<invalid>,
> > +                       std::__not_<invalid>>);
> > +#endif
> > --
> > 2.37.2.490.g6c8e4ee870
> >
> >
>
>

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2022-09-02 14:10 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-09-02 13:18 [PATCH] libstdc++: Fix laziness of __and/or/not_ Patrick Palka
2022-09-02 13:34 ` Patrick Palka
2022-09-02 14:10   ` Jonathan Wakely

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).