[Bug c++/109678] New: exponential time behavior on std::variant

[Bug c++/109678] New: exponential time behavior on std::variant

[quentin.sabah at gmail dot com]

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

            Bug ID: 109678
           Summary: exponential time behavior on std::variant
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: quentin.sabah at gmail dot com
  Target Milestone: ---

Hi,
I observe an exponential time behavior while compiling an std::variant with an
increasing number of alternatives (see testcase below).
It seems to be a regression in gcc 13 of the constant expression evaluation
while compiling "constexpr std::_Enable_default_constructor".

Found with gcc 13 shipped with Fedora 38.

Reproduced on Compiler Explorer:
Compiles in 20 seconds with gcc 13.1: https://godbolt.org/z/hhWx51sds
Compiles in a hundreds of milliseconds with gcc 12.2 and clang 16.

Testcase:

//=======================
#include <variant>

struct A {};
struct B {};
struct C {};
struct D {};
struct E {};
struct F {};
struct G {};
struct H {};
struct I {};
struct J {};
struct K {};
struct L {};
struct M {};
struct N {};
struct O {};
struct P {};
struct Q {};
struct R {};
struct S {};
struct T {};
struct U {};
struct V {};
struct W {
    // gcc13 + compiler explorer = 20000ms 
    // gcc12.2 + compiler explorer =   400ms
    int i;
};
struct X {};
struct Y {};
struct Z {};

using Foo = std::variant<A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R,
S, T, U, V, W, X, Y, Z>;

struct Bar {
    Foo f;
    static Bar dummy() {
        // issue is triggered by this initialization
        return {Z{}};
        // return {A{}}; // would be very quick
    }
};
//=======================



Compilation time reported on my machine (Intel(R) Core(TM) i7-4790 CPU @
3.60GHz)
$ time  g++ -v -std=c++17 -Wall -Wextra -c test.cpp 
...
GNU C++17 (GCC) version 13.0.1 20230401 (Red Hat 13.0.1-0)
(x86_64-redhat-linux)
        compiled by GNU C version 13.0.1 20230401 (Red Hat 13.0.1-0), GMP
version 6.2.1, MPFR version 4.1.1-p1, MPC version 1.3.1, isl version
isl-0.24-GMP
...
________________________________________________________
Executed in  131.43 secs    fish           external
   usr time  125.50 secs  659.00 micros  125.50 secs
   sys time    5.53 secs  109.00 micros    5.53 secs


perf report:
  29.51%  cc1plus  cc1plus               [.] cxx_eval_constant_expression       
  20.46%  cc1plus  cc1plus               [.] cxx_fold_indirect_ref_1            
   4.17%  cc1plus  cc1plus               [.] is_overloaded_fn



g++ -Q show that most time is spent in:
  constexpr std::_Enable_default_constructor<_Switch,
_Tag>::_Enable_default_constructor(std::_Enable_default_constructor_tag) [with
bool _Switch = true; _Tag = std::variant<A, B, C, D, E, F, G, H, I, J, K, L, M,
N, O, P, Q, R, S, T, U, V, W, X, Y, Z>]



g++ -ftime-report-details:
Time variable                                   usr           sys          wall
          GGC
 phase setup                        :   0.00 (  0%)   0.00 (  0%)   0.00 (  0%)
 1752k (  0%)
 phase parsing                      : 127.30 (100%)   4.76 (100%) 132.47 (100%)
16911M (100%)
 phase lang. deferred               :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
   19k (  0%)
 phase opt and generate             :   0.03 (  0%)   0.00 (  0%)   0.03 (  0%)
  103k (  0%)
 |name lookup                       :   0.02 (  0%)   0.01 (  0%)   0.04 (  0%)
  963k (  0%)
 |overload resolution               :   0.02 (  0%)   0.01 (  0%)   0.04 (  0%)
 3018k (  0%)
 garbage collection                 :   0.12 (  0%)   0.00 (  0%)   0.12 (  0%)
    0  (  0%)
 callgraph construction             :   0.03 (  0%)   0.00 (  0%)   0.03 (  0%)
  101k (  0%)
 preprocessing                      :   0.02 (  0%)   0.00 (  0%)   0.04 (  0%)
  361k (  0%)
 parser (global)                    :   0.01 (  0%)   0.02 (  0%)   0.05 (  0%)
 2957k (  0%)
 `- parser struct body              :   0.01 (  0%)   0.00 (  0%)   0.02 (  0%)
  669k (  0%)
 `- template instantiation          :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
   72k (  0%)
 `- preprocessing                   :   0.02 (  0%)   0.00 (  0%)   0.04 (  0%)
  361k (  0%)
 `- parser inl. func. body          :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
  263k (  0%)
 `- varconst                        :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
    0  (  0%)
 parser struct body                 :   0.02 (  0%)   0.02 (  0%)   0.04 (  0%)
 2568k (  0%)
 parser inl. func. body             :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
  362k (  0%)
 parser inl. meth. body             :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
  654k (  0%)
 `- garbage collection              :   0.12 (  0%)   0.00 (  0%)   0.12 (  0%)
    0  (  0%)
 `- template instantiation          :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
   13k (  0%)
 `- constant expression evaluation  : 127.02 (100%)   4.68 ( 98%) 132.10 (100%)
16896M (100%)
 template instantiation             :   0.06 (  0%)   0.04 (  1%)   0.12 (  0%)
 9062k (  0%)
 `- template instantiation          :   0.02 (  0%)   0.01 (  0%)   0.05 (  0%)
 1618k (  0%)
 `- symout                          :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
    0  (  0%)
 `- constant expression evaluation  :   0.02 (  0%)   0.00 (  0%)   0.00 (  0%)
   39k (  0%)
 constant expression evaluation     : 127.04 (100%)   4.68 ( 98%) 132.10 (100%)
16896M (100%)
 `- template instantiation          :   0.01 (  0%)   0.01 (  0%)   0.00 (  0%)
  345k (  0%)
 varconst                           :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
 4376  (  0%)
 symout                             :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
    0  (  0%)
 TOTAL                              : 127.33          4.76        132.51       
16913M

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[ppalka at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-04-29
   Target Milestone|---                         |13.2
             Status|UNCONFIRMED                 |NEW
                 CC|                            |ppalka at gcc dot gnu.org
      Known to work|                            |12.2.0
            Summary|exponential time behavior   |[13/14 Regression]
                   |on std::variant             |exponential time behavior
                   |                            |on std::variant
           Keywords|                            |compile-time-hog
     Ever confirmed|0                           |1

--- Comment #1 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Confirmed, started with r13-749-g1189c03859cefe.

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[jason at gcc dot gnu.org]

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

Jason Merrill <jason at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |jason at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |13.1.0
           Priority|P3                          |P2

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[geryemreis at gmail dot com]

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

--- Comment #2 from Gery Emreis <geryemreis at gmail dot com> ---
Its not just about compilation time but also about RAM usage. Compilation of
variation of std::variant as in provided example consumes unholy amounts of RAM
which in the end makes some files uncompilable on my system, because GCC
consumes all available RAM and swap and makes my system hang.

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jason Merrill
<jason@gcc.gnu.org>:

https://gcc.gnu.org/g:275e059dd7542f0d45adba74de18296134ac0d15

commit r13-7279-g275e059dd7542f0d45adba74de18296134ac0d15
Author: Jason Merrill <jason@redhat.com>
Date:   Tue May 2 15:03:57 2023 -0400

    Revert "c++: *this folding in constexpr call"

    The earlier commit wasn't fixing a known bug, so let's revert it on the
    branch.

            PR c++/109678

    This reverts commit 1189c03859cefef4fc4fd44d57eb3d4d3348b562.

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

https://gcc.gnu.org/g:4b8d0d4d7fd245ef85c7801e7838845502a5a61d

commit r14-409-g4b8d0d4d7fd245ef85c7801e7838845502a5a61d
Author: Jason Merrill <jason@redhat.com>
Date:   Mon May 1 17:41:44 2023 -0400

    c++: std::variant slow to compile [PR109678]

    Here, when dealing with a class with a complex subobject structure, we
would
    try and fail to find the relevant FIELD_DECL for an empty base before
giving
    up.  And we would do this at each level, in a combinatorially problematic
    way.  Instead, we should check for an empty base first.

            PR c++/109678

    gcc/cp/ChangeLog:

            * constexpr.cc (cxx_fold_indirect_ref_1): Handle empty base first.

    gcc/testsuite/ChangeLog:

            * g++.dg/cpp1z/variant1.C: New test.

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

https://gcc.gnu.org/g:a43f3616c0069541b1f465eea67285eeeff36785

commit r14-410-ga43f3616c0069541b1f465eea67285eeeff36785
Author: Jason Merrill <jason@redhat.com>
Date:   Mon May 1 21:03:45 2023 -0400

    c++: look for empty base at specific offset [PR109678]

    While looking at the empty base handling for 109678, it occurred to me that
    we ought to be able to look for an empty base at a specific offset, not
just
    in general.

            PR c++/109678

    gcc/cp/ChangeLog:

            * cp-tree.h (lookup_base): Add offset parm.
            * constexpr.cc (cxx_fold_indirect_ref_1): Pass it.
            * search.cc (struct lookup_base_data_s): Add offset.
            (dfs_lookup_base): Handle it.
            (lookup_base): Pass it.

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[jason at gcc dot gnu.org]

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

Jason Merrill <jason at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #6 from Jason Merrill <jason at gcc dot gnu.org> ---
Fixed for 13.2/14.

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[quentin.sabah at gmail dot com]

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

--- Comment #7 from Quentin Sabah <quentin.sabah at gmail dot com> ---
@jason Thanks for the fix!

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |toojays at toojays dot net

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
*** Bug 110078 has been marked as a duplicate of this bug. ***

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |manuel.bergler at mvtec dot com

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 110257 has been marked as a duplicate of this bug. ***

[Bug c++/109678] [13/14 Regression] exponential time behavior on std::variant

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jason Merrill
<jason@gcc.gnu.org>:

https://gcc.gnu.org/g:d3088f0ed25fe7200fd657b70cb5af53139b0193

commit r13-7713-gd3088f0ed25fe7200fd657b70cb5af53139b0193
Author: Jason Merrill <jason@redhat.com>
Date:   Mon May 1 17:41:44 2023 -0400

    c++: std::variant slow to compile [PR109678]

    Here, when dealing with a class with a complex subobject structure, we
would
    try and fail to find the relevant FIELD_DECL for an empty base before
giving
    up.  And we would do this at each level, in a combinatorially problematic
    way.  Instead, we should check for an empty base first.

            PR c++/109678

    gcc/cp/ChangeLog:

            * constexpr.cc (cxx_fold_indirect_ref_1): Handle empty base first.

    gcc/testsuite/ChangeLog:

            * g++.dg/cpp1z/variant1.C: New test.