[GHC] #13739: Very slow linking of profiled executables

[GHC]

#13739: Very slow linking of profiled executables
-------------------------------------+-------------------------------------
        Reporter:  duog              |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.1-rc2
      Resolution:                    |             Keywords:
Operating System:  Linux             |         Architecture:  x86_64
 Type of failure:  Compile-time      |  (amd64)
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by duog):

 I have done some investigation and think I understand this now. Linking
 against libraries built with -split-sections is slow, and seems to be
 superlinear in the number of sections.

 I have been testing on HEAD, using BuildFlavour = Validate. By default,
 profiling libraries are not built, and SplitSections = No.

 Setting BUILD_PROF_LIBS = YES in build.mk and Linking the trivial program
 is only slightly slower than with 8.0.2 with and without -prof.

 I have been using the following command to count sections in library
 files, this is counting the sections in the profiled base I built without
 SplitSections:
 {{{
 objdump -xw libraries/base/dist-install/build/libHSbase-4.10.0.0_p.a | wc
 -l
 524008
 }}}
 This is counting the sections in the profiled base I got from launchpad:
 {{{
 objdump -xw
 /opt/ghc/8.2.1/lib/ghc-8.2.0.20170522/base-4.10.0.0/libHSbase-4.10.0.0_p.a
 | wc -l
 1022947
 }}}
 Now setting SplitSections = YES, cleaning and building libraries
 {{{
 objdump -xw libraries/base/dist-install/build/libHSbase-4.10.0.0_p.a | wc
 -l
 1031190
 }}}

 And the test case is as slow as it has been in my previous testing.
 I tried upgrading my gcc to 6.3.0, and this does not change the results. I
 haven't tried upgrading ld, I can't see how to do that.

 It looks like the libraries from launchpad, both profiled and unprofiled,
 were built with SplitSections = Yes. The prof build flavour does not set
 SplitSections = No, unlike all of the other ones, so I suspect they came
 from a prof build.

 I believe that the above explains what causes linking to be very slow, and
 why we have had difficulty reliably reproducing it. I don't know why many
 sections slows linking. My only idea comes from
 [http://eli.thegreenplace.net/2013/07/09/library-order-in-static-linking]:
 > Finally, if any of the objects in the library has been included in the
 link, the library is rescanned again - it's possible that symbols imported
 by the included object can be found in other objects within the same
 library.
 That algorithm sounds quadratic in the worst case.

 The following are the file sizes produced in various cases (83 has
 SplitSections libraries):
 {{{
 -rwxr-xr-x 1 doug fileservs  1507544 May 29 00:09 profiled_80
 -rwxr-xr-x 1 doug fileservs  1511320 May 29 00:09 profiled_83
 -rwxr-xr-x 1 doug fileservs 13138024 May 29 00:09 profiled_nogcsections_83
 -rwxr-xr-x 1 doug fileservs  1040752 May 29 00:09 unprofiled_80
 -rwxr-xr-x 1 doug fileservs   903616 May 29 00:09 unprofiled_83
 -rwxr-xr-x 1 doug fileservs  7923416 May 29 00:09
 unprofiled_nogcsections_83
 }}}
 and the times taken to produce them:
 {{{
 8.0 profiled command

 real    0m0.183s
 user    0m0.168s
 sys     0m0.012s
 8.2 profiled command

 real    0m14.764s
 user    0m14.616s
 sys     0m0.144s
 8.2 profiled command no gc-section s

 real    0m2.138s
 user    0m1.940s
 sys     0m0.192s
 8.0 unprofiled command

 real    0m0.179s
 user    0m0.140s
 sys     0m0.036s
 8.2 unprofiled command

 real    0m1.749s
 user    0m1.656s
 sys     0m0.088s
 8.2 unprofiled command no gc-sections

 real    0m1.373s
 user    0m1.220s
 sys     0m0.148s
 }}}

 ----
 I think SplitSections should not be enabled in prof.mk (or any others), at
 least for libraries.

 There is good reason to pass -Wl,--gc-sections to the linker always, since
 it lets you leverage libraries that have been compiled with -split-
 sections, but perhaps this is too dangerous while we don't understand
 exactly what causes the slowdown.

 There should be better interface than -fwhole-archive-hs-libs to disable
 --gc-sections while doing a profiling build. One or many of:
 * Don't pass --gc-sections if profiling is enabled
 * * unless another flag is passed
 * A warning if -prof is passed without -fwhole-archive-hs-libs
 * * add another flag that only disables --gc-sections

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13739#comment:17>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler