Re: PR 161/251 patch causing massive link time regression

["H. J. Lu" <hjl at lucon dot org>]

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.