This is the mail archive of the binutils@sources.redhat.com mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]