PR 161/251 patch causing massive link time regression

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

H.J's 2004-07-27 patch causes massive slow-down of the linker, e.g.
when linking libgklayout.so from mozilla.
Oprofile shows more than 77% of time spent in try_match_symbols_in_sections.
No single member section groups were present (this was a GCC 3.4.2-RH
build).
There were 22520 calls to already_linked and 253586460 calls to
try_match_symbols_in_sections.  If there were some single member section
groups and some linkonce section groups, I think the time would be even
worse (essentially (n_linkonce_sec^2) * log(symbols_in_section)).
The patch below is just a quick hack to get it behave better if there
are no single member section groups at all.
ld-new time below is with this patch, ld-new.vanilla without that patch.

$ time /usr/src/binutils/obj/ld/ld-new `cat args`

real    0m13.263s
user    0m12.684s
sys     0m0.580s
$ time /usr/src/binutils/obj/ld/ld-new.vanilla `cat args`

real    0m48.072s
user    0m42.809s
sys     0m0.576s

Now, before fixing this properly I'd like to understand this
hunk in try_match_symbols_in_sections:
      /* It is the member of a single member comdat group. Try to match
         it with a linkonce section.  */
      for (l = h->entry; l != NULL; l = l->next)
        if ((l->sec->flags & SEC_GROUP) == 0
            && bfd_coff_get_comdat_section (l->sec->owner, l->sec) == NULL
            && bfd_elf_match_symbols_in_sections (l->sec, s->sec))
          {
            s->linked = l->sec;
            return FALSE;
          }
My understanding is that for sections in section group,
bfd_elf_match_symbols_in_sections will be called for both
normal linkonce sections and any sections which are part of some
section group.  Is that the desired behaviour or should there be
        if ((l->sec->flags & SEC_GROUP) == 0
	    && elf_sec_group (l->sec) == NULL
            && bfd_coff_get_comdat_section (l->sec->owner, l->sec) == NULL
            && bfd_elf_match_symbols_in_sections (l->sec, s->sec))
?
What I think should be done to cure this performance regression
is as soon as it is known already_linked will be needed, compute hash
of all the relevant information bfd_elf_match_symbols_in_sections
compares (not section name and SHF_GROUP flag though), including
hash of all defined symbol names, when already_linked would be
called for the first time for current already_linked_table
entries and later on for each new section being added there.
Depending on whether it is a single member section group
or normal linkonce section it would be added into one of two
hash tables and already_linked would just look it up in the opposite
hash table and call bfd_elf_match_symbols_in_sections on those
few sections that have the same hash.

--- bfd/elflink.c.jj	2004-10-13 10:02:09.000000000 +0200
+++ bfd/elflink.c	2004-10-13 22:17:59.026349718 +0200
@@ -9274,6 +9274,8 @@ struct already_linked_section
   asection *linked;
 };
 
+static bfd_boolean single_member_group_seen;
+
 /* Check if the member of a single member comdat group matches a
    linkonce section and vice versa.  */
 static bfd_boolean
@@ -9504,12 +9506,22 @@ _bfd_elf_section_already_linked (bfd *ab
       if (! already_linked (elf_next_in_group (sec), group))
 	return;
     }
-  else
+  else if (single_member_group_seen
+           || elf_sec_group (sec) != NULL)
     /* There is no direct match. But for linkonce section, we should
        check if there is a match with comdat group member. We always
        record the linkonce section, discarded or not.  */
     already_linked (sec, group);
-  
+
+  if (sec->flags & SEC_GROUP)
+    {
+      asection *first = elf_next_in_group (sec);
+
+      if (first != NULL
+          && elf_next_in_group (first) == first)
+        single_member_group_seen = TRUE;
+    }
+
   /* This is the first section with this name.  Record it.  */
   bfd_section_already_linked_table_insert (already_linked_list, sec);
 }


	Jakub