[Bug c++/102780] New: Checking constraints using large fold expression is slow

[Bug c++/102780] New: Checking constraints using large fold expression is slow

[redi at gcc dot gnu.org]

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.

[Bug c++/102780] Checking constraints using large fold expression is slow

[redi at gcc dot gnu.org]

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

[Bug c++/102780] Checking constraints using large fold expression is slow

[redi at gcc dot gnu.org]

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.

[Bug c++/102780] Checking constraints using large fold expression is slow

[redi at gcc dot gnu.org]

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.

[Bug c++/102780] Checking constraints using large fold expression is slow

[cvs-commit at gcc dot gnu.org]

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.

[Bug c++/102780] Checking constraints using large fold expression is slow

[ppalka at gcc dot gnu.org]

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

[Bug c++/102780] Checking constraints using large fold expression is slow

[cvs-commit at gcc dot gnu.org]

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)

[Bug c++/102780] Checking constraints using large fold expression is slow

[cvs-commit at gcc dot gnu.org]

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)

[Bug c++/102780] Checking constraints using large fold expression is slow

[ppalka at gcc dot gnu.org]

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.

[Bug c++/102780] Checking constraints using large fold expression is slow

[cvs-commit at gcc dot gnu.org]

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.