[PATCH] Optimize ldlang_add_file for large input quantities

[Noah Misch]

I collected a profile of GNU ld while it linked a local application.  In this
invocation, ldlang_add_file used 21.7% of the linker run time.  The application
in question generates many thousands of input BFDs, each rather small; as such,
the linker spends a relatively large amount of time repeatedly finding the
input_bfds tail.  This patch makes ld store that tail, clearing this bottleneck.

The following fanciful link illustrates the difference:

  echo 'static int foo = 5;' >foo.c
  gcc -c foo.c

  i=10000
  while test $i -gt 0; do
      ln -s foo.o f-$i.o
      i=$(($i - 1))
  done

  echo 'int main() {return 0;}' >main.c
  gcc -c main.c
  time gcc f-*.o main.o

CVS ld, without patch:
15.61user 1.86system 0:17.47elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+91982minor)pagefaults 0swaps

with patch:
3.84user 1.47system 0:05.31elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+91983minor)pagefaults 0swaps

The test suite shows no regressions on i686-pc-linux-gnu.


2007-05-26  Noah Misch  <noah@cs.caltech.edu>

	include/
	* bfdlink.h (struct bfd_link_info): Add input_bfds_tail.
	
	ld/
	* ldlang.c (ldlang_add_file): Use input_bfds_tail.

diff -urp -X /home/nm/src/cvs/dontdiff src-clean/include/bfdlink.h src-many_input/include/bfdlink.h
--- src-clean/include/bfdlink.h	2007-04-30 10:06:40.000000000 -0400
+++ src-many_input/include/bfdlink.h	2007-05-26 09:42:58.000000000 -0400
@@ -396,6 +396,9 @@ struct bfd_link_info
      together via the link_next field.  */
   bfd *input_bfds;
 
+  /* Tail of the above list of input BFDs. */
+  bfd *input_bfds_tail;
+
   /* If a symbol should be created for each input BFD, this is section
      where those symbols should be placed.  It must be a section in
      the output BFD.  It may be NULL, in which case no such symbols
diff -urp -X /home/nm/src/cvs/dontdiff src-clean/ld/ldlang.c src-many_input/ld/ldlang.c
--- src-clean/ld/ldlang.c	2007-05-01 21:22:40.000000000 -0400
+++ src-many_input/ld/ldlang.c	2007-05-26 10:39:39.000000000 -0400
@@ -5435,8 +5435,6 @@ lang_for_each_file (void (*func) (lang_i
 void
 ldlang_add_file (lang_input_statement_type *entry)
 {
-  bfd **pp;
-
   lang_statement_append (&file_chain,
 			 (lang_statement_union_type *) entry,
 			 &entry->next);
@@ -5445,9 +5443,11 @@ ldlang_add_file (lang_input_statement_ty
      a link.  */
   ASSERT (entry->the_bfd->link_next == NULL);
   ASSERT (entry->the_bfd != output_bfd);
-  for (pp = &link_info.input_bfds; *pp != NULL; pp = &(*pp)->link_next)
-    ;
-  *pp = entry->the_bfd;
+  if (link_info.input_bfds == NULL)
+    link_info.input_bfds = entry->the_bfd;
+  else
+    link_info.input_bfds_tail->link_next = entry->the_bfd;
+  link_info.input_bfds_tail = entry->the_bfd;
   entry->the_bfd->usrdata = entry;
   bfd_set_gp_size (entry->the_bfd, g_switch_value);