[Bug c++/113835] New: compiling std::vector with const size in C++20 is slow

[Bug c++/113835] New: compiling std::vector with const size in C++20 is slow

[pobrn at protonmail dot com]

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

            Bug ID: 113835
           Summary: compiling std::vector with const size in C++20 is slow
           Product: gcc
           Version: 13.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pobrn at protonmail dot com
  Target Milestone: ---

Consider the following code:

    #include <vector>
    const std::size_t N = 1'000'000;
    std::vector<int> x(N);
    int main() {}

Then:

    $ hyperfine 'g++ -std=c++20 -O2 x.cpp' 'g++ -std=c++17 -O2 x.cpp'
    Benchmark 1: g++ -std=c++20 -O2 x.cpp
      Time (mean ± σ):      4.945 s ±  0.116 s    [User: 4.676 s, System: 0.229
s]
      Range (min … max):    4.770 s …  5.178 s    10 runs

    Benchmark 2: g++ -std=c++17 -O2 x.cpp
      Time (mean ± σ):     491.3 ms ±  24.0 ms    [User: 440.9 ms, System: 46.3
ms]
      Range (min … max):   465.6 ms … 538.0 ms    10 runs

    Summary
      g++ -std=c++17 -O2 x.cpp ran
       10.07 ± 0.55 times faster than g++ -std=c++20 -O2 x.cpp

If you remove the `const` from `N`, the runtime will be closer to C++17 levels.

`-ftime-report` suggests that "constant expression evaluation" is the reason. I
imagine this is related to C++20 making std::vector constexpr.

[Bug libstdc++/113835] [13/14 Regression] compiling std::vector with const size in C++20 is slow

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2024-02-09
   Target Milestone|---                         |13.3
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
      Known to fail|                            |13.2.1, 14.0
          Component|c++                         |libstdc++
      Known to work|                            |12.2.1
            Summary|compiling std::vector with  |[13/14 Regression]
                   |const size in C++20 is slow |compiling std::vector with
                   |                            |const size in C++20 is slow

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed with -std=c++20 -fsyntax-only

 constant expression evaluation     :   1.80 ( 85%)   0.03 ( 14%)   1.84 ( 78%)
  220M ( 88%)
 TOTAL                              :   2.13          0.22          2.36       
  250M


Samples: 8K of event 'cycles', Event count (approx.): 9294971478                
Overhead       Samples  Command  Shared Object     Symbol                       
  16.33%          1385  cc1plus  cc1plus           [.]
cxx_eval_constant_expression
   4.35%           369  cc1plus  cc1plus           [.] cxx_eval_call_expression
   3.90%           331  cc1plus  cc1plus           [.]
cxx_eval_store_expression
   3.16%           268  cc1plus  cc1plus           [.]
hash_table<hash_map<tree_node*, tree_node*, simple_has
   2.55%           216  cc1plus  cc1plus           [.]
hash_table<hash_map<tree_node*, tree_node*, simple_has
   2.15%           183  cc1plus  cc1plus           [.] ggc_internal_alloc
   2.04%           173  cc1plus  cc1plus           [.]
hash_table<int_cst_hasher, false, xcallocator>::find_s
   1.98%           168  cc1plus  cc1plus           [.] tree_operand_check

GCC 12 was fast (possibly std::vector wasn't constexpr there?)

[Bug libstdc++/113835] [13/14 Regression] compiling std::vector with const size in C++20 is slow

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> GCC 12 was fast (possibly std::vector wasn't constexpr there?)

It was constexpr since 12.1.0

So this might be related to Jason's implicit constexpr changes instead.

[Bug libstdc++/113835] [13/14 Regression] compiling std::vector with const size in C++20 is slow

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The most significant slowdown (though just approximate, I've been bisecting
that in an mostly -O0 built compiler) is
r13-6421-gcbaa1d9c218d9c0b5e34e510a462ff4e299a0f3f
Though, no idea what could be done against it, because the standard requires
that...

[Bug libstdc++/113835] [13/14 Regression] compiling std::vector with const size in C++20 is slow

[ppalka at gcc dot gnu.org]

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

--- Comment #4 from Patrick Palka <ppalka at gcc dot gnu.org> ---
r13-6421 just makes us use mce_true and mce_uknown during trial constant
evaluation of x's initialization, so my guess is before that commit the
evaluation was quickly aborted as soon as it saw a std::is_constant_evaluated()
call, and afterwards we evaluate is_constant_evaluated() to true and keep going
until we hit constexpr_loop_limit / constexpr_ops_limit.  So perhaps we should
have reduced limits for trial constant evaluation?

[Bug libstdc++/113835] [13/14 Regression] compiling std::vector with const size in C++20 is slow

[ppalka at gcc dot gnu.org]

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

--- Comment #5 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Relatedly, if we actually make x constexpr

#include <vector>
const std::size_t N = 1'000'000;
constexpr std::vector<int> x(N);
int main() {}

we end up evaluating its expensive initialization (and hitting the constexpr
loop/ops limit) four times:

1. expand_default_init -> maybe_constant_init
2. store_init_value -> maybe_constant_value
3. store_init_value -> maybe_constant_init
4. store_init_value -> cxx_constant_init

The first three silently fail due to hitting the ops limit, and the fourth
actually diagnoses the failure.  This seems wasteful, we should silently
evaluate such an initializer once.

For the original testcase where x is not constexpr, we constant evaluate the
initialization just once (which silently fails due to the ops limit), which
still takes a few seconds unfortunately.

[Bug libstdc++/113835] [13/14 Regression] compiling std::vector with const size in C++20 is slow

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Should we really be reaching the limits for cases like this?
I mean, all the default ctors produce the same value here and we could figure
out that
they are in no way dependent on the exact position of the element in the
vector, nor allocating heap memory during constexpr evaluation, so ideally we'd
optimize and just fill in the whole initializer with the same value (ideally
using range for the ctor index to even save compile time memory).
Guess the hard part is find out the cases where the constexpr evaluation for
element would be dependent on something that would prevent such an
optimization.

[Bug libstdc++/113835] [13/14 Regression] compiling std::vector with const size in C++20 is slow

[law at gcc dot gnu.org]

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

Jeffrey A. Law <law at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
                 CC|                            |law at gcc dot gnu.org