* PR 161/251 patch causing massive link time regression
@ 2004-10-13 20:40 Jakub Jelinek
2004-10-14 0:21 ` H. J. Lu
0 siblings, 1 reply; 6+ messages in thread
From: Jakub Jelinek @ 2004-10-13 20:40 UTC (permalink / raw)
To: binutils
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 161/251 patch causing massive link time regression
2004-10-13 20:40 PR 161/251 patch causing massive link time regression Jakub Jelinek
@ 2004-10-14 0:21 ` H. J. Lu
2004-10-14 12:58 ` Jakub Jelinek
0 siblings, 1 reply; 6+ messages in thread
From: H. J. Lu @ 2004-10-14 0:21 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: binutils, gcc
On Wed, Oct 13, 2004 at 10:39:09PM +0200, Jakub Jelinek wrote:
> 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.
>
It should help. We can also require the single member comdat group,
which may match a linkonce section, should have the group sigature
the same as the section name of the linkonce section. We don't have
to check symbols between 2 sections.
BTW, the problem my patch tries to fix is
.section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,__i686.get_pc_thunk.bx,comdat
vs.
.section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
linker should treat them the same. If gcc can generate
.section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,.gnu.linkonce.t.__i686.get_pc_thunk.bx,comdat
it will help linker a lot.
H.J.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 161/251 patch causing massive link time regression
2004-10-14 0:21 ` H. J. Lu
@ 2004-10-14 12:58 ` Jakub Jelinek
2004-10-14 18:48 ` H. J. Lu
0 siblings, 1 reply; 6+ messages in thread
From: Jakub Jelinek @ 2004-10-14 12:58 UTC (permalink / raw)
To: H. J. Lu; +Cc: binutils, gcc
On Wed, Oct 13, 2004 at 05:21:07PM -0700, H. J. Lu wrote:
> It should help. We can also require the single member comdat group,
> which may match a linkonce section, should have the group sigature
> the same as the section name of the linkonce section. We don't have
> to check symbols between 2 sections.
>
> BTW, the problem my patch tries to fix is
>
> .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,__i686.get_pc_thunk.bx,comdat
>
> vs.
>
> .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
>
> linker should treat them the same. If gcc can generate
>
> .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,.gnu.linkonce.t.__i686.get_pc_thunk.bx,comdat
>
> it will help linker a lot.
Would the following patch be enough?
E.g. following combinations would work:
.section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,__i686.get_pc_thunk.bx,comdat
.section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
.section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,.gnu.linkonce.t.__i686.get_pc_thunk.bx,comdat
.section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
.section .text,"axG",@progbits,__i686.get_pc_thunk.bx,comdat
.section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
.section .text,"axG",@progbits,.gnu.linkonce.t.__i686.get_pc_thunk.bx,comdat
.section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
though your testcase in PR 161 will not work (the comdat group is there
.__i686.get_pc_thunk.bx, not sure why the dot at the begining).
At least the intent of the patch (unless I goofed up) is doing exactly what
linker did without this patch, but only try to match sections that have the
same base section name (resp. comdat group name), where base section name
is section name with ^\.gnu\.linkonce\.[^.]*\. prefix if present stripped.
2004-10-14 Jakub Jelinek <jakub@redhat.com>
* elflink.c (struct already_linked_section): Removed.
(try_match_symbols_in_sections, already_linked): Removed.
(_bfd_elf_section_already_linked): Skip ^\.gnu\.linkonce\.[^.]*\.
prefix of section names when finding already_linked_table
chain. Compare section names. Instead of calling already_linked,
do it inline and only for sections in the same already_linked_list.
--- bfd/elflink.c.jj 2004-10-13 10:02:09.000000000 +0200
+++ bfd/elflink.c 2004-10-14 14:29:17.000000000 +0200
@@ -9268,88 +9268,11 @@ bfd_elf_discard_info (bfd *output_bfd, s
return ret;
}
-struct already_linked_section
-{
- asection *sec;
- asection *linked;
-};
-
-/* Check if the member of a single member comdat group matches a
- linkonce section and vice versa. */
-static bfd_boolean
-try_match_symbols_in_sections
- (struct bfd_section_already_linked_hash_entry *h, void *info)
-{
- struct bfd_section_already_linked *l;
- struct already_linked_section *s
- = (struct already_linked_section *) info;
-
- if (elf_sec_group (s->sec) == NULL)
- {
- /* It is a linkonce section. Try to match it with the member of a
- single member comdat group. */
- for (l = h->entry; l != NULL; l = l->next)
- if ((l->sec->flags & SEC_GROUP))
- {
- asection *first = elf_next_in_group (l->sec);
-
- if (first != NULL
- && elf_next_in_group (first) == first
- && bfd_elf_match_symbols_in_sections (first, s->sec))
- {
- s->linked = first;
- return FALSE;
- }
- }
- }
- else
- {
- /* 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;
- }
- }
-
- return TRUE;
-}
-
-static bfd_boolean
-already_linked (asection *sec, asection *group)
-{
- struct already_linked_section result;
-
- result.sec = sec;
- result.linked = NULL;
-
- bfd_section_already_linked_table_traverse
- (try_match_symbols_in_sections, &result);
-
- if (result.linked)
- {
- sec->output_section = bfd_abs_section_ptr;
- sec->kept_section = result.linked;
-
- /* Also discard the group section. */
- if (group)
- group->output_section = bfd_abs_section_ptr;
-
- return TRUE;
- }
-
- return FALSE;
-}
-
void
_bfd_elf_section_already_linked (bfd *abfd, struct bfd_section * sec)
{
flagword flags;
- const char *name;
+ const char *name, *p;
struct bfd_section_already_linked *l;
struct bfd_section_already_linked_hash_entry *already_linked_list;
asection *group;
@@ -9399,7 +9322,13 @@ _bfd_elf_section_already_linked (bfd *ab
name = bfd_get_section_name (abfd, sec);
- already_linked_list = bfd_section_already_linked_table_lookup (name);
+ if (strncmp (name, ".gnu.linkonce.", sizeof (".gnu.linkonce.") - 1) == 0
+ && (p = strchr (name + sizeof (".gnu.linkonce.") - 1, '.')) != NULL)
+ p++;
+ else
+ p = name;
+
+ already_linked_list = bfd_section_already_linked_table_lookup (p);
for (l = already_linked_list->entry; l != NULL; l = l->next)
{
@@ -9409,10 +9338,11 @@ _bfd_elf_section_already_linked (bfd *ab
a linkonce section with a linkonce section, and ignore comdat
section. */
if ((flags & SEC_GROUP) == (l->sec->flags & SEC_GROUP)
+ && strcmp (name, l->sec->name) == 0
&& bfd_coff_get_comdat_section (l->sec->owner, l->sec) == NULL)
{
/* The section has already been linked. See if we should
- issue a warning. */
+ issue a warning. */
switch (flags & SEC_LINK_DUPLICATES)
{
default:
@@ -9501,15 +9431,39 @@ _bfd_elf_section_already_linked (bfd *ab
section. We only record the discarded comdat group. Otherwise
the undiscarded group will be discarded incorrectly later since
itself has been recorded. */
- if (! already_linked (elf_next_in_group (sec), group))
+ for (l = already_linked_list->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,
+ elf_next_in_group (sec)))
+ {
+ elf_next_in_group (sec)->output_section = bfd_abs_section_ptr;
+ elf_next_in_group (sec)->kept_section = l->sec;
+ group->output_section = bfd_abs_section_ptr;
+ break;
+ }
+ if (l == NULL)
return;
}
else
/* 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);
-
+ for (l = already_linked_list->entry; l != NULL; l = l->next)
+ if (l->sec->flags & SEC_GROUP)
+ {
+ asection *first = elf_next_in_group (l->sec);
+
+ if (first != NULL
+ && elf_next_in_group (first) == first
+ && bfd_elf_match_symbols_in_sections (first, sec))
+ {
+ sec->output_section = bfd_abs_section_ptr;
+ sec->kept_section = l->sec;
+ break;
+ }
+ }
+
/* This is the first section with this name. Record it. */
bfd_section_already_linked_table_insert (already_linked_list, sec);
}
Jakub
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 161/251 patch causing massive link time regression
2004-10-14 12:58 ` Jakub Jelinek
@ 2004-10-14 18:48 ` H. J. Lu
2004-10-14 20:19 ` Jakub Jelinek
0 siblings, 1 reply; 6+ messages in thread
From: H. J. Lu @ 2004-10-14 18:48 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: binutils, gcc
On Thu, Oct 14, 2004 at 02:56:26PM +0200, Jakub Jelinek wrote:
> On Wed, Oct 13, 2004 at 05:21:07PM -0700, H. J. Lu wrote:
> > It should help. We can also require the single member comdat group,
> > which may match a linkonce section, should have the group sigature
> > the same as the section name of the linkonce section. We don't have
> > to check symbols between 2 sections.
> >
> > BTW, the problem my patch tries to fix is
> >
> > .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,__i686.get_pc_thunk.bx,comdat
> >
> > vs.
> >
> > .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
> >
> > linker should treat them the same. If gcc can generate
> >
> > .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,.gnu.linkonce.t.__i686.get_pc_thunk.bx,comdat
> >
> > it will help linker a lot.
>
> Would the following patch be enough?
>
> E.g. following combinations would work:
> .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,__i686.get_pc_thunk.bx,comdat
> .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
>
> .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"axG",@progbits,.gnu.linkonce.t.__i686.get_pc_thunk.bx,comdat
> .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
>
> .section .text,"axG",@progbits,__i686.get_pc_thunk.bx,comdat
> .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
>
> .section .text,"axG",@progbits,.gnu.linkonce.t.__i686.get_pc_thunk.bx,comdat
> .section .gnu.linkonce.t.__i686.get_pc_thunk.bx,"ax",@progbits
>
> though your testcase in PR 161 will not work (the comdat group is there
> .__i686.get_pc_thunk.bx, not sure why the dot at the begining).
It is OK. We can put restriction on group signature when it should
match a linkonce section.
> At least the intent of the patch (unless I goofed up) is doing exactly what
> linker did without this patch, but only try to match sections that have the
> same base section name (resp. comdat group name), where base section name
> is section name with ^\.gnu\.linkonce\.[^.]*\. prefix if present stripped.
>
It looks good to me. How much speed up did yot get with it?
H.J.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 161/251 patch causing massive link time regression
2004-10-14 18:48 ` H. J. Lu
@ 2004-10-14 20:19 ` Jakub Jelinek
2004-10-15 2:35 ` Alan Modra
0 siblings, 1 reply; 6+ messages in thread
From: Jakub Jelinek @ 2004-10-14 20:19 UTC (permalink / raw)
To: H. J. Lu; +Cc: binutils, gcc
On Thu, Oct 14, 2004 at 11:48:47AM -0700, H. J. Lu wrote:
> It is OK. We can put restriction on group signature when it should
> match a linkonce section.
>
> > At least the intent of the patch (unless I goofed up) is doing exactly what
> > linker did without this patch, but only try to match sections that have the
> > same base section name (resp. comdat group name), where base section name
> > is section name with ^\.gnu\.linkonce\.[^.]*\. prefix if present stripped.
> >
>
> It looks good to me. How much speed up did yot get with it?
On the specific test (linking libgklayout.so) it is back on the old
speed, i.e. on my x86-64 back to ~ 13s down from ~ 44s.
Jakub
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 161/251 patch causing massive link time regression
2004-10-14 20:19 ` Jakub Jelinek
@ 2004-10-15 2:35 ` Alan Modra
0 siblings, 0 replies; 6+ messages in thread
From: Alan Modra @ 2004-10-15 2:35 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: binutils
On Thu, Oct 14, 2004 at 04:19:19PM -0400, Jakub Jelinek wrote:
> On Thu, Oct 14, 2004 at 11:48:47AM -0700, H. J. Lu wrote:
> > It is OK. We can put restriction on group signature when it should
> > match a linkonce section.
> >
> > > At least the intent of the patch (unless I goofed up) is doing exactly what
> > > linker did without this patch, but only try to match sections that have the
> > > same base section name (resp. comdat group name), where base section name
> > > is section name with ^\.gnu\.linkonce\.[^.]*\. prefix if present stripped.
> > >
> >
> > It looks good to me. How much speed up did yot get with it?
>
> On the specific test (linking libgklayout.so) it is back on the old
> speed, i.e. on my x86-64 back to ~ 13s down from ~ 44s.
Looks OK to me too. Please commit.
--
Alan Modra
IBM OzLabs - Linux Technology Centre
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2004-10-15 2:35 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-10-13 20:40 PR 161/251 patch causing massive link time regression Jakub Jelinek
2004-10-14 0:21 ` H. J. Lu
2004-10-14 12:58 ` Jakub Jelinek
2004-10-14 18:48 ` H. J. Lu
2004-10-14 20:19 ` Jakub Jelinek
2004-10-15 2:35 ` Alan Modra
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).