[patch] ld speedup 3/3 (weak symbol handling)
Daniel Jacobowitz
drow@mvista.com
Thu Jan 29 15:45:00 GMT 2004
This patch was never applied, and I don't remember seeing a reason in
another thread to discard it. The loop in question is still present
and still quadratic with a large number of weak symbols.
Would someone mind reviewing this?
On Wed, Sep 10, 2003 at 09:01:01PM +0200, Michael Matz wrote:
> Hi,
>
> the below patch again is a nice speedup. ld tries to note in weak symbols
> which non-weak symbols live at the same address. Currently this is
> implemented by a O(n*n) loop, similar to this:
> for w in weaks
> for s in syms
> if s nonweak, and address(s)==address(w)
> w->backlink = s
>
> Well, clearly it's more clever to create a hashtable for the symbols to
> speed up the address test. This is what this patch does. Lars and me
> initially did our own simple hashtable, but Andreas figured it makes more
> sense to use hashtab.c, so he did. The patch passes the testsuite, and in
> fact produces identical binaries.
>
> Results are as follows (the speedup is noticable only if linking
> _against_ big libraries):
> non-debug build:
>
> ld.cvs
> libqt-mt.so real 0m2.409s user 0m2.190s sys 0m0.220s
> assistant real 0m2.649s user 0m2.600s sys 0m0.050s
> designer real 0m3.425s user 0m3.350s sys 0m0.080s
>
> ld.weak
> libqt-mt.so real 0m2.374s user 0m2.040s sys 0m0.330s
> assistant real 0m0.272s user 0m0.240s sys 0m0.040s
> designer real 0m0.815s user 0m0.710s sys 0m0.100s
>
>
> debug build:
> ld.cvs
> libqt-mt.so real 1m12.083s user 1m2.280s sys 0m1.650s
> assistant real 0m4.854s user 0m4.050s sys 0m0.200s
> designer real 0m26.252s user 0m19.830s sys 0m0.910s
>
> ld.weak
> libqt-mt.so real 1m11.529s user 1m3.450s sys 0m1.760s
> assistant real 0m1.645s user 0m1.070s sys 0m0.160s
> designer real 0m21.367s user 0m16.470s sys 0m0.750s
>
>
> For entertainment here the results of applying all three patches to the
> three testcases:
>
> non-debug build:
> ld.all
> libqt-mt.so real 0m1.450s user 0m1.180s sys 0m0.270s
> assistant real 0m0.262s user 0m0.210s sys 0m0.050s
> designer real 0m0.730s user 0m0.600s sys 0m0.130s
>
> ld.all
> libqt-mt.so real 0m22.837s user 0m15.800s sys 0m1.550s
> assistant real 0m1.148s user 0m0.710s sys 0m0.090s
> designer real 0m11.759s user 0m5.580s sys 0m1.010s
>
> Yeah, that's it for now ;-)
>
>
> Ciao,
> Michael.
>
> 2003-09-10 Lars Knoll <lars@trolltech.com>
> Michael Matz <matz@suse.de>
> Andreas Jaeger <aj@suse.de>
>
> * elflink.h: Include hashtab.h.
> (sym_tab_hash, sym_hash_equal): New.
> (elf_link_add_object_symbols): Avoid quadratic algorithm by using
> a hash of all symbols.
> * Makefile.in (elf32.lo, elf64.lo): Add $(INCDIR)/hashtab.h .
>
> Index: Makefile.in
> ===================================================================
> RCS file: /cvs/src/src/bfd/Makefile.in,v
> retrieving revision 1.138
> diff -u -p -r1.138 Makefile.in
> --- Makefile.in 27 Aug 2003 17:43:38 -0000 1.138
> +++ Makefile.in 10 Sep 2003 18:44:14 -0000
> @@ -1845,7 +1845,7 @@ elf32-xtensa.lo: elf32-xtensa.c $(INCDIR
> elf32.lo: elf32.c elfcode.h $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
> $(INCDIR)/bfdlink.h elf-bfd.h $(INCDIR)/elf/common.h \
> $(INCDIR)/elf/internal.h $(INCDIR)/elf/external.h elfcore.h \
> - elflink.h
> + elflink.h $(INCDIR)/hashtab.h
> elflink.lo: elflink.c $(INCDIR)/filenames.h $(INCDIR)/bfdlink.h \
> elf-bfd.h $(INCDIR)/elf/common.h $(INCDIR)/elf/internal.h \
> $(INCDIR)/elf/external.h
> @@ -2127,7 +2127,7 @@ elf64-sparc.lo: elf64-sparc.c $(INCDIR)/
> elf64.lo: elf64.c elfcode.h $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
> $(INCDIR)/bfdlink.h elf-bfd.h $(INCDIR)/elf/common.h \
> $(INCDIR)/elf/internal.h $(INCDIR)/elf/external.h elfcore.h \
> - elflink.h
> + elflink.h $(INCDIR)/hashtab.h
> mmo.lo: mmo.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
> $(INCDIR)/elf/mmix.h $(INCDIR)/elf/reloc-macros.h $(INCDIR)/opcode/mmix.h
> nlm32-alpha.lo: nlm32-alpha.c $(INCDIR)/filenames.h \
> Index: elflink.h
> ===================================================================
> RCS file: /cvs/src/src/bfd/elflink.h,v
> retrieving revision 1.240
> diff -u -p -r1.240 elflink.h
> --- elflink.h 23 Aug 2003 04:10:34 -0000 1.240
> +++ elflink.h 10 Sep 2003 18:44:15 -0000
> @@ -18,6 +18,8 @@
> along with this program; if not, write to the Free Software
> Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
>
> +#include <hashtab.h>
> +
> /* ELF linker code. */
>
> static bfd_boolean elf_link_add_object_symbols (bfd *, struct bfd_link_info *);
> @@ -390,6 +392,28 @@ elf_link_add_archive_symbols (bfd *abfd,
> return FALSE;
> }
>
> +static hashval_t
> +sym_tab_hash (const void *ptr)
> +{
> + const struct elf_link_hash_entry *h;
> + h = (const struct elf_link_hash_entry *) ptr;
> +
> + return (hashval_t)(h->root.u.def.value >> 3)
> + ^ (h->root.u.def.section->target_index << 10);
> +}
> +
> +
> +static int
> +sym_hash_equal (const void *p1, const void *p2)
> +{
> + const struct elf_link_hash_entry *h1, *h2;
> + h1 = (const struct elf_link_hash_entry *) p1;
> + h2 = (const struct elf_link_hash_entry *) p2;
> +
> + return ((h1->root.u.def.section == h2->root.u.def.section)
> + && (h1->root.u.def.value == h2->root.u.def.value));
> +}
> +
> /* Add symbols from an ELF object file to the linker hash table. */
>
> static bfd_boolean
> @@ -1489,36 +1513,52 @@ elf_link_add_object_symbols (bfd *abfd,
> assembler code, handling it correctly would be very time
> consuming, and other ELF linkers don't handle general aliasing
> either. */
> - while (weaks != NULL)
> + if (weaks != NULL)
> {
> - struct elf_link_hash_entry *hlook;
> - asection *slook;
> - bfd_vma vlook;
> + htab_t sym_tab;
> struct elf_link_hash_entry **hpp;
> struct elf_link_hash_entry **hppend;
>
> - hlook = weaks;
> - weaks = hlook->weakdef;
> - hlook->weakdef = NULL;
> -
> - BFD_ASSERT (hlook->root.type == bfd_link_hash_defined
> - || hlook->root.type == bfd_link_hash_defweak
> - || hlook->root.type == bfd_link_hash_common
> - || hlook->root.type == bfd_link_hash_indirect);
> - slook = hlook->root.u.def.section;
> - vlook = hlook->root.u.def.value;
> + sym_tab = htab_create_alloc ((size_t) extsymcount * 3, sym_tab_hash,
> + sym_hash_equal, NULL, calloc, free);
>
> + if (sym_tab == NULL)
> + goto error_return;
> +
> + /* Fill symbol hashtable. */
> hpp = elf_sym_hashes (abfd);
> hppend = hpp + extsymcount;
> for (; hpp < hppend; hpp++)
> {
> + struct elf_link_hash_entry *h = *hpp;
> + if (h && h->root.type == bfd_link_hash_defined)
> + {
> + void **p = htab_find_slot (sym_tab, h, INSERT);
> + if (p == NULL)
> + goto error_return;
> + if (*p == NULL)
> + /* Add element to hashtable. */
> + *p = h;
> + }
> + }
> +
> + while (weaks != NULL)
> + {
> + struct elf_link_hash_entry *hlook;
> struct elf_link_hash_entry *h;
> +
> + hlook = weaks;
> + weaks = hlook->weakdef;
> + hlook->weakdef = NULL;
> +
> + BFD_ASSERT (hlook->root.type == bfd_link_hash_defined
> + || hlook->root.type == bfd_link_hash_defweak
> + || hlook->root.type == bfd_link_hash_common
> + || hlook->root.type == bfd_link_hash_indirect);
>
> - h = *hpp;
> - if (h != NULL && h != hlook
> - && h->root.type == bfd_link_hash_defined
> - && h->root.u.def.section == slook
> - && h->root.u.def.value == vlook)
> + h = (struct elf_link_hash_entry *)htab_find (sym_tab, hlook);
> +
> + if (h && h != hlook)
> {
> hlook->weakdef = h;
>
> @@ -1543,9 +1583,9 @@ elf_link_add_object_symbols (bfd *abfd,
> if (! _bfd_elf_link_record_dynamic_symbol (info, hlook))
> goto error_return;
> }
> - break;
> }
> }
> + htab_delete (sym_tab);
> }
>
> /* If this object is the same format as the output object, and it is
>
>
--
Daniel Jacobowitz
MontaVista Software Debian GNU/Linux Developer
More information about the Binutils
mailing list