Significant ld speed up on i386-pc-mingw32

[Sonal Santan <sonal dot santan at xilinx dot com>]

Hello,

I have made some changes in ldlang.c which speeds up ld on MinGW 
platform by about 5 times! The speed-up is most apparent when linking an 
executable with more than 2000 object files.

Without the change, ld spends close to 50% of its time in 
compare_section(). This is due to the Insertion Sort algorithm used in 
walk_wild_section_specs1_wild1() together with output_section_callback() 
and wild_sort() to sort PE sections by name. I changed this algorithm to 
use Binary Search Tree which makes sorting PE sections by name 
significantly faster.

I have tested the change with the binutils snapshot dated 
binutils-060502 for target i386-pc-mingw32. The testsuite gives same 
results with and without the ldlang.c change. Please review the changes 
below and advise how these can be pushed to binutils CVS.

diff -t -c -p ldlang.orig.c ldlang.c (ldlang.orig.c is the CVS version 
1.223) --


*** ldlang.orig.c    2006-06-14 14:24:41.000000000 -0700
--- ldlang.c    2006-06-14 15:36:13.000000000 -0700
***************
*** 45,50 ****
--- 45,59 ----
 #define offsetof(TYPE, MEMBER) ((size_t) & (((TYPE*) 0)->MEMBER))
 #endif

+ /* Binary search tree structure to efficiently sort
+    sections by name */
+ typedef struct lang_section_bst
+ {
+   asection * section;
+   struct lang_section_bst * left;
+   struct lang_section_bst * right;
+ } lang_section_bst_type;
+
 /* Locals variables.  */
 static struct obstack stat_obstack;
 static struct obstack map_obstack;
*************** static void print_input_section (asectio
*** 84,89 ****
--- 93,106 ----
 static bfd_boolean lang_one_common (struct bfd_link_hash_entry *, void *);
 static void lang_record_phdrs (void);
 static void lang_do_version_exports_section (void);
+ static void
+ output_section_callback (lang_wild_statement_type *ptr,
+                          struct wildcard_list *sec,
+                          asection *section,
+                          lang_input_statement_type *file,
+                          void *output);
+ static int
+ compare_section (sort_type sort, asection *asec, asection *bsec);

 /* Exported variables.  */
 lang_output_section_statement_type *abs_output_section;
*************** match_simple_wild (const char *pattern,
*** 316,321 ****
--- 333,412 ----
   return TRUE;
 }

+ /*
+  * Build a Binary Search Tree to sort sections, unlike insertion sort
+  * used in wild_sort(). BST is considerably faster if the number of
+  * of sections are large.
+  */
+
+ static lang_section_bst_type **
+ wild_sort_fast(lang_wild_statement_type *wild,
+                struct wildcard_list *sec,
+                lang_input_statement_type *file ATTRIBUTE_UNUSED,
+                asection *section)
+ {
+   lang_section_bst_type ** tree =
+     (lang_section_bst_type **)(&(wild->handler_data[1]));
+   if (!wild->filenames_sorted
+     && (sec == NULL || sec->spec.sorted == none)) {
+     /* Append at the right end of tree */
+      while (*tree) {
+        tree = &((*tree)->right);
+      }
+      return tree;
+   }
+   while (*tree) {
+     /* Find the correct node to append this section */
+     if (compare_section (sec->spec.sorted, section, (*tree)->section) 
< 0)
+       tree = &((*tree)->left);
+     else
+       tree = &((*tree)->right);
+   }
+   return tree;
+ }
+
+ /*
+  * Use wild_sort_fast to build a BST to sort sections.
+  */
+
+ static void
+ output_section_callback_fast (lang_wild_statement_type *ptr,
+                               struct wildcard_list *sec,
+                               asection *section,
+                               lang_input_statement_type *file,
+                               void *output ATTRIBUTE_UNUSED)
+ {
+   if (unique_section_p (section))
+     return;
+
+   lang_section_bst_type * node = xmalloc(sizeof(lang_section_bst_type));
+   node->left = 0;
+   node->right = 0;
+   node->section = section;
+   lang_section_bst_type ** tree = wild_sort_fast(ptr, sec, file, section);
+   *tree = node;
+ }
+
+ /*
+  * Convert a sorted sections' BST back to list form
+  */
+
+ static void
+ output_section_callback_tree_to_list (lang_wild_statement_type *ptr,
+                                       lang_section_bst_type * tree,
+                                       void *output)
+ {
+   if (tree->left) {
+     output_section_callback_tree_to_list(ptr, tree->left, output);
+   }
+   lang_add_section (&ptr->children, tree->section,
+                     (lang_output_section_statement_type *) output);
+   if (tree->right) {
+     output_section_callback_tree_to_list(ptr, tree->right, output);
+   }
+   free(tree);
+ }
+
 /* Specialized, optimized routines for handling different kinds of
    wildcards */

*************** walk_wild_section_specs1_wild1 (lang_wil
*** 348,354 ****
--- 439,468 ----
 {
   asection *s;
   struct wildcard_list *wildsec0 = ptr->handler_data[0];
+ 
+   if (wildsec0->spec.sorted == by_name)
+     {
+       /* Special handling for efficient sorting by name */
+       for (s = file->the_bfd->sections; s != NULL; s = s->next)
+         {
+           const char *sname = bfd_get_section_name (file->the_bfd, s);
+           bfd_boolean skip = !match_simple_wild (wildsec0->spec.name, 
sname);
+          
+           if (!skip)
+             walk_wild_consider_section (ptr, file, s, wildsec0, 
callback, data);
+         }
+       /* Now use the sorted binary tree */
+       if (ptr->handler_data[1])
+         {
+           output_section_callback_tree_to_list(ptr,
+                                                (lang_section_bst_type 
*)ptr->handler_data[1],
+                                                data);
+           ptr->handler_data[1] = NULL;
+         }
+       return;
+     }

+   /* Generic handling for regular cases */
   for (s = file->the_bfd->sections; s != NULL; s = s->next)
     {
       const char *sname = bfd_get_section_name (file->the_bfd, s);
*************** analyze_walk_wild_section_handler (lang_
*** 608,613 ****
--- 722,731 ----
      given order, because we've already determined that no section
      will match more than one spec.  */
   data_counter = 0;
+   ptr->handler_data[0] = NULL;
+   ptr->handler_data[1] = NULL;
+   ptr->handler_data[2] = NULL;
+   ptr->handler_data[3] = NULL;
   for (sec = ptr->section_list; sec != NULL; sec = sec->next)
     if (!wildcardp (sec->spec.name))
       ptr->handler_data[data_counter++] = sec;
*************** wild (lang_wild_statement_type *s,
*** 2450,2456 ****
 {
   struct wildcard_list *sec;

!   walk_wild (s, output_section_callback, output);

   if (default_common_section == NULL)
     for (sec = s->section_list; sec != NULL; sec = sec->next)
--- 2568,2582 ----
 {
   struct wildcard_list *sec;

!   if (s->handler_data[0] && (s->handler_data[0]->spec.sorted == by_name)
!       && !s->filenames_sorted)
!     {
!       walk_wild (s, output_section_callback_fast, output);
!     }
!   else
!     {
!       walk_wild (s, output_section_callback, output);
!     }

   if (default_common_section == NULL)
     for (sec = s->section_list; sec != NULL; sec = sec->next)


Thanks,
Sonal