Re: Slow lang_insert_orphan

[Alan Modra <amodra at bigpond dot net dot au>]

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.)

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre