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]

Re: Slow linker with shared C++ libraries


On Thu, Feb 26, 2004 at 07:09:00AM +0100, Jakub Jelinek wrote:
> On Wed, Feb 25, 2004 at 11:42:24PM -0800, H. J. Lu wrote:
> > On Wed, Feb 25, 2004 at 10:19:28PM -0800, 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?
> > > 
> > 
> > I am thinking about adding a special note section which contains the
> > symbol alias information so that the linker doesn't have to go through
> > the whole symbol list even though a symbol may have no alias at
> > all.
> 
> Or you perhaps could when reading symbols qsort them by value and build
> the alias info yourself at symbol read time.
> 

This patch seems to solve my problem quite nicely. In one testcase,
link time went from 20 seconds to 3 seconds.


H.J.
-----
2004-02-26  H.J. Lu  <hongjiu.lu@intel.com>

	* elflink.h (sort_symbol): New.
	(elf_link_add_object_symbols): Use a sorted symbol array for
	weakdef.

--- bfd/elflink.h.weak	2004-02-24 09:32:07.000000000 -0800
+++ bfd/elflink.h	2004-02-26 12:26:15.000000000 -0800
@@ -392,6 +392,18 @@ elf_link_add_archive_symbols (bfd *abfd,
   return FALSE;
 }
 
+/* Sort symbol by value.  */
+static int
+sort_symbol (const void *arg1, const void *arg2)
+{
+  const struct elf_link_hash_entry *h1
+    = *(const struct elf_link_hash_entry **) arg1;
+  const struct elf_link_hash_entry *h2
+    = *(const struct elf_link_hash_entry **) arg2;
+
+  return 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,63 +1505,129 @@ 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;
       struct elf_link_hash_entry **hpp;
       struct elf_link_hash_entry **hppend;
+      struct elf_link_hash_entry **sorted_sym_hash;
+      struct elf_link_hash_entry *h;
+      size_t sym_count;
 
-      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;
-
+      amt = extsymcount * sizeof (struct elf_link_hash_entry *);
+      sorted_sym_hash = bfd_malloc (amt);
+      if (sorted_sym_hash == NULL)
+	goto error_return;
+      sym_hash = sorted_sym_hash;
       hpp = elf_sym_hashes (abfd);
       hppend = hpp + extsymcount;
+      sym_count = 0;
       for (; hpp < hppend; hpp++)
 	{
-	  struct elf_link_hash_entry *h;
-
 	  h = *hpp;
-	  if (h != NULL && h != hlook
+	  if (h != NULL
 	      && h->root.type == bfd_link_hash_defined
-	      && h->root.u.def.section == slook
-	      && h->root.u.def.value == vlook)
+	      && h->type != STT_FUNC)
 	    {
-	      hlook->weakdef = h;
+	      *sym_hash = h;
+	      sym_hash++;
+	      sym_count++;
+	    }
+	}
 
-	      /* If the weak definition is in the list of dynamic
-		 symbols, make sure the real definition is put there
-		 as well.  */
-	      if (hlook->dynindx != -1
-		  && h->dynindx == -1)
+      qsort (sorted_sym_hash, sym_count,
+	     sizeof (struct elf_link_hash_entry *),
+	     sort_symbol);
+
+      while (weaks != NULL)
+	{
+	  struct elf_link_hash_entry *hlook;
+	  asection *slook;
+	  bfd_vma vlook;
+	  int diff, k, ilook;
+	  size_t i, j, idx;
+
+	  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;
+
+	  ilook = -1;
+	  i = 0;
+	  j = sym_count;
+	  while (i < j)
+	    {
+	      idx = (i + j) / 2;
+	      h = sorted_sym_hash [idx];
+	      diff = vlook - h->root.u.def.value;
+	      if (diff < 0)
+		j = idx;
+	      else if (diff > 0)
+		i = idx + 1;
+	      else
 		{
-		  if (! _bfd_elf_link_record_dynamic_symbol (info, h))
-		    goto error_return;
+		  ilook = idx;
+		  break;
 		}
+	    }
+
+	  /* We didn't find a value match.  */
+	  if (ilook == -1)
+	    continue;
+
+	  /* We have to start at the first value match since section
+	     may be different.  */
+	  for (k = ilook - 1; k >= 0; k--)
+	    {
+	      h = sorted_sym_hash [k];
+	      if (vlook != h->root.u.def.value)
+		break;
+	    }
 
-	      /* If the real definition is in the list of dynamic
-		 symbols, make sure the weak definition is put there
-		 as well.  If we don't do this, then the dynamic
-		 loader might not merge the entries for the real
-		 definition and the weak definition.  */
-	      if (h->dynindx != -1
-		  && hlook->dynindx == -1)
+	  /* We need to check if section matches or not.  */
+	  for (i = k + 1; i < sym_count; i++)
+	    {
+	      h = sorted_sym_hash [i];
+
+	      /* Stop if value doesn't match.  */
+	      if (h->root.u.def.value != vlook)
+		break;
+	      else if (h != hlook && h->root.u.def.section == slook)
 		{
-		  if (! _bfd_elf_link_record_dynamic_symbol (info, hlook))
-		    goto error_return;
+		  hlook->weakdef = h;
+
+		  /* If the weak definition is in the list of dynamic
+		     symbols, make sure the real definition is put
+		     there as well.  */
+		  if (hlook->dynindx != -1 && h->dynindx == -1)
+		    {
+		      if (! _bfd_elf_link_record_dynamic_symbol (info,
+								 h))
+			goto error_return;
+		    }
+
+		  /* If the real definition is in the list of dynamic
+		     symbols, make sure the weak definition is put
+		     there as well.  If we don't do this, then the
+		     dynamic loader might not merge the entries for the
+		     real definition and the weak definition.  */
+		  if (h->dynindx != -1 && hlook->dynindx == -1)
+		    {
+		      if (! _bfd_elf_link_record_dynamic_symbol (info,
+								 hlook))
+			goto error_return;
+		    }
+		  break;
 		}
-	      break;
 	    }
 	}
+
+      free (sorted_sym_hash);
     }
 
   /* 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]