PATCH: Slow linker with shared C++ libraries

[H. J. Lu]

On Thu, Feb 26, 2004 at 11:58:05AM +0100, Lars Knoll wrote:
> On Thursday 26 February 2004 07:19, H. J. Lu wrote:
> > If a shared C++ library has many weak data definitions and many
> > symbols, linking against such libraries can be very slow since
> > elf_link_add_object_symbols has to go through all symbols for
> > each referenced weak data definition to search for its aliases,
> > although in most cases there is no alias. What is the best way
> > to speed it up? Can we introduce a linker command not to check
> > aliase for a DSO?
> 
> Michael Matz and myself made a patch to speed up weak symbol handling in the 
> linker, see:
> 
> http://sources.redhat.com/ml/binutils/2003-09/msg00175.html
> 
> As far as I know the patch is still not in binutils, but it sounds very much 
> like a solution to your problem.

That is the same problem. You may want to add h->type != STT_FUNC
when you create the hash table. In my testcase, there is no visible
speed difference between sorted array and hash table. Either way
should work for me.

I am enclosing the modified hash table patch here. Could someone
please take a look at both?

Thanks.


H.J.
-------------- next part --------------
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.

--- bfd/elflink.h.weak	2004-02-24 09:32:07.000000000 -0800
+++ bfd/elflink.h	2004-02-26 12:55:20.000000000 -0800
@@ -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.  */
 
 #include "safe-ctype.h"
@@ -392,6 +394,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
@@ -1493,36 +1517,54 @@ 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
+	      && h->type != STT_FUNC)
+	    {
+	      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;
 
-	  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)
+	  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 = (struct elf_link_hash_entry *)htab_find (sym_tab, hlook);
+
+	  if (h && h != hlook)
 	    {
 	      hlook->weakdef = h;
 
@@ -1547,9 +1589,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