Slow lang_output_section_find_1

["H. J. Lu" <hjl at lucon dot org>]

On Fri, Mar 18, 2005 at 11:44:31PM +1030, Alan Modra wrote:
> On Fri, Mar 18, 2005 at 10:01:03AM +0000, Nick Clifton wrote:
> > Hi H. J.
> > 
> > >When we have many orphaned sections, lang_insert_orphan spends lots
> > >of time in
> > >
> > >/* Unlink the section.  */
> > >for (pps = &output_bfd->sections; *pps != snew; pps = &(*pps)->next)
> > >  continue;
> > >
> > >It is the case of 64K section ld test. Use a doubly linked list
> > >for section may help. But it will add a pointer to bfd_section. Should
> > >I give a try?
> > 
> > I am reluctant to increase the size of the bfd_section structure.  Maybe 
> >  lang_insert_orphans() could be made smarter with a different algorithm 
> > ?  Possibly it could keep a local bitmap or list of sections to unlink 
> > and then only unlink them all right at the end ?
> 
> Yes, I think you could try other approaches first.  For instance
> I think it would be better to ask ourselves whether this list really
> needs to be ordered.  Before I wrote this code, orphan sections appeared
> at the end of the section list.  As the comment says, shuffling the
> section list was only cosmetic, but now I see some code has crept into
> lang_size_section, for DATA_SEGMENT_ALIGN, that depends on correct
> section ordering.  The lang_size_section code could easily be rewritten
> to traverse the lang_output_section_statement list instead.
> 
> If we do care about the ordering, then perhaps delay sorting the
> bfd_section list according to the output section statement list until
> after all orphans have been added.  Hmm, probably the best thing would
> be to save output_bfd->section_tail before adding the orphan.  Then you
> know how to unlink the orphan without looking through the list.  (I
> think the orphan code predated the section hash table and section_tail.)

With Alan's fix to lang_insert_orphan, lang_output_section_find_1
becomes the most time consuming part of ld:

 62.81   1156.48  1156.48        1     1.16     1.83  lang_process
 32.51   1755.16   598.68   128089     0.00     0.00 lang_output_section_find_1
  2.43   1799.93    44.77   640881     0.00     0.00  bfd_hash_lookup
  1.22   1822.38    22.45    13002     0.00     0.00  walk_wild_section
  0.16   1825.26     2.88   128221     0.00     0.00 get_special_section

I don't think the current linker is designed to support many many output
sections. Should we use a hash table or doubly linked list to avoid
the linear search over a linked list of more than 64K sections?


H.J.