[Bug ld/30358] bfd very slow (> 4 minutes) to link busybox with -Wl,--sort-section,alignment (regression in binutils-2.40) since af31506c31a59a6edbb13498d6075fa704b801cd

[matz at suse dot de]

https://sourceware.org/bugzilla/show_bug.cgi?id=30358

--- Comment #11 from Michael Matz <matz at suse dot de> ---
The old (insertion-sort) code only added something to the output section list
if the considered section wasn't already either discarded or linked (by being
part of a group for instance).  That is done by lang_add_section.
This output section list is the sorted container into which further insertions
are done (and hence its length is the one determining performance).

The binary search tree code always adds all candidates to the tree (which in
our
unlucky case here mostly degrades to a linked list), and only then goes through
that tree to linearize it to a list which doesn't contain the discarded or
already linked input sections (group members).

So, the intermediate tree contains things that aren't ultimately going to be
output, blowing performance down the drain.  Otherwise the old insertion-sort
code and the now always used tree-based code are equivalent here.  But the
example contains _many_ groups, and all of them have a .debug_macro section
(and only that!) and it exists in many input files, so the difference is
a search-chain length of about 1500 in the insertion sort case and about 106000
in the binary tree case, and that factor goes in quadraticly into performance
(as said, the search tree is degraded in the example).

So, the solution is obvious: don't add something to the tree if it won't be
added to the linearized list later.  That requires some refactoring.

A hacky un-refactored patch for the above is below (relative to master).
It restores performance.

diff --git a/ld/ldlang.c b/ld/ldlang.c
index 4bec280b9df..7e0a9db51e3 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -687,6 +687,19 @@ output_section_callback_sort (lang_wild_statement_type
*ptr,
   if (unique_section_p (section, os))
     return;

+  /* Don't add sections to the tree when we already know that
+     lang_add_section won't do anything with it.  */
+  if (section->output_section != NULL)
+    {
+      if (!link_info.non_contiguous_regions)
+       return;
+
+      /* SECTION has already been handled in a special way
+        (eg. LINK_ONCE): skip it.  */
+      if (bfd_is_abs_section (section->output_section))
+       return;
+    }
+
   node = (lang_section_bst_type *) xmalloc (sizeof (lang_section_bst_type));
   node->left = 0;
   node->right = 0;

-- 
You are receiving this mail because:
You are on the CC list for the bug.