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.