public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug c++/102780] New: Checking constraints using large fold expression is slow
@ 2021-10-15 13:12 redi at gcc dot gnu.org
2021-10-15 13:14 ` [Bug c++/102780] " redi at gcc dot gnu.org
` (8 more replies)
0 siblings, 9 replies; 10+ messages in thread
From: redi at gcc dot gnu.org @ 2021-10-15 13:12 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
Bug ID: 102780
Summary: Checking constraints using large fold expression is
slow
Product: gcc
Version: 12.0
Status: UNCONFIRMED
Keywords: compile-time-hog
Severity: normal
Priority: P3
Component: c++
Assignee: unassigned at gcc dot gnu.org
Reporter: redi at gcc dot gnu.org
Target Milestone: ---
template<int I> struct S { };
template<typename T, T...> struct integer_sequence { };
template<typename T, T N>
using make_integer_sequence
#if __has_builtin(__make_integer_seq)
= __make_integer_seq<integer_sequence, T, N>;
#else
= integer_sequence<T, __integer_pack(N)...>;
#endif
template<typename... _Types>
concept trivially_destructible
= (__has_trivial_destructor(_Types) && ...);
template<typename...> union variadic_union { static constexpr int size = 0; };
template<typename T, typename... U>
union variadic_union<T, U...>
{
~variadic_union() = default;
#ifndef TRIVIAL_ONLY
// Conditionally non-trivial dtor, if required.
constexpr ~variadic_union() requires (!trivially_destructible<T, U...>)
{ }
#endif
T first;
variadic_union<U...> rest;
static constexpr int size = variadic_union<U...>::size + 1;
};
template <int... Is>
void f_impl(integer_sequence<int, Is...>)
{
using V = variadic_union<S<Is>...>;
// cause instantiation of V:
static_assert( V::size == sizeof...(Is) );
}
template <int I>
void f()
{
f_impl(make_integer_sequence<int, I>());
}
int main()
{
f<254>();
f<255>();
f<256>();
}
Compiled with -std=gnu++20 -ftime-report I get:
TOTAL : 10.46 3.58 14.08 78M
Adding -fno-checking helps a little:
TOTAL : 7.71 3.70 11.43 78M
Clang compiles this in under a second.
Full details:
> Time variable usr sys wall GGC
> phase setup : 0.00 ( 0%) 0.00 ( 0%) 0.01 ( 0%) 1589k ( 2%)
> phase lang. deferred : 7.88 ( 75%) 3.68 (100%) 11.62 ( 82%) 69M ( 88%)
> phase opt and generate : 2.59 ( 25%) 0.00 ( 0%) 2.60 ( 18%) 7297k ( 9%)
> |name lookup : 0.05 ( 0%) 0.02 ( 1%) 0.02 ( 0%) 670k ( 1%)
> |overload resolution : 7.35 ( 70%) 3.51 ( 95%) 10.91 ( 77%) 10M ( 13%)
> garbage collection : 0.04 ( 0%) 0.00 ( 0%) 0.04 ( 0%) 0 ( 0%)
> callgraph construction : 2.56 ( 24%) 0.00 ( 0%) 2.58 ( 18%) 7016k ( 9%)
> callgraph ipa passes : 0.02 ( 0%) 0.00 ( 0%) 0.01 ( 0%) 15k ( 0%)
> CFG verifier : 0.01 ( 0%) 0.00 ( 0%) 0.00 ( 0%) 0 ( 0%)
> template instantiation : 0.25 ( 2%) 0.11 ( 3%) 0.37 ( 3%) 43M ( 56%)
> constant expression evaluation : 4.36 ( 42%) 2.02 ( 55%) 6.61 ( 46%) 72 ( 0%)
> constraint satisfaction : 3.20 ( 31%) 1.55 ( 42%) 4.57 ( 32%) 20M ( 25%)
> symout : 0.05 ( 0%) 0.00 ( 0%) 0.04 ( 0%) 5726k ( 7%)
> initialize rtl : 0.00 ( 0%) 0.00 ( 0%) 0.01 ( 0%) 12k ( 0%)
> TOTAL : 10.47 3.68 14.23 78M
> Extra diagnostic checks enabled; compiler may run slowly.
> Configure with --enable-checking=release to disable checks.
Defining -DTRIVIAL_ONLY makes it compile in under 2s, and 0.4s with
-DTRIVIAL_ONLY -fno-checking (almost as fast as clang)
The constraint satisfaction seems to be the problem, even though "template
instantiation" shows up as a larger percentage in the time report.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug c++/102780] Checking constraints using large fold expression is slow
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
@ 2021-10-15 13:14 ` redi at gcc dot gnu.org
2021-10-15 13:26 ` redi at gcc dot gnu.org
` (7 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: redi at gcc dot gnu.org @ 2021-10-15 13:14 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
Jonathan Wakely <redi at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Ever confirmed|0 |1
Last reconfirmed| |2021-10-15
Status|UNCONFIRMED |NEW
--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This code is reduce from std::variant
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug c++/102780] Checking constraints using large fold expression is slow
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
2021-10-15 13:14 ` [Bug c++/102780] " redi at gcc dot gnu.org
@ 2021-10-15 13:26 ` redi at gcc dot gnu.org
2021-10-15 14:32 ` redi at gcc dot gnu.org
` (6 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: redi at gcc dot gnu.org @ 2021-10-15 13:26 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
In the real code, I find that a separate constrained specialization like this:
template<typename T, typename... U>
union variadic_union<T, U...>
{
T first;
variadic_union<U...> rest;
static constexpr int size = variadic_union<U...>::size + 1;
};
template<typename T, typename... U>
requires (!trivially_destructible<T, U...>)
union variadic_union<T, U...>
{
variadic_union(const variadic_union&) = default;
variadic_union(variadic_union&&) = default;
variadic_union& operator=(const variadic_union&) = default;
variadic_union& operator=(variadic_union&&) = default;
// Non-trivial dtor is required for this partial specialization
constexpr ~variadic_union()
{ }
T first;
variadic_union<U...> rest;
static constexpr int size = variadic_union<U...>::size + 1;
};
Is much faster (14s instead of 20s+) than a constrained destructor in the
primary template:
template<typename T, typename... U>
union variadic_union<T, U...>
{
variadic_union(const variadic_union&) = default;
variadic_union(variadic_union&&) = default;
variadic_union& operator=(const variadic_union&) = default;
variadic_union& operator=(variadic_union&&) = default;
~variadic_union() = default;
// Conditionally non-trivial dtor, if required.
constexpr ~variadic_union() requires (!trivially_destructible<T, U...>)
{ }
T first;
variadic_union<U...> rest;
static constexpr int size = variadic_union<U...>::size + 1;
};
I haven't been able to reproduce that time difference in the reduced examples
though.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug c++/102780] Checking constraints using large fold expression is slow
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
2021-10-15 13:14 ` [Bug c++/102780] " redi at gcc dot gnu.org
2021-10-15 13:26 ` redi at gcc dot gnu.org
@ 2021-10-15 14:32 ` redi at gcc dot gnu.org
2021-10-28 14:05 ` cvs-commit at gcc dot gnu.org
` (5 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: redi at gcc dot gnu.org @ 2021-10-15 14:32 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Patrick suggested defining the destructor constraint like this instead:
// Conditionally non-trivial dtor, if required.
constexpr ~variadic_union()
requires (!trivially_destructible<T>)
|| (!trivially_destructible<variadic_union<U...>>)
{ }
This makes a huge difference in the examples above, making them compile much
faster.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug c++/102780] Checking constraints using large fold expression is slow
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
` (2 preceding siblings ...)
2021-10-15 14:32 ` redi at gcc dot gnu.org
@ 2021-10-28 14:05 ` cvs-commit at gcc dot gnu.org
2021-10-28 14:49 ` ppalka at gcc dot gnu.org
` (4 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-10-28 14:05 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Patrick Palka <ppalka@gcc.gnu.org>:
https://gcc.gnu.org/g:9927ecbb42d5be48fa933adc26f8601fab5007ca
commit r12-4769-g9927ecbb42d5be48fa933adc26f8601fab5007ca
Author: Patrick Palka <ppalka@redhat.com>
Date: Thu Oct 28 10:05:14 2021 -0400
c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
In the testcase below the two left fold expressions each expand into a
constant logical expression with 1024 terms, for which potential_const_expr
takes more than a minute to return true. This happens because p_c_e_1
performs trial evaluation of the first operand of a &&/|| in order to
determine whether to consider the potentiality of the second operand.
And because the expanded expression is left-associated, this trial
evaluation causes p_c_e_1 to be quadratic in the number of terms of the
expression.
This patch fixes this quadratic behavior by making p_c_e_1 preemptively
compute potentiality of the second operand of a &&/||, and perform trial
evaluation of the first operand only if the second operand isn't
potentially constant. We must be careful to avoid emitting bogus
diagnostics during the preemptive computation; to that end, we perform
this shortcut only when tf_error is cleared, and when tf_error is set we
now first check potentiality of the whole expression quietly and replay
the check noisily for diagnostics.
Apart from fixing the quadraticness for left-associated logical exprs,
this change also reduces compile time for the libstdc++ testcase
20_util/variant/87619.cc by about 15% even though our <variant> uses
right folds instead of left folds. Likewise for the testcase in the PR,
for which compile time is reduced by 30%. The reason for these speedups
is that p_c_e_1 no longer performs expensive trial evaluation of each term
of large constant logical expressions when determining their potentiality.
PR c++/102780
gcc/cp/ChangeLog:
* constexpr.c (potential_constant_expression_1) <case
TRUTH_*_EXPR>:
When tf_error isn't set, preemptively check potentiality of the
second operand before performing trial evaluation of the first
operand.
(potential_constant_expression_1): When tf_error is set, first
check
potentiality quietly and return true if successful, otherwise
proceed noisily to give errors.
gcc/testsuite/ChangeLog:
* g++.dg/cpp1z/fold13.C: New test.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug c++/102780] Checking constraints using large fold expression is slow
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
` (3 preceding siblings ...)
2021-10-28 14:05 ` cvs-commit at gcc dot gnu.org
@ 2021-10-28 14:49 ` ppalka at gcc dot gnu.org
2022-12-16 21:11 ` cvs-commit at gcc dot gnu.org
` (3 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: ppalka at gcc dot gnu.org @ 2021-10-28 14:49 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
Patrick Palka <ppalka at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Assignee|unassigned at gcc dot gnu.org |ppalka at gcc dot gnu.org
Status|NEW |ASSIGNED
CC| |ppalka at gcc dot gnu.org
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug c++/102780] Checking constraints using large fold expression is slow
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
` (4 preceding siblings ...)
2021-10-28 14:49 ` ppalka at gcc dot gnu.org
@ 2022-12-16 21:11 ` cvs-commit at gcc dot gnu.org
2022-12-16 21:14 ` cvs-commit at gcc dot gnu.org
` (2 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2022-12-16 21:11 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Patrick Palka
<ppalka@gcc.gnu.org>:
https://gcc.gnu.org/g:71d2567a678b01a3a59064d22e0f9165be9e93c3
commit r11-10424-g71d2567a678b01a3a59064d22e0f9165be9e93c3
Author: Patrick Palka <ppalka@redhat.com>
Date: Thu Oct 28 10:05:14 2021 -0400
c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
In the testcase below the two left fold expressions each expand into a
constant logical expression with 1024 terms, for which potential_const_expr
takes more than a minute to return true. This happens because p_c_e_1
performs trial evaluation of the first operand of a &&/|| in order to
determine whether to consider the potentiality of the second operand.
And because the expanded expression is left-associated, this trial
evaluation causes p_c_e_1 to be quadratic in the number of terms of the
expression.
This patch fixes this quadratic behavior by making p_c_e_1 preemptively
compute potentiality of the second operand of a &&/||, and perform trial
evaluation of the first operand only if the second operand isn't
potentially constant. We must be careful to avoid emitting bogus
diagnostics during the preemptive computation; to that end, we perform
this shortcut only when tf_error is cleared, and when tf_error is set we
now first check potentiality of the whole expression quietly and replay
the check noisily for diagnostics.
Apart from fixing the quadraticness for left-associated logical exprs,
this change also reduces compile time for the libstdc++ testcase
20_util/variant/87619.cc by about 15% even though our <variant> uses
right folds instead of left folds. Likewise for the testcase in the PR,
for which compile time is reduced by 30%. The reason for these speedups
is that p_c_e_1 no longer performs expensive trial evaluation of each term
of large constant logical expressions when determining their potentiality.
PR c++/102780
PR c++/108138
gcc/cp/ChangeLog:
* constexpr.c (potential_constant_expression_1) <case
TRUTH_*_EXPR>:
When tf_error isn't set, preemptively check potentiality of the
second operand before performing trial evaluation of the first
operand.
(potential_constant_expression_1): When tf_error is set, first
check
potentiality quietly and return true if successful, otherwise
proceed noisily to give errors.
gcc/testsuite/ChangeLog:
* g++.dg/cpp1z/fold13.C: New test.
(cherry picked from commit 9927ecbb42d5be48fa933adc26f8601fab5007ca)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug c++/102780] Checking constraints using large fold expression is slow
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
` (5 preceding siblings ...)
2022-12-16 21:11 ` cvs-commit at gcc dot gnu.org
@ 2022-12-16 21:14 ` cvs-commit at gcc dot gnu.org
2022-12-16 23:57 ` ppalka at gcc dot gnu.org
2024-01-07 1:00 ` cvs-commit at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2022-12-16 21:14 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Patrick Palka
<ppalka@gcc.gnu.org>:
https://gcc.gnu.org/g:16605ad9b1e1a6c5aab2c98b5b0f995285584f81
commit r10-11124-g16605ad9b1e1a6c5aab2c98b5b0f995285584f81
Author: Patrick Palka <ppalka@redhat.com>
Date: Thu Oct 28 10:05:14 2021 -0400
c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
In the testcase below the two left fold expressions each expand into a
constant logical expression with 1024 terms, for which potential_const_expr
takes more than a minute to return true. This happens because p_c_e_1
performs trial evaluation of the first operand of a &&/|| in order to
determine whether to consider the potentiality of the second operand.
And because the expanded expression is left-associated, this trial
evaluation causes p_c_e_1 to be quadratic in the number of terms of the
expression.
This patch fixes this quadratic behavior by making p_c_e_1 preemptively
compute potentiality of the second operand of a &&/||, and perform trial
evaluation of the first operand only if the second operand isn't
potentially constant. We must be careful to avoid emitting bogus
diagnostics during the preemptive computation; to that end, we perform
this shortcut only when tf_error is cleared, and when tf_error is set we
now first check potentiality of the whole expression quietly and replay
the check noisily for diagnostics.
Apart from fixing the quadraticness for left-associated logical exprs,
this change also reduces compile time for the libstdc++ testcase
20_util/variant/87619.cc by about 15% even though our <variant> uses
right folds instead of left folds. Likewise for the testcase in the PR,
for which compile time is reduced by 30%. The reason for these speedups
is that p_c_e_1 no longer performs expensive trial evaluation of each term
of large constant logical expressions when determining their potentiality.
PR c++/102780
PR c++/108138
gcc/cp/ChangeLog:
* constexpr.c (potential_constant_expression_1) <case
TRUTH_*_EXPR>:
When tf_error isn't set, preemptively check potentiality of the
second operand before performing trial evaluation of the first
operand.
(potential_constant_expression_1): When tf_error is set, first
check
potentiality quietly and return true if successful, otherwise
proceed noisily to give errors.
gcc/testsuite/ChangeLog:
* g++.dg/cpp1z/fold13.C: New test.
(cherry picked from commit 9927ecbb42d5be48fa933adc26f8601fab5007ca)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug c++/102780] Checking constraints using large fold expression is slow
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
` (6 preceding siblings ...)
2022-12-16 21:14 ` cvs-commit at gcc dot gnu.org
@ 2022-12-16 23:57 ` ppalka at gcc dot gnu.org
2024-01-07 1:00 ` cvs-commit at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: ppalka at gcc dot gnu.org @ 2022-12-16 23:57 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
Patrick Palka <ppalka at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Resolution|--- |FIXED
Target Milestone|--- |10.5
Status|ASSIGNED |RESOLVED
--- Comment #7 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Fixed, I suppose.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug c++/102780] Checking constraints using large fold expression is slow
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
` (7 preceding siblings ...)
2022-12-16 23:57 ` ppalka at gcc dot gnu.org
@ 2024-01-07 1:00 ` cvs-commit at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2024-01-07 1:00 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102780
--- Comment #8 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:
https://gcc.gnu.org/g:7d11d813583efad652c83c7631ef8d6d18489119
commit r14-6974-g7d11d813583efad652c83c7631ef8d6d18489119
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Wed Dec 6 18:32:21 2023 +0000
libstdc++: Remove dg-timeout-factor from test
As the comment notes, the increased timeout was needed because of PR
102780, but that was fixed long ago.
libstdc++-v3/ChangeLog:
* testsuite/20_util/variant/87619.cc: Remove dg-timeout-factor.
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2024-01-07 1:00 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-10-15 13:12 [Bug c++/102780] New: Checking constraints using large fold expression is slow redi at gcc dot gnu.org
2021-10-15 13:14 ` [Bug c++/102780] " redi at gcc dot gnu.org
2021-10-15 13:26 ` redi at gcc dot gnu.org
2021-10-15 14:32 ` redi at gcc dot gnu.org
2021-10-28 14:05 ` cvs-commit at gcc dot gnu.org
2021-10-28 14:49 ` ppalka at gcc dot gnu.org
2022-12-16 21:11 ` cvs-commit at gcc dot gnu.org
2022-12-16 21:14 ` cvs-commit at gcc dot gnu.org
2022-12-16 23:57 ` ppalka at gcc dot gnu.org
2024-01-07 1:00 ` cvs-commit at gcc dot gnu.org
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).