Slow lang_insert_orphan

Slow lang_insert_orphan

[H. J. Lu]

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?


H.J.

Re: Slow lang_insert_orphan

[Nick Clifton]

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 ?

Cheers
   Nick

Re: Slow lang_insert_orphan

[Alan Modra]

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

Re: Slow lang_insert_orphan

[Alan Modra]

On Fri, Mar 18, 2005 at 11:44:31PM +1030, Alan Modra wrote:
> 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.)

Committing to mainline.

	* ldlang.c (lang_insert_orphan): Use old section_tail rather than
	traversing the bfd section list to find pointer to new section.

Index: ld/ldlang.c
===================================================================
RCS file: /cvs/src/src/ld/ldlang.c,v
retrieving revision 1.175
diff -u -p -r1.175 ldlang.c
--- ld/ldlang.c	17 Mar 2005 16:20:19 -0000	1.175
+++ ld/ldlang.c	18 Mar 2005 13:50:24 -0000
@@ -818,6 +818,7 @@ lang_insert_orphan (lang_input_statement
   etree_type *load_base;
   lang_output_section_statement_type *os;
   lang_output_section_statement_type **os_tail;
+  asection **bfd_tail;
 
   /* Start building a list of statements for this section.
      First save the current statement pointer.  */
@@ -871,6 +872,7 @@ lang_insert_orphan (lang_input_statement
 
   os_tail = ((lang_output_section_statement_type **)
 	     lang_output_section_statement.tail);
+  bfd_tail = output_bfd->section_tail;
   os = lang_enter_output_section_statement (secname, address, 0, NULL, NULL,
 					    load_base, 0);
 
@@ -902,7 +904,7 @@ lang_insert_orphan (lang_input_statement
 
   if (after != NULL && os->bfd_section != NULL)
     {
-      asection *snew, **pps;
+      asection *snew;
 
       snew = os->bfd_section;
 
@@ -929,9 +931,8 @@ lang_insert_orphan (lang_input_statement
 	place->section = &output_bfd->sections;
 
       /* Unlink the section.  */
-      for (pps = &output_bfd->sections; *pps != snew; pps = &(*pps)->next)
-	continue;
-      bfd_section_list_remove (output_bfd, pps);
+      ASSERT (*bfd_tail == snew);
+      bfd_section_list_remove (output_bfd, bfd_tail);
 
       /* Now tack it back on in the right place.  */
       bfd_section_list_insert (output_bfd, place->section, snew);

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: Slow lang_insert_orphan

[H. J. Lu]

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.

Slow lang_output_section_find_1

[H. J. Lu]

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.

Re: Slow lang_output_section_find_1

[Alan Modra]

On Fri, Mar 18, 2005 at 11:33:25AM -0800, H. J. Lu wrote:
> With Alan's fix to lang_insert_orphan, lang_output_section_find_1
> becomes the most time consuming part of ld:

Yes, I meant to comment on that last night.  We need to do something
about the lang_output_section_statement list.  A hash would work, but it
seems silly to have a bfd section hash that duplicates most if not all
entries that would be in the lang_output_section_statement list.  Hmm..
Probably best not to be too clever.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre