This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
Re: [PATCH] Speed up ld by about 5 times on Windows.
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
*** 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)