This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
[patch] ld speedup 3/3 (weak symbol handling)
- From: Michael Matz <matz at suse dot de>
- To: binutils at sources dot redhat dot com
- Cc: Lars Knoll <lars at trolltech dot com>
- Date: Wed, 10 Sep 2003 21:01:01 +0200 (CEST)
- Subject: [patch] ld speedup 3/3 (weak symbol handling)
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