This is the mail archive of the binutils@sourceware.org mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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)

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]