[Bug c++/55402] New: Compiling large initializer lists never finishes

[Bug c++/55402] New: Compiling large initializer lists never finishes

[kevin at topsy dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

             Bug #: 55402
           Summary: Compiling large initializer lists never finishes
    Classification: Unclassified
           Product: gcc
           Version: 4.7.2
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: kevin@topsy.com


An initializer list of tens of thousands of simple std::pair<...> causes GCC
4.7.2 to busily never return.

Command line:

kevin@ps027:~$ cat /proc/version
Linux version 2.6.32-32-server (buildd@allspice) (gcc version 4.4.3 (Ubuntu
4.4.3-4ubuntu5) ) #62-Ubuntu SMP Wed Apr 20 22:07:43 UTC 2011
kevin@ps027:~$ g++-4.7 --version
g++-4.7 (Ubuntu/Linaro 4.7.2-2+ub1) 4.7.2
Copyright (C) 2012 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

kevin@ps027:~$ g++ -std=c++0x -save-temps hang.cc
(never returns, compiler forever busy)

[Bug c++/55402] Compiling large initializer lists never finishes

[kevin at topsy dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

--- Comment #1 from Kevin Hsu <kevin at topsy dot com> 2012-11-19 22:27:00 UTC ---
In the example, the initializer list has maybe around 60,000 elements. This is
pretty large, but by no means a corner case.

[Bug c++/55402] Compiling large initializer lists never finishes

[kevin at topsy dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

--- Comment #2 from Kevin Hsu <kevin at topsy dot com> 2012-11-19 22:28:53 UTC ---
Created attachment 28737
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28737
The .cc file, gzip'd

In case it helps (gzipped)

[Bug c++/55402] Compiling large initializer lists never finishes

[kevin at topsy dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

--- Comment #3 from Kevin Hsu <kevin at topsy dot com> 2012-11-19 22:30:48 UTC ---
Created attachment 28738
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28738
intermediate file, gzipped

[Bug c++/55402] Compiling large initializer lists never finishes

[kevin at topsy dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

--- Comment #4 from Kevin Hsu <kevin at topsy dot com> 2012-11-19 22:32:35 UTC ---
(In reply to comment #0)
> An initializer list of tens of thousands of simple std::pair<...> causes GCC
> 4.7.2 to busily never return.
> 
> Command line:
> 
> kevin@ps027:~$ cat /proc/version
> Linux version 2.6.32-32-server (buildd@allspice) (gcc version 4.4.3 (Ubuntu
> 4.4.3-4ubuntu5) ) #62-Ubuntu SMP Wed Apr 20 22:07:43 UTC 2011
> kevin@ps027:~$ g++-4.7 --version
> g++-4.7 (Ubuntu/Linaro 4.7.2-2+ub1) 4.7.2
> Copyright (C) 2012 Free Software Foundation, Inc.
> This is free software; see the source for copying conditions.  There is NO
> warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
> 
> kevin@ps027:~$ g++ -std=c++0x -save-temps hang.cc
> (never returns, compiler forever busy)

Oops, the actual command line used was indeed g++-4.7:

kevin@ps027:~$ g++-4.7 -std=c++0x -save-temps hang.cc

[Bug c++/55402] Compiling large initializer lists never finishes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-11-20
     Ever Confirmed|0                           |1

--- Comment #5 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-11-20 00:16:22 UTC ---
I don't think it's correct to say that it *never* finishes - the memory usage
also doesn't diverge - it's just extremely slow. We have of course to analyze
why (as far as I know nobody tested so far this typical ;) case).

[Bug c++/55402] Compiling large initializer lists never finishes

[kevin at topsy dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

--- Comment #6 from Kevin Hsu <kevin at topsy dot com> 2012-11-20 00:24:11 UTC ---
(In reply to comment #5)
> I don't think it's correct to say that it *never* finishes - the memory usage
> also doesn't diverge - it's just extremely slow. We have of course to analyze
> why (as far as I know nobody tested so far this typical ;) case).

Right, I did test with a few thousand entries, and it did come back. It feels
like there's a exponential issue somewhere... Anyways, thank you for looking
into this :)

The use case we encountered was that we have a global data structure with
around 25,000 pairs known at compile time. So, we naturally generated the code
file. I haven't tested whether this happens at all with std::unordered_map or
other containers.

My workaround was to change the ctor to take a pointer to the entries with a
count. In that case, the C-style initialization compiles in expected time.

[Bug c++/55402] Compiling large initializer lists never finishes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

Paolo Carlini <paolo.carlini at oracle dot com> changed:

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

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-11-20 11:13:10 UTC ---
Steven, are you willing to have a look and figure out what we are doing wrong?

[Bug c++/55402] Compiling large initializer lists never finishes

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog
             Status|NEW                         |ASSIGNED
                 CC|steven at gcc dot gnu.org   |
         AssignedTo|unassigned at gcc dot       |steven at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #8 from Steven Bosscher <steven at gcc dot gnu.org> 2012-11-20 11:20:23 UTC ---
I'll have a look...

[Bug c++/55402] Compiling large initializer lists never finishes

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-11-20 11:43:27 UTC ---
I believe the expensive part here is the EH, we end up with > 56000 nested
try/finally constructs.  With -fno-exceptions this compiles in reasonable time
(even for the insane testcase), at least without optimizations, with
optimizations costly phases are e.g. the inliner (remember there are hundreds
of thousands of calls to inline).
For EH, I think it would help if at least for the larger initializer list the
compiler emitted just a single try/finally, where if exception is thrown during
construction of some element, it would just loop over all the older elements in
the array (starting from previous one down to first) that would destruct them.

[Bug c++/55402] Compiling large initializer lists never finishes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

Paolo Carlini <paolo.carlini at oracle dot com> changed:

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

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-11-20 12:26:13 UTC ---
I see, thanks Jakub. Let's add Jason too in CC. For now only wanted to add
that, for the exceptions, an hackish but effective local workaround would be
marking the constructor noexcept.

[Bug c++/55402] Compiling large initializer lists never finishes

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55402

--- Comment #11 from Steven Bosscher <steven at gcc dot gnu.org> 2013-03-06 10:30:20 UTC ---
Maybe the issues in this bug are the same as those for bug 55135.