This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
PR 161/251 patch causing massive link time regression
- From: Jakub Jelinek <jakub at redhat dot com>
- To: binutils at sources dot redhat dot com
- Date: Wed, 13 Oct 2004 22:39:09 +0200
- Subject: PR 161/251 patch causing massive link time regression
- Reply-to: 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