[Bug c++/108138] New: g++ 9+ takes 7-10x longer compiling constexpr

[Bug c++/108138] New: g++ 9+ takes 7-10x longer compiling constexpr

[peter at meraki dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

            Bug ID: 108138
           Summary: g++ 9+ takes 7-10x longer compiling constexpr
           Product: gcc
           Version: 11.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: peter at meraki dot com
  Target Milestone: ---

Created attachment 54107
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54107&action=edit
testcase

The attached testcase takes ~24s to compile on gcc 8.4.0 but takes ~172s with
gcc 11.1.0:

g++-8 -std=gnu++11 -Wall -Werror -ftime-report -c constexpr-testcase2.cc

Time variable                                   usr           sys          wall
              GGC
 phase setup                        :   0.01 (  0%)   0.00 (  0%)   0.02 (  0%)
   1495 kB ( 32%)
 phase parsing                      :  19.02 (100%)   5.05 (100%)  24.07 (100%)
   3197 kB ( 68%)
 |name lookup                       :   0.01 (  0%)   0.01 (  0%)   0.02 (  0%)
    102 kB (  2%)
 |overload resolution               :   6.60 ( 35%)   1.61 ( 32%)   7.87 ( 33%)
    474 kB ( 10%)
 preprocessing                      :   0.01 (  0%)   0.01 (  0%)   0.00 (  0%)
    264 kB (  6%)
 parser (global)                    :   0.00 (  0%)   0.00 (  0%)   0.02 (  0%)
    576 kB ( 12%)
 parser inl. func. body             :   2.34 ( 12%)   0.72 ( 14%)   2.83 ( 12%)
   2325 kB ( 49%)
 constant expression evaluation     :  16.67 ( 88%)   4.32 ( 86%)  21.22 ( 88%)
     31 kB (  1%)
 TOTAL                              :  19.03          5.05         24.09       
   4709 kB

g++-11 -Wall -Werror -ftime-report -c constexpr-testcase2.cc

Time variable                                   usr           sys          wall
          GGC
 phase setup                        :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
 1553k (  4%)
 phase parsing                      : 165.22 (100%)   7.55 (100%) 172.78 (100%)
   36M ( 96%)
 |name lookup                       :   0.02 (  0%)   0.00 (  0%)   0.00 (  0%)
  102k (  0%)
 |overload resolution               :  82.10 ( 50%)   4.00 ( 53%)  85.99 ( 50%)
   17M ( 46%)
 preprocessing                      :   0.01 (  0%)   0.02 (  0%)   0.01 (  0%)
  224k (  1%)
 parser (global)                    :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
  579k (  1%)
 parser inl. func. body             :   2.92 (  2%)   0.12 (  2%)   2.82 (  2%)
 5336k ( 14%)
 constant expression evaluation     : 162.29 ( 98%)   7.41 ( 98%) 169.94 ( 98%)
   30M ( 80%)
 TOTAL                              : 165.22          7.55        172.79       
   38M


The dramatic slowdown appears to have been introduced in gcc 9
The best wall time (of versions tested) was gcc 7.5 at ~15s
The worst wall time was gcc 10.3 at ~180s

The wordlist was trivially constructed from:
wget https://www.mit.edu/~ecprice/wordlist.10000
head -1000 wordlist.10000 | sed 's/\(.*\)/CHECK(\1)/' > wordlist.1000.hh

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[peter at meraki dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

--- Comment #1 from Peter Hurley <peter at meraki dot com> ---
Created attachment 54108
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54108&action=edit
testcase header file

[Bug c++/108138] [10/11 Regression] g++ 9+ takes 7-10x longer compiling constexpr

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog
   Target Milestone|---                         |10.5
      Known to work|                            |12.1.0
            Summary|g++ 9+ takes 7-10x longer   |[10/11 Regression] g++ 9+
                   |compiling constexpr         |takes 7-10x longer
                   |                            |compiling constexpr

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Looks like it was fixed in GCC 12.

[Bug c++/108138] [10/11 Regression] g++ 9+ takes 7-10x longer compiling constexpr

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---

GCC 12 looks faster than GCC 8 even:
Time variable                                   usr           sys          wall
          GGC
 phase setup                        :   0.00 (  0%)   0.01 ( 25%)   0.02 (  7%)
 1578k ( 19%)
 phase parsing                      :   0.18 (100%)   0.03 ( 75%)   0.25 ( 93%)
 6615k ( 81%)
 |name lookup                       :   0.00 (  0%)   0.00 (  0%)   0.02 (  7%)
  102k (  1%)
 |overload resolution               :   0.07 ( 39%)   0.01 ( 25%)   0.09 ( 33%)
 2446k ( 30%)
 preprocessing                      :   0.00 (  0%)   0.01 ( 25%)   0.01 (  4%)
  224k (  3%)
 parser inl. func. body             :   0.17 ( 94%)   0.02 ( 50%)   0.21 ( 78%)
 5625k ( 69%)
 constant expression evaluation     :   0.01 (  6%)   0.00 (  0%)   0.03 ( 11%)
  187k (  2%)
 TOTAL                              :   0.18          0.04          0.27       
 8204k

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=102780
            Summary|[10/11 Regression] g++ 9+   |g++ 9+ takes 7-10x longer
                   |takes 7-10x longer          |compiling constexpr
                   |compiling constexpr         |
   Target Milestone|10.5                        |12.0

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I think it was fixed by the patch which fixed/improved PR 102780:
r12-4769-g9927ecbb42d5b

The reason why I am declaring this as fully fixed for GCC 12 is that GCC 12 is
so much faster than all other versions including 7.

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ppalka at gcc dot gnu.org

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Patrick, is there anything that can be done on the GCC 10/11 branches for this
regression from GCC 8?

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Just for the record, since nobody seems to have said it yet, the slowdown is
independent of the -std option. GCC 8 is fast even with -std=gnu++17 (instead
of the default gnu++14) and GCC 11 is slow even with -std=gnu++14 (instead of
the default -std=gnu++17).

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jason at gcc dot gnu.org

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The slowdown began with r9-942-ge079dced7a8383

    CWG 1581: When are constexpr member functions defined?

            * constexpr.c (instantiate_cx_fn_r, instantiate_constexpr_fns):
New.
            (cxx_eval_outermost_constant_expr): Call instantiate_constexpr_fns.

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-12-16
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
                 CC|                            |marxin at gcc dot gnu.org

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

--- Comment #8 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> I think it was fixed by the patch which fixed/improved PR 102780:
> r12-4769-g9927ecbb42d5b

I can confirm this!

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[ppalka at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

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

--- Comment #9 from Patrick Palka <ppalka at gcc dot gnu.org> ---
I'll look into backporting the PR102780 fix

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

--- Comment #10 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++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

--- Comment #11 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++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[ppalka at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.0                        |10.5
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #12 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Fixed for GCC 10.5/11.4+

[Bug c++/108138] g++ 9+ takes 7-10x longer compiling constexpr

[peter at meraki dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108138

--- Comment #13 from Peter Hurley <peter at meraki dot com> ---
Thanks everyone! We're really grateful for the rapid response and backports!
Happy holidays!