Home Original page

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

Sonal Santan sonal.santan@xilinx.com
Mon Jul 17 16:31:00 GMT 2006 
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)
>
More information about the Binutils mailing list