[PATCH 0/8] ld: Speed up section selection

[PATCH 0/8] ld: Speed up section selection

[Michael Matz]

Hello,

so this series rewrites how ld selects sections, i.e. how the globs inside 
linker scripts are evaluated.  My speed testcase is always linking cc1, 
a reasonably sized c++ program with many input files and sections (due to 
templates and section groups).  I will use x86-64.  The characteristics of 
that testcase are:

* 674 input files
* 300050 input sections
* 129 wild statements in the linker script
* 179 section selecttors in these wild statements (not all of them globs)

With an -O2 build ld.bfd we start with this before the series:

overall link time:
           4.2823 +- 0.0188 seconds time elapsed  ( +-  0.44% )

relevant pieces of the profile (overall this has 16900 samples):
     percentage    Samples program shared object symbol name
     5.82%           937  ld-new   ld-new        walk_wild_section_specs3_wild2
     4.45%           718  ld-new   ld-new        walk_wild_section_specs1_wild1
     2.97%           480  ld-new   ld-new        walk_wild_section_specs2_wild1
     1.97%           317  ld-new   ld-new        walk_wild_section_general
     0.85%           137  ld-new   ld-new        match_simple_wild

After the series this will be:

overall link time:
           3.62733 +- 0.00779 seconds time elapsed  ( +-  0.21% )

relevant pieces of the profile (overall this has 14244 samples):
     percentage    Samples program shared object symbol name
     0.67%            97  ld-new   ld-new        resolve_wild_sections.part.0
 
Yep, that's it, 97 samples remain from the initial 2500 samples for the 
whole of section selection.  I have further patches that speedup GNU ld, 
but this series is only about the section selection process, which is the 
second top-most profile entry and the only code taking considerable time 
that isn't in libbfd.

The way the series works is to first reshuffle the order of the overall 
loop structure matching all sections against all wild statements.  Then we 
can memoize these results (which needs some adjustments), then we can use 
a prefix tree to quickly rule out possible matches, and then we cleaup.

For review purpose I decided to not merge together some of the patches in 
the series.  In particular it adds some interface into libbfd (in 2/8) 
that gets removed again later (in 7/8).  Also the patches adding 
functionality often only comment out the old variants that are then only 
removed in a later patch.  I think in this case that makes it easier to 
review (I looked at the overall squashed patch and it's quite confusing).

I will also have a question in 4/8 whose answer might make the bfd change 
useful, so that it wouldn't have to be removed.

I've tested the whole series without regression on all of Alans targets 
(158 of them).  So, okay for master? :)


Ciao,
Michael.


Michael Matz (8):
  section-select: Lazily resolve section matches
  section-select: Deal with sections added late
  section-select: Implement a prefix-tree
  section-select: Completely rebuild matches
  section-select: Remove unused code
  section-select: Cleanup
  section-select: Remove bfd_max_section_id again
  section-select: Fix exclude-file-3

 ld/ldlang.c                                | 672 +++++++++------------
 ld/ldlang.h                                |  13 +-
 ld/testsuite/ld-scripts/exclude-file-3.map |   4 +-
 3 files changed, 295 insertions(+), 394 deletions(-)

-- 
2.36.1

Re: [PATCH 0/8] ld: Speed up section selection

[Alan Modra]

On Fri, Nov 25, 2022 at 04:44:23PM +0000, Michael Matz via Binutils wrote:
>   section-select: Lazily resolve section matches
>   section-select: Deal with sections added late
>   section-select: Implement a prefix-tree
>   section-select: Completely rebuild matches
>   section-select: Remove unused code
>   section-select: Cleanup
>   section-select: Remove bfd_max_section_id again
>   section-select: Fix exclude-file-3
> 
>  ld/ldlang.c                                | 672 +++++++++------------
>  ld/ldlang.h                                |  13 +-
>  ld/testsuite/ld-scripts/exclude-file-3.map |   4 +-

OK.

-- 
Alan Modra
Australia Development Lab, IBM

Re: [PATCH 0/8] ld: Speed up section selection

[Michael Matz]

Hello,

On Wed, 30 Nov 2022, Alan Modra wrote:

> On Fri, Nov 25, 2022 at 04:44:23PM +0000, Michael Matz via Binutils wrote:
> >   section-select: Lazily resolve section matches
> >   section-select: Deal with sections added late
> >   section-select: Implement a prefix-tree
> >   section-select: Completely rebuild matches
> >   section-select: Remove unused code
> >   section-select: Cleanup
> >   section-select: Remove bfd_max_section_id again
> >   section-select: Fix exclude-file-3
> > 
> >  ld/ldlang.c                                | 672 +++++++++------------
> >  ld/ldlang.h                                |  13 +-
> >  ld/testsuite/ld-scripts/exclude-file-3.map |   4 +-
> 
> OK.

Thanks (885d8643).  I've cosmetically shuffled the series and squashed 
some commits, but the end result is textually the same, so I'm not 
resending a v2.


Ciao,
Michael.