Significant ld speed up on i386-pc-mingw32

Significant ld speed up on i386-pc-mingw32

[Sonal Santan]

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

[PATCH] Speed up ld by about 5 times on Windows.

[Sonal Santan]

Hello,

I have a PATCH for speeding up GNU ld for PE-COFF by about 5 times. I 
had posted this patch last week to binutils mailing list, but saw no 
response. Should I be posting this to MinGW mailing list instead?

Here are the details--

The changes are confined to ldlang.c. 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 ld testsuite gives same 
results with and without this 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

Re: [PATCH] Speed up ld by about 5 times on Windows.

[Brian Dessent]

Sonal Santan wrote:

> I have a PATCH for speeding up GNU ld for PE-COFF by about 5 times. I
> had posted this patch last week to binutils mailing list, but saw no
> response. Should I be posting this to MinGW mailing list instead?

No, you posted to the right place.  I can't speak for Mingw but I don't
think they are interested in maintaining local patches, and besides,
mingw is not the only PE/COFF target.

Sometimes it just takes a while for patches to be reviewed.  However,
you can speed this process along by reformatting your changes according
to the GCS: <http://www.gnu.org/prep/standards/standards.html>.  For
example, multi-line comments like this:

+ /*
+  * 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.
+  */

should be written as:

/* 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.  */

Note the two spaces at the end.  Braces should go on a line by
themselves, so things like this:

+   if (tree->left) {
+     output_section_callback_tree_to_list(ptr, tree->left, output);
+   }

should be written as

  if (tree->left)
    {
      output_section_callback_tree_to_list (ptr, tree->left, output);
    }

Although for single line blocks you can skip the braces entirely.  There
should be no space after * in a declaration, but always a space before (
in a function call, and after a cast, so:

char *x = (cast *) foo (bar);

not

char * x = (cast *)foo(bar);

You included your patch inline and some lines were wrapped, which means
it will not apply without a great deal of cleanup work.  Therefore you
should always send your patch as an attachment, not inline.

You also should supply a ChangeLog that follows the GCS.  But do not
include changes to the ChangeLog in the patch (as the ChangeLog file is
very likely to change often), instead just include the ChangeLog entry
as plaintext in your message.

These things may seem like minor nits, but if a strict coding style was
not enforced the code would quickly turn into a jumbled mess, so this is
required before your patch can be considered.  If you resumbit a patch
that follows the GCS with a ChangeLog your chances of a speedy review
are much increased.

Brian

Re: [PATCH] Speed up ld by about 5 times on Windows.

[Sonal Santan]

[-- Attachment #1: Type: text/plain, Size: 3268 bytes --]

Many Thanks to Brian for his suggestions on how to improve my Patch.

I have attached an updated patch for ldlang.c (against revision 1.226). 
I have tried to follow GNU coding standards in my changes. Please review 
my changes.

The ChangeLog contents are below.

2006-06-21  Sonal Santan  <sonal.santan@xilinx.com>

    * ldlang.c (walk_wild_section_specs1_wild1): Use a Binary
    Search Tree to sort sections by name.
    (lang_section_bst_type): New typedef.
    (analyze_walk_wild_section_handler): Initialize handler_data with
    NULL.
    (wild): Choose output_section_callback_fast as callback method
    for sorting by name.
    (wild_sort_fast, output_section_callback_fast,
    output_section_callback_tree_to_list,): New functions.

Sonal

Brian Dessent wrote:
>
> Sonal Santan wrote:
>
> > I have a PATCH for speeding up GNU ld for PE-COFF by about 5 times. I
> > had posted this patch last week to binutils mailing list, but saw no
> > response. Should I be posting this to MinGW mailing list instead?
>
> No, you posted to the right place.  I can't speak for Mingw but I don't
> think they are interested in maintaining local patches, and besides,
> mingw is not the only PE/COFF target.
>
> Sometimes it just takes a while for patches to be reviewed.  However,
> you can speed this process along by reformatting your changes according
> to the GCS: <http://www.gnu.org/prep/standards/standards.html>.  For
> example, multi-line comments like this:
>
> + /*
> +  * 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.
> +  */
>
> should be written as:
>
> /* 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.  */
>
> Note the two spaces at the end.  Braces should go on a line by
> themselves, so things like this:
>
> +   if (tree->left) {
> +     output_section_callback_tree_to_list(ptr, tree->left, output);
> +   }
>
> should be written as
>
>   if (tree->left)
>     {
>       output_section_callback_tree_to_list (ptr, tree->left, output);
>     }
>
> Although for single line blocks you can skip the braces entirely.  There
> should be no space after * in a declaration, but always a space before (
> in a function call, and after a cast, so:
>
> char *x = (cast *) foo (bar);
>
> not
>
> char * x = (cast *)foo(bar);
>
> You included your patch inline and some lines were wrapped, which means
> it will not apply without a great deal of cleanup work.  Therefore you
> should always send your patch as an attachment, not inline.
>
> You also should supply a ChangeLog that follows the GCS.  But do not
> include changes to the ChangeLog in the patch (as the ChangeLog file is
> very likely to change often), instead just include the ChangeLog entry
> as plaintext in your message.
>
> These things may seem like minor nits, but if a strict coding style was
> not enforced the code would quickly turn into a jumbled mess, so this is
> required before your patch can be considered.  If you resumbit a patch
> that follows the GCS with a ChangeLog your chances of a speedy review
> are much increased.
>
> Brian
>


[-- Attachment #2: ldlang.patch --]
[-- Type: text/x-patch, Size: 6174 bytes --]

*** ldlang.1.226.c	2006-06-21 13:28:36.000000000 -0700
--- ldlang.c	2006-06-21 14:00:51.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
*** 83,88 ****
--- 92,105 ----
  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,405 ----
    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 ****
--- 432,461 ----
  {
    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 ****
--- 715,724 ----
       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,
*** 2461,2467 ****
  {
    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)
--- 2572,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)

Re: [PATCH] Speed up ld by about 5 times on Windows.

[Nick Clifton]

Hi Sonal,

> I have attached an updated patch for ldlang.c (against revision 1.226). 
> I have tried to follow GNU coding standards in my changes. Please review 
> my changes.

Thanks for submitting this patch.  I am looking at it now, but I have 
encountered a problem.  It appears that the patch breaks a couple of 
tests in the linker testsuite, at least for ELF based toolchains:

   Running 
/work/sources/binutils/current/ld/testsuite/ld-scripts/sort.exp ...
   FAIL: SORT_BY_NAME(SORT_BY_NAME())
   FAIL: SORT_BY_NAME(SORT_BY_NAME()) --sort-section name

These tests are not run for PE based toolchains, including the mingw32 
toolchain, which may be why you did not encounter it in your own testing.

The tests are expecting the input sections to be sorted into this order:

   texta
   textb
   text1a
   text1b
   text2a
   text2b
   text3a
   text3b

But instead the (patched) linker is sorting them into this order:

   texta
   text1a
   text2a
   text3a
   textb
   text1b
   text2b
   text3b

Perhaps you could look into this ?

Cheers
   Nick

Re: [PATCH] Speed up ld by about 5 times on Windows.

[Sonal Santan]

[-- Attachment #1: Type: text/plain, Size: 1300 bytes --]

Hello Nick,

Thanks for trying my patch. I have fixed the regressions seen for ELF 
based toolchains. An updated patch is attached with this mail.

Thanks,
Sonal

Nick Clifton wrote:
> Hi Sonal,
>
>> I have attached an updated patch for ldlang.c (against revision 
>> 1.226). I have tried to follow GNU coding standards in my changes. 
>> Please review my changes.
>
> Thanks for submitting this patch.  I am looking at it now, but I have 
> encountered a problem.  It appears that the patch breaks a couple of 
> tests in the linker testsuite, at least for ELF based toolchains:
>
>   Running 
> /work/sources/binutils/current/ld/testsuite/ld-scripts/sort.exp ...
>   FAIL: SORT_BY_NAME(SORT_BY_NAME())
>   FAIL: SORT_BY_NAME(SORT_BY_NAME()) --sort-section name
>
> These tests are not run for PE based toolchains, including the mingw32 
> toolchain, which may be why you did not encounter it in your own testing.
>
> The tests are expecting the input sections to be sorted into this order:
>
>   texta
>   textb
>   text1a
>   text1b
>   text2a
>   text2b
>   text3a
>   text3b
>
> But instead the (patched) linker is sorting them into this order:
>
>   texta
>   text1a
>   text2a
>   text3a
>   textb
>   text1b
>   text2b
>   text3b
>
> Perhaps you could look into this ?
>
> Cheers
>   Nick
>


[-- Attachment #2: ldlang.c.diff --]
[-- Type: text/x-patch, Size: 5257 bytes --]

*** ldlang.1.226.c	2006-06-21 13:28:36.000000000 -0700
--- ldlang.c	2006-06-23 15:37:23.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
*** 83,88 ****
--- 92,105 ----
  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,405 ----
    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 */
  
*************** analyze_walk_wild_section_handler (lang_
*** 608,613 ****
--- 692,701 ----
       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,
*** 2461,2467 ****
  {
    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)
--- 2549,2566 ----
  {
    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);
!       if (s->handler_data[1]) 
!         output_section_callback_tree_to_list (s, 
!                                               (lang_section_bst_type *) s->handler_data[1], 
!                                               output);
!       s->handler_data[1] = NULL;
!     }
!   else 
!     walk_wild (s, output_section_callback, output);
  
    if (default_common_section == NULL)
      for (sec = s->section_list; sec != NULL; sec = sec->next)

Re: [PATCH] Speed up ld by about 5 times on Windows.

[Sonal Santan]

Hello Nick,

Wondering if you got a chance to try my updated ld speedup patch I had 
posted last month?

Thanks,
Sonal

Sonal Santan wrote:
> Hello Nick,
>
> Thanks for trying my patch. I have fixed the regressions seen for ELF 
> based toolchains. An updated patch is attached with this mail.
>
> Thanks,
> Sonal
>
> Nick Clifton wrote:
>> Hi Sonal,
>>
>>> I have attached an updated patch for ldlang.c (against revision 
>>> 1.226). I have tried to follow GNU coding standards in my changes. 
>>> Please review my changes.
>>
>> Thanks for submitting this patch.  I am looking at it now, but I have 
>> encountered a problem.  It appears that the patch breaks a couple of 
>> tests in the linker testsuite, at least for ELF based toolchains:
>>
>>   Running 
>> /work/sources/binutils/current/ld/testsuite/ld-scripts/sort.exp ...
>>   FAIL: SORT_BY_NAME(SORT_BY_NAME())
>>   FAIL: SORT_BY_NAME(SORT_BY_NAME()) --sort-section name
>>
>> These tests are not run for PE based toolchains, including the 
>> mingw32 toolchain, which may be why you did not encounter it in your 
>> own testing.
>>
>> The tests are expecting the input sections to be sorted into this order:
>>
>>   texta
>>   textb
>>   text1a
>>   text1b
>>   text2a
>>   text2b
>>   text3a
>>   text3b
>>
>> But instead the (patched) linker is sorting them into this order:
>>
>>   texta
>>   text1a
>>   text2a
>>   text3a
>>   textb
>>   text1b
>>   text2b
>>   text3b
>>
>> Perhaps you could look into this ?
>>
>> Cheers
>>   Nick
>>
>
> ------------------------------------------------------------------------
>
> *** ldlang.1.226.c	2006-06-21 13:28:36.000000000 -0700
> --- ldlang.c	2006-06-23 15:37:23.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
> *** 83,88 ****
> --- 92,105 ----
>   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,405 ----
>     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 */
>   
> *************** analyze_walk_wild_section_handler (lang_
> *** 608,613 ****
> --- 692,701 ----
>        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,
> *** 2461,2467 ****
>   {
>     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)
> --- 2549,2566 ----
>   {
>     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);
> !       if (s->handler_data[1]) 
> !         output_section_callback_tree_to_list (s, 
> !                                               (lang_section_bst_type *) s->handler_data[1], 
> !                                               output);
> !       s->handler_data[1] = NULL;
> !     }
> !   else 
> !     walk_wild (s, output_section_callback, output);
>   
>     if (default_common_section == NULL)
>       for (sec = s->section_list; sec != NULL; sec = sec->next)
>   

Re: [PATCH] Speed up ld by about 5 times on Windows.

[Nick Clifton]

Hi Sonal,

> Thanks for trying my patch. I have fixed the regressions seen for ELF 
> based toolchains. An updated patch is attached with this mail.

Thanks for submitting this revised patch.  I am sorry that it took me so 
long to get around to reviewing it.

The revised form of the patch is fine and I have applied to the sources. 
  I had to make two changes however:

   1. In the output_section_callback_fast() function you were declaring 
the 'node' and 'tree' variables in the body of the code rather than at 
the start of the function.  Although GCC does allow this other compilers 
do not, and we want the binutils sources to conform to the ISO C90 C 
language specification.

   2. You did not supply a ChangeLog entry, so I have created one for you.

Cheers
   Nick

ld/ChangeLog
2006-07-23  Sonal Santan  <sonal.santan@xilinx.com>

	* ldlang.c (lang_section_bst): New structure for sorting sections
	by name.
	(wild_sort_fast): New function: Insert a section into a binary
	search tree.
	(output_section_callback_fast): New function: Store a section in
	BST.
	(output_section_callback_tree_to_list): New function: Convert a
	BST into a list.
	(analyze_walk_wild_section_handler): Initialize handler_data
	elements.
	(wild): If the data is sorted by name use the BST method to sort
	the names.

RE: [PATCH] Speed up ld by about 5 times on Windows.

[Sonal Santan]

Thanks a lot! 

Sonal

-----Original Message-----
From: binutils-owner@sourceware.org
[mailto:binutils-owner@sourceware.org] On Behalf Of Nick Clifton
Sent: Sunday, July 23, 2006 8:32 AM
To: Sonal Santan
Cc: binutils@sourceware.org
Subject: Re: [PATCH] Speed up ld by about 5 times on Windows.

Hi Sonal,

> Thanks for trying my patch. I have fixed the regressions seen for ELF 
> based toolchains. An updated patch is attached with this mail.

Thanks for submitting this revised patch.  I am sorry that it took me so

long to get around to reviewing it.

The revised form of the patch is fine and I have applied to the sources.

  I had to make two changes however:

   1. In the output_section_callback_fast() function you were declaring 
the 'node' and 'tree' variables in the body of the code rather than at 
the start of the function.  Although GCC does allow this other compilers

do not, and we want the binutils sources to conform to the ISO C90 C 
language specification.

   2. You did not supply a ChangeLog entry, so I have created one for
you.

Cheers
   Nick

ld/ChangeLog
2006-07-23  Sonal Santan  <sonal.santan@xilinx.com>

	* ldlang.c (lang_section_bst): New structure for sorting
sections
	by name.
	(wild_sort_fast): New function: Insert a section into a binary
	search tree.
	(output_section_callback_fast): New function: Store a section in
	BST.
	(output_section_callback_tree_to_list): New function: Convert a
	BST into a list.
	(analyze_walk_wild_section_handler): Initialize handler_data
	elements.
	(wild): If the data is sorted by name use the BST method to sort
	the names.