Re: Slow lang_insert_orphan

["H. J. Lu" <hjl@lucon.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.)
> 

It isn't just lang_insert_orphan:

# find -name *.* | xargs grep bfd_section_list_remove
./bfd/bfd-in2.h:#define bfd_section_list_remove(ABFD, PS) \
./bfd/coffcode.h:         bfd_section_list_remove (abfd, ps);
./bfd/elf32-i370.c:               bfd_section_list_remove
(s->output_section->owner, spp);
./bfd/elf64-mmix.c:      bfd_section_list_remove (abfd, secpp);
./bfd/section.c:.#define bfd_section_list_remove(ABFD, PS) \
./bfd/sunos.c:  bfd_section_list_remove (abfd, ps);
./bfd/xcofflink.c:                    bfd_section_list_remove (abfd,
st);
./bfd/elfxx-mips.c:           bfd_section_list_remove (abfd, secpp);
./gas/config/obj-ecoff.c:           bfd_section_list_remove (stdoutput,
sec);
./gas/config/tc-mmix.c:      bfd_section_list_remove (stdoutput,
secpp);
./gas/config/tc-xtensa.c:  /* Handle brain-dead bfd_section_list_remove
macro, which
./gas/config/tc-xtensa.c:  bfd_section_list_remove (stdoutput,
ps_next_ptr);
./gas/write.c:      bfd_section_list_remove (stdoutput, seclist);
./ld/ldlang.c:      bfd_section_list_remove (output_bfd, pps);
./ld/ldlang.c:          bfd_section_list_remove (output_bfd, p);
./ld/emultempl/elf32.em:                    bfd_section_list_remove
(output_bfd, p);

We are lucky so far that bfd_section_list_remove is only called a few
times in most places and most of files don't have that many sections.


H.J.