Slow lang_insert_orphan
H. J. Lu
hjl@lucon.org
Fri Mar 18 16:24:00 GMT 2005
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.
More information about the Binutils
mailing list