Bug 86320 - very long compilation time for std::array<std::pair<int, int>, 1024 * 1024>
Summary: very long compilation time for std::array<std::pair<int, int>, 1024 * 1024>
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: c++ (show other bugs)
Version: 8.1.1
: P3 normal
Target Milestone: 8.2
Assignee: Jason Merrill
URL:
Keywords: compile-time-hog, memory-hog
Depends on:
Blocks:
 
Reported: 2018-06-26 10:27 UTC by Ulya
Modified: 2018-06-27 06:17 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2018-06-26 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Ulya 2018-06-26 10:27:07 UTC

    
Comment 1 Ulya 2018-06-26 10:36:33 UTC
Compilation takes very long time for an array of tuples. Time depends on the length of an array. Clang doesn't seem to have this problem. 

// 1.cpp
#include <array>
#include <utility>

void foo ()
{
  std::array<std::pair<int, int>, 1024 * 1024> arr {};
}

$ time g++ --std=c++11 -c 1.cpp

real    0m48.344s
user    0m45.545s
sys     0m2.306s

$ time clang++ --std=c++11 -c 1.cpp

real    0m0.540s
user    0m0.322s
sys     0m0.030s

A quick check shows that previous GCC version are affected as well:

https://godbolt.org/g/s3yudL the previous GCC versions 

Finally, this the following program with a user-defined 'pair' type compiles fast:

#include <array>

template <typename T, typename U>
struct pair
{
  T t;
  U u;
};

void foo ()
{
  std::array<pair<int, int>, 1024 * 1024> arr {};
}

$ time g++ --std=c++11 -c 1.cpp

real    0m0.172s
user    0m0.159s
sys     0m0.011s
Comment 2 Jonathan Wakely 2018-06-26 11:13:12 UTC
Jason, is this a dup of PR 80290?

Time variable                                   usr           sys          wall               GGC
 phase setup                        :   0.01 (  0%)   0.00 (  0%)   0.02 (  0%)    1468 kB (  0%)
 phase parsing                      :  66.83 ( 99%)  28.56 (100%)  95.67 ( 99%)10574003 kB (100%)
 phase lang. deferred               :   0.35 (  1%)   0.01 (  0%)   0.35 (  0%)    3668 kB (  0%)
 phase opt and generate             :   0.19 (  0%)   0.00 (  0%)   0.19 (  0%)     797 kB (  0%)
 |name lookup                       :   0.47 (  1%)   0.20 (  1%)   0.97 (  1%)    1362 kB (  0%)
 |overload resolution               :  29.76 ( 44%)  13.39 ( 47%)  43.55 ( 45%) 4895039 kB ( 46%)
 garbage collection                 :   1.20 (  2%)   0.01 (  0%)   1.21 (  1%)       0 kB (  0%)
 callgraph construction             :   0.08 (  0%)   0.00 (  0%)   0.08 (  0%)     738 kB (  0%)
 preprocessing                      :   0.02 (  0%)   0.03 (  0%)   0.04 (  0%)    1064 kB (  0%)
 parser (global)                    :   0.05 (  0%)   0.04 (  0%)   0.09 (  0%)    7717 kB (  0%)
 parser struct body                 :   0.01 (  0%)   0.01 (  0%)   0.05 (  0%)    3910 kB (  0%)
 parser function body               :  28.76 ( 43%)  12.76 ( 45%)  42.13 ( 44%) 5804556 kB ( 55%)
 parser inl. func. body             :   0.04 (  0%)   0.00 (  0%)   0.00 (  0%)     721 kB (  0%)
 parser inl. meth. body             :   0.01 (  0%)   0.00 (  0%)   0.04 (  0%)    1605 kB (  0%)
 template instantiation             :  28.70 ( 43%)  11.93 ( 42%)  40.94 ( 43%) 3951992 kB ( 37%)
 constant expression evaluation     :   8.39 ( 12%)   3.79 ( 13%)  11.50 ( 12%)  802859 kB (  8%)
 integrated RA                      :   0.10 (  0%)   0.00 (  0%)   0.10 (  0%)      24 kB (  0%)
 symout                             :   0.00 (  0%)   0.00 (  0%)   0.02 (  0%)    3280 kB (  0%)
 initialize rtl                     :   0.01 (  0%)   0.00 (  0%)   0.01 (  0%)      12 kB (  0%)
 TOTAL                              :  67.38         28.57         96.23       10579989 kB
Extra diagnostic checks enabled; compiler may run slowly.
Configure with --enable-checking=release to disable checks.
Comment 3 Jason Merrill 2018-06-26 18:46:01 UTC
Not a duplicate, but related.
Comment 4 Jason Merrill 2018-06-27 03:00:36 UTC
Author: jason
Date: Wed Jun 27 02:59:44 2018
New Revision: 262173

URL: https://gcc.gnu.org/viewcvs?rev=262173&root=gcc&view=rev
Log:
	PR c++/86320 - memory-hog with std::array of pair

	* typeck2.c (process_init_constructor_array): Only compute a
	constant initializer once.

In this PR, we have a large std::array of pairs.  Since the C array is
wrapped in a class we don't go to build_vec_init, so we end up with
digest_init wanting to build up the element initializer for each element of
the array.

In the more general case, like 80272, we have a data structure problem: we
don't currently have a good way of expressing the same dynamic
initialization of many elements within a CONSTRUCTOR.  RANGE_EXPR probably
ought to work, but will need more work at genericize or gimplify time.

But in this case, the initialization for each element reduces to constant
0, so we don't even need to add anything to the CONSTRUCTOR.  We just need
to realize that if the initializer for one element is 0, the others will be
as well, and we don't need to iterate over the whole array.

For the trunk, I also use a RANGE_EXPR to handle constant initialization by
a value other than 0.

void foo ()
{
  std::array<std::pair<int, int>, 1024 * 1024> arr {};
}

Modified:
    trunk/gcc/cp/ChangeLog
    trunk/gcc/cp/typeck2.c
Comment 5 Jason Merrill 2018-06-27 03:07:15 UTC
Author: jason
Date: Wed Jun 27 03:06:43 2018
New Revision: 262175

URL: https://gcc.gnu.org/viewcvs?rev=262175&root=gcc&view=rev
Log:
	PR c++/86320 - memory-hog with std::array of pair

	* typeck2.c (process_init_constructor_array): If zero-initialization
	is fine for one element, we're done.

Modified:
    branches/gcc-8-branch/gcc/cp/ChangeLog
    branches/gcc-8-branch/gcc/cp/typeck2.c
Comment 6 Jason Merrill 2018-06-27 03:09:04 UTC
Fixed.
Comment 7 Ulya 2018-06-27 06:17:29 UTC
Thank you, that was really fast!