The assembly code generator seems to produce erroneous code. The linker is awfully slow. Release: gcc3.2 Environment: Linux Mandrake 9.0 (2.4.19-16mdk)
From: Manuel Serrano <Manuel.Serrano@sophia.inria.fr> To: gcc-gnats@gcc.gnu.org, nobody@gcc.gnu.org Cc: Subject: Re: c/8108: Problem in the code generator for C and the linker is extremelly slow Date: 25 Oct 2002 09:00:52 +0200 Hello there, Somtime ago I have posted a bug report of gcc3.2 and I have received the following: > Thank you very much for your problem report. > It has the internal identification `c/8108'. > The individual assigned to look at your > report is: unassigned. > > >Category: c > >Responsible: unassigned > >Synopsis: Problem in the code generator for C and the linker is extremelly slow > >Arrival-Date: Tue Oct 01 08:16:02 PDT 2002 This that time I have made extra experiments with several versions of Linux. I confirm that the problem comes from gcc3.2. With all the Linux kernels (2.4.18, 2.4.19, 2.4.20pre11), with all the file systems (ext2, ext3, reiserfs) I have tested, linking my huge (about 1 million lines of C code) last about a couple of seconds with gcc2.95 and gcc2.96 while it last about 40 minutes with gcc3.2. Are you aware of this problem? Do you think that it will be fixed for the next version of gcc? Many thanks in advance. -- Manuel
State-Changed-From-To: open->feedback State-Changed-Why: Unfortunately, your report does not contain a self-contained testcase, i.e. a file (including a main function) that when compiled with a different set of flags or with a different compiler produces differing output. Please take a look at the bug reporting instructions at the gcc homepage (http://gcc.gnu.org/). Regarding the long linker times: this is likely a problem with the linker, not with gcc. Did you observe the slowdown on the _same_ machine, i.e. using the same linker but different versions of the linker? Or was that on different machines with different linkers? Thanks Wolfgang
State-Changed-From-To: feedback->closed State-Changed-Why: Submitter has notified me of no interest to provide a testcase.
From: Wolfgang Bangerth <bangerth@ticam.utexas.edu> To: gcc-gnats@gcc.gnu.org Cc: Subject: Re: c/8108: Problem in the code generator for C and the linker is extremelly slow Date: Wed, 8 Jan 2003 08:26:03 -0600 (CST) ---------- Forwarded message ---------- Date: Wed, 8 Jan 2003 09:04:13 +0100 From: Manuel Serrano <Manuel.Serrano@sophia.inria.fr> To: bangerth@dealii.org Subject: Re: c/8108: Problem in the code generator for C and the linker is extremelly slow > Unfortunately, your report does not contain a self-contained > testcase, i.e. a file (including a main function) that when > compiled with a different set of flags or with a different > compiler produces differing output. Please take a look at > the bug reporting instructions at the gcc homepage > (http://gcc.gnu.org/). > > Regarding the long linker times: this is likely a problem > with the linker, not with gcc. Did you observe the > slowdown on the _same_ machine, i.e. using the same linker > but different versions of the linker? Or was that on > different machines with different linkers? Sorry, as I have said in my previous mail, the problem was too essential: Gcc3.2 (or the linker) was simply not usable for me as is. I have downgraded to gcc2.95 since a long time and I don't have access anymore to any gcc3.2xxx releases. Sorry but I can't help anymore. -- Manuel
Hi, I have also encountered this problem and, after spending some time profiling and analyzing ld, have found what the problem is: It seems that ld uses a non-optimal algorithm to merge strings. This is done, if I understand correctly, to be able to represent strings that are suffixes of other strings as pointers into the longer string. Even though some hashing is used in ld to reduce the search time, the employed algorithm has more or less quadratic runtime in the number of strings. I assume that the placement of debug information has changed between older gcc versions and newer gcc versions and that now the debug information is also mergable. This may lead to a dramatic increase in linking time when switching from older versions to newer (3.2.2 for me) release. I have encountered a rise from ~10 seconds to ~1h. Suggestion: of course this should best be fixed in ld directly, and I will talk to the guys there, but it would also help if gcc would receive an option that makes it treat debug information as non-mergable data. BR Stephan
Subject: Re: Problem in the code generator for C and the linker is extremelly slow Hello Stephan, > I have also encountered this problem and, after spending some time profiling and > analyzing ld, have found what the problem is: > > It seems that ld uses a non-optimal algorithm to merge strings. This is done, if > I understand correctly, to be able to represent strings that are suffixes of > other strings as pointers into the longer string. Even though some hashing is > used in ld to reduce the search time, the employed algorithm has more or less > quadratic runtime in the number of strings. > > I assume that the placement of debug information has changed between older gcc > versions and newer gcc versions and that now the debug information is also mergable. > > This may lead to a dramatic increase in linking time when switching from older > versions to newer (3.2.2 for me) release. I have encountered a rise from ~10 > seconds to ~1h. > > Suggestion: of course this should best be fixed in ld directly, and I will talk > to the guys there, but it would also help if gcc would receive an option that > makes it treat debug information as non-mergable data. I'm happy (well, not really), to see that I'm not the only one having this problem with gcc3. I have had the feeling that my problem was interesting exactly nobody. This is why I'm still using gcc2.95 :-( The gcc3.2's option "-fno-merge-constants" gets rid of the problem. Unfortunately it has no effect with gcc3.3 (well, I have not tested recent versions, may be this has improved now).
Subject: Re: Problem in the code generator for C and the linker is extremelly slow ext Manuel Serrano wrote: >Hello Stephan, > > > >>I have also encountered this problem and, after spending some time profiling and >>analyzing ld, have found what the problem is: >> >>It seems that ld uses a non-optimal algorithm to merge strings. This is done, if >>I understand correctly, to be able to represent strings that are suffixes of >>other strings as pointers into the longer string. Even though some hashing is >>used in ld to reduce the search time, the employed algorithm has more or less >>quadratic runtime in the number of strings. >> >>I assume that the placement of debug information has changed between older gcc >>versions and newer gcc versions and that now the debug information is also mergable. >> >>This may lead to a dramatic increase in linking time when switching from older >>versions to newer (3.2.2 for me) release. I have encountered a rise from ~10 >>seconds to ~1h. >> >>Suggestion: of course this should best be fixed in ld directly, and I will talk >>to the guys there, but it would also help if gcc would receive an option that >>makes it treat debug information as non-mergable data. >> >> >I'm happy (well, not really), to see that I'm not the only one having this >problem with gcc3. I have had the feeling that my problem was interesting >exactly nobody. This is why I'm still using gcc2.95 :-( > > No, when we start building large systems with lots of automatically generated code, we run into this problem quite relyably, not only for one system. Sticking with an old gcc is currecntly also the only option for us :-(. >The gcc3.2's option "-fno-merge-constants" gets rid of the problem. >Unfortunately it has no effect with gcc3.3 (well, I have not tested recent >versions, may be this has improved now). > > Unfortunately, this is not really the case for us. We do not have that many string constants in our code, so setting this option does not change our linking times at all. What seems to be the killer for me is the debug information. Currently there is no option to treat debug info as non-mergable. I have already seen a gcc patch floating around that achieves this, but I don't think that it is considered for inclusion into the main gcc development, or even has been submitted. There is a version of the binutils in the making (2.15) which will solve the problem from the point of view of ld. They have a much improved string merging algorithm that reduces link times for me from ~3000s to ~40s. This is still worse than the original ~7s (for gcc-2.95.x generated objects) but it is 2 orders of magnitudes down. BR Stephan Tobies
Subject: Re: Problem in the code generator for C and the linker is extremelly slow > No, when we start building large systems with lots of automatically > generated code, we run into this problem quite relyably, not only for > one system. Sticking with an old gcc is currecntly also the only option > for us :-(. I see, we are having the very same troubles and very same solutions :-( > >The gcc3.2's option "-fno-merge-constants" gets rid of the problem. > >Unfortunately it has no effect with gcc3.3 (well, I have not tested recent > >versions, may be this has improved now). > > > > > Unfortunately, this is not really the case for us. We do not have that > many string constants in our code, so setting this option does not > change our linking times at all. What seems to be the killer for me is > the debug information. Currently there is no option to treat debug info > as non-mergable. I have already seen a gcc patch floating around that > achieves this, but I don't think that it is considered for inclusion > into the main gcc development, or even has been submitted. Same things for me. The real pain is when I try to compile in C debug mode... > There is a version of the binutils in the making (2.15) which will solve > the problem from the point of view of ld. They have a much improved > string merging algorithm that reduces link times for me from ~3000s to > ~40s. This is still worse than the original ~7s (for gcc-2.95.x > generated objects) but it is 2 orders of magnitudes down. I would by, at once, a 2x slowdown ;-)
Subject: Re: Problem in the code generator for C and the linker is extremelly slow ext Manuel Serrano wrote: > [snip] > >>There is a version of the binutils in the making (2.15) which will solve >>the problem from the point of view of ld. They have a much improved >>string merging algorithm that reduces link times for me from ~3000s to >>~40s. This is still worse than the original ~7s (for gcc-2.95.x >>generated objects) but it is 2 orders of magnitudes down. >> >> >I would by, at once, a 2x slowdown ;-) > > I have profiled this some more. Most of the time spent now during linking is no longer in the string merging, but instead in the general merging process. I have basically no clue of how object files are structured and how linking takes places, but it would seem to me that ld has done most of what they can do to solve the problem of the increased link time. I cannot judge if the slow down in the linker is now still due to the way that debug information is represented, of if this is general problem/feature of how the later gcc's structure the object files. Maybe somebody from the gcc maintainers will take on this problem - I would offer my help to nail down the problem. BR Stephan
I have found a patch for gcc which claims to solve exactly this problem here (haven't tested it though): http://lists.boost.org/MailArchives/boost/msg53004.php So it seems there are now at least 3 parties independent parties who seem to suffer from this problem Ok, the upcoming 2.15 release of ld will solve the problem somewhat, but it would still be great if this could also be tackled from gcc's side.
The problem is clearer now, and there is supposedly a patch out there. So reopening this PR. W.
Not related to C front end, patch suggests related to debug info generation so changing component accordingly.
Still this is not a gcc bug but rather a big preformance bug in binutils report it to them. Also there is no proper testcase in here to test.
actually this is a problem where GCC *can* help, as demonstrated by the patch linked to from comment #10
(In reply to comment #14) > actually this is a problem where GCC *can* help, as demonstrated > by the patch linked to from comment #10 That patch just disables the merging of the debugging strings which means the debugging info will be much larger than needed. This is still better solved in the LD really. It might be the case it already has but I have not looked into binutils linker sources lately.
It has been fixed in the linker now.