Slow lang_insert_orphan
Alan Modra
amodra@bigpond.net.au
Fri Mar 18 15:08:00 GMT 2005
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
More information about the Binutils
mailing list