This is the mail archive of the binutils@sourceware.org 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] Speed up bfd_elf_match_symbols_in_sections


On Fri, Jan 19, 2007 at 09:58:24AM -0800, H. J. Lu wrote:
> > BTW, unless you plan to reuse elf_tdata (bfd)->symbuf in some other
> > place, bfd_elf_match_symbols_in_sections only ever looks at
> > st_info, st_other, st_shndx st_name of the internal symbols.
> > So to save memory, you can very well also just save that data and
> > nothing else (nor the undef symbols and save more than 50% of memory on
> > this).
> 
> I can't reproduce
> 
> https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=223181
> 
> with the current binutils in CVS. I believe the Linux binutils
> 2.17.50.0.9 is also OK.  We can certainly improve it further.  But
> I don't believe it is a major problem.

Here is what I had in mind.

On the mozilla libgtklayout.so testcase (elf_i386) I measured following
speedups:

64-bit ld, -melf_i386, vanilla

minimum: 6.197972000 sec real / 0.000042200 sec CPU
maximum: 6.221018000 sec real / 0.000051107 sec CPU
average: 6.209165400 sec real / 0.000047178 sec CPU
stdev  : 0.007460193 sec real / 0.000002511 sec CPU

64-bit ld, -melf_i386, patched

minimum: 5.813455000 sec real / 0.000040907 sec CPU
maximum: 5.832608000 sec real / 0.000050820 sec CPU
average: 5.824494400 sec real / 0.000044679 sec CPU
stdev  : 0.007183229 sec real / 0.000003334 sec CPU

64-bit ld, -melf_i386, vanilla --reduce-memory-overhead

minimum: 119.494778000 sec real / 0.000042224 sec CPU
maximum: 119.688682000 sec real / 0.000048612 sec CPU
average: 119.572915333 sec real / 0.000045315 sec CPU
stdev  : 0.102282282 sec real / 0.000003198 sec CPU

64-bit ld, -melf_i386, patched --reduce-memory-overhead

minimum: 12.085348000 sec real / 0.000034931 sec CPU
maximum: 12.707033000 sec real / 0.000044928 sec CPU
average: 12.433576333 sec real / 0.000041296 sec CPU
stdev  : 0.317515608 sec real / 0.000005530 sec CPU

32-bit ld, -melf_i386, vanilla

minimum: 5.614649000 sec real / 0.000040188 sec CPU
maximum: 7.419195000 sec real / 0.000048463 sec CPU
average: 5.805475800 sec real / 0.000044945 sec CPU
stdev  : 0.567107166 sec real / 0.000002036 sec CPU

32-bit ld, -melf_i386, patched

minimum: 5.341537000 sec real / 0.000042763 sec CPU
maximum: 5.396931000 sec real / 0.000051652 sec CPU
average: 5.371220400 sec real / 0.000046096 sec CPU
stdev  : 0.015796821 sec real / 0.000002779 sec CPU

32-bit ld, -melf_i386, vanilla --reduce-memory-overhead

minimum: 68.299867000 sec real / 0.000038836 sec CPU
maximum: 68.471527000 sec real / 0.000045482 sec CPU
average: 68.399761666 sec real / 0.000043199 sec CPU
stdev  : 0.089220140 sec real / 0.000003780 sec CPU

32-bit ld, -melf_i386, patched --reduced-memory-overhead

minimum: 13.593733000 sec real / 0.000035211 sec CPU
maximum: 14.030673000 sec real / 0.000043386 sec CPU
average: 13.789711000 sec real / 0.000040315 sec CPU
stdev  : 0.221916225 sec real / 0.000004450 sec CPU

As shown, with --reduce-memory-overhead the speedup is dramatic
(your change only speeded up the other case), but even without
that there is a noticeable speedup (all measurements were
from 10 runs).  The gains for the non-reduce-memory-overhead
case are in:
1) not running qsort on SHN_UNDEF symbols and running it on
   indirect array, so only pointers are swapped rather than
   20 (32 on 64-bit arches) bytes structures
2) having symbol counts for each section handily available,
   plus using a binary search to find it
3) slightly smaller memory requirements
In the --reduce-memory-overhead case the speedup is mainly
from completely omitting the extremely expensive first qsort
as it is not needed at all.

2007-02-01  Jakub Jelinek  <jakub@redhat.com>

	* elf-bfd.h (struct elf_obj_tdata): Change symbuf type to void *.
	* elf.c (struct elf_symbuf_symbol, struct elf_symbuf_head): New types.
	(struct elf_symbol): Change first member into union.
	(elf_sort_elf_symbol): Compare pointers to internal syms rather than
	internal syms.  Only compare st_shndx fields.
	(elf_create_symbuf): New function.
	(bfd_elf_match_symbols_in_sections): Use it.  If symbufs are available
	for bfds, use a binary search, otherwise don't qsort symbols
	unnecessarily only to select which symbols are for the particular
	shndx.

--- bfd/elf-bfd.h.jj	2007-02-01 18:55:49.000000000 +0100
+++ bfd/elf-bfd.h	2007-02-01 19:03:53.000000000 +0100
@@ -1392,7 +1392,7 @@ struct elf_obj_tdata
   bfd_boolean flags_init;
 
   /* Symbol buffer.  */
-  Elf_Internal_Sym *symbuf;
+  void *symbuf;
 };
 
 #define elf_tdata(bfd)		((bfd) -> tdata.elf_obj_data)
--- bfd/elf.c.jj	2007-02-01 18:55:49.000000000 +0100
+++ bfd/elf.c	2007-02-01 19:44:30.000000000 +0100
@@ -8745,39 +8745,41 @@ _bfd_elf_get_synthetic_symtab (bfd *abfd
   return n;
 }
 
-/* Sort symbol by binding and section. We want to put definitions
-   sorted by section at the beginning.  */
-
-static int
-elf_sort_elf_symbol (const void *arg1, const void *arg2)
+struct elf_symbuf_symbol
 {
-  const Elf_Internal_Sym *s1;
-  const Elf_Internal_Sym *s2;
-  int shndx;
-
-  /* Make sure that undefined symbols are at the end.  */
-  s1 = (const Elf_Internal_Sym *) arg1;
-  if (s1->st_shndx == SHN_UNDEF)
-    return 1;
-  s2 = (const Elf_Internal_Sym *) arg2;
-  if (s2->st_shndx == SHN_UNDEF)
-    return -1;
-
-  /* Sorted by section index.  */
-  shndx = s1->st_shndx - s2->st_shndx;
-  if (shndx != 0)
-    return shndx;
+  unsigned long st_name;	/* Symbol name, index in string tbl */
+  unsigned char st_info;	/* Type and binding attributes */
+  unsigned char st_other;	/* Visibilty, and target specific */
+};
 
-  /* Sorted by binding.  */
-  return ELF_ST_BIND (s1->st_info)  - ELF_ST_BIND (s2->st_info);
-}
+struct elf_symbuf_head
+{
+  struct elf_symbuf_symbol *ssym;
+  bfd_size_type count;
+  unsigned int st_shndx;
+};
 
 struct elf_symbol
 {
-  Elf_Internal_Sym *sym;
+  union
+    {
+      Elf_Internal_Sym *isym;
+      struct elf_symbuf_symbol *ssym;
+    } u;
   const char *name;
 };
 
+/* Sort references to symbols by ascending section number.  */
+
+static int
+elf_sort_elf_symbol (const void *arg1, const void *arg2)
+{
+  const Elf_Internal_Sym *s1 = *(const Elf_Internal_Sym **) arg1;
+  const Elf_Internal_Sym *s2 = *(const Elf_Internal_Sym **) arg2;
+
+  return s1->st_shndx - s2->st_shndx;
+}
+
 static int
 elf_sym_name_compare (const void *arg1, const void *arg2)
 {
@@ -8786,6 +8788,64 @@ elf_sym_name_compare (const void *arg1, 
   return strcmp (s1->name, s2->name);
 }
 
+static struct elf_symbuf_head *
+elf_create_symbuf (bfd_size_type symcount, Elf_Internal_Sym *isymbuf)
+{
+  Elf_Internal_Sym **ind, **indbufend, **indbuf
+    = bfd_malloc2 (symcount, sizeof (*indbuf));
+  struct elf_symbuf_symbol *ssym;
+  struct elf_symbuf_head *ssymbuf, *ssymhead;
+  bfd_size_type i, shndx_count;
+
+  if (indbuf == NULL)
+    return NULL;
+
+  for (ind = indbuf, i = 0; i < symcount; i++)
+    if (isymbuf[i].st_shndx != SHN_UNDEF)
+      *ind++ = &isymbuf[i];
+  indbufend = ind;
+
+  qsort (indbuf, indbufend - indbuf, sizeof (Elf_Internal_Sym *),
+	 elf_sort_elf_symbol);
+
+  shndx_count = 0;
+  if (indbufend > indbuf)
+    for (ind = indbuf, shndx_count++; ind < indbufend - 1; ind++)
+      if (ind[0]->st_shndx != ind[1]->st_shndx)
+	shndx_count++;
+
+  ssymbuf = bfd_malloc ((shndx_count + 1) * sizeof (*ssymbuf)
+			+ (indbufend - indbuf) * sizeof (*ssymbuf));
+  if (ssymbuf == NULL)
+    {
+      free (indbuf);
+      return NULL;
+    }
+
+  ssym = (struct elf_symbuf_symbol *) (ssymbuf + shndx_count);
+  ssymbuf->ssym = NULL;
+  ssymbuf->count = shndx_count;
+  ssymbuf->st_shndx = 0;
+  for (ssymhead = ssymbuf, ind = indbuf; ind < indbufend; ssym++, ind++)
+    {
+      if (ind == indbuf || ssymhead->st_shndx != (*ind)->st_shndx)
+	{
+	  ssymhead++;
+	  ssymhead->ssym = ssym;
+	  ssymhead->count = 0;
+	  ssymhead->st_shndx = (*ind)->st_shndx;
+	}
+      ssym->st_name = (*ind)->st_name;
+      ssym->st_info = (*ind)->st_info;
+      ssym->st_other = (*ind)->st_other;
+      ssymhead->count++;
+    }
+  BFD_ASSERT ((bfd_size_type) (ssymhead - ssymbuf) == shndx_count);
+
+  free (indbuf);
+  return ssymbuf;
+}
+
 /* Check if 2 sections define the same set of local and global
    symbols.  */
 
@@ -8798,9 +8858,9 @@ bfd_elf_match_symbols_in_sections (asect
   Elf_Internal_Shdr *hdr1, *hdr2;
   bfd_size_type symcount1, symcount2;
   Elf_Internal_Sym *isymbuf1, *isymbuf2;
-  Elf_Internal_Sym *isymstart1 = NULL, *isymstart2 = NULL, *isym;
-  Elf_Internal_Sym *isymend;
-  struct elf_symbol *symp, *symtable1 = NULL, *symtable2 = NULL;
+  struct elf_symbuf_head *ssymbuf1, *ssymbuf2;
+  Elf_Internal_Sym *isym, *isymend;
+  struct elf_symbol *symtable1 = NULL, *symtable2 = NULL;
   bfd_size_type count1, count2, i;
   int shndx1, shndx2;
   bfd_boolean result;
@@ -8848,99 +8908,154 @@ bfd_elf_match_symbols_in_sections (asect
     return FALSE;
 
   result = FALSE;
-  isymbuf1 = elf_tdata (bfd1)->symbuf;
-  isymbuf2 = elf_tdata (bfd2)->symbuf;
+  isymbuf1 = NULL;
+  isymbuf2 = NULL;
+  ssymbuf1 = elf_tdata (bfd1)->symbuf;
+  ssymbuf2 = elf_tdata (bfd2)->symbuf;
 
-  if (isymbuf1 == NULL)
+  if (ssymbuf1 == NULL)
     {
       isymbuf1 = bfd_elf_get_elf_syms (bfd1, hdr1, symcount1, 0,
 				       NULL, NULL, NULL);
       if (isymbuf1 == NULL)
 	goto done;
-      /* Sort symbols by binding and section. Global definitions are at
-	 the beginning.  */
-      qsort (isymbuf1, symcount1, sizeof (Elf_Internal_Sym),
-	     elf_sort_elf_symbol);
+
       if (!info->reduce_memory_overheads)
-	elf_tdata (bfd1)->symbuf = isymbuf1;
+	elf_tdata (bfd1)->symbuf = ssymbuf1
+	  = elf_create_symbuf (symcount1, isymbuf1);
     }
 
-  if (isymbuf2 == NULL)
+  if (ssymbuf1 == NULL || ssymbuf2 == NULL)
     {
       isymbuf2 = bfd_elf_get_elf_syms (bfd2, hdr2, symcount2, 0,
 				       NULL, NULL, NULL);
       if (isymbuf2 == NULL)
 	goto done;
-      /* Sort symbols by binding and section. Global definitions are at
-	 the beginning.  */
-      qsort (isymbuf2, symcount2, sizeof (Elf_Internal_Sym),
-	     elf_sort_elf_symbol);
-      if (!info->reduce_memory_overheads)
-	elf_tdata (bfd2)->symbuf = isymbuf2;
+
+      if (ssymbuf1 != NULL && !info->reduce_memory_overheads)
+	elf_tdata (bfd2)->symbuf = ssymbuf2
+	  = elf_create_symbuf (symcount2, isymbuf2);
     }
 
-  /* Count definitions in the section.  */
-  count1 = 0;
-  for (isym = isymbuf1, isymend = isym + symcount1;
-       isym < isymend; isym++)
+  if (ssymbuf1 != NULL && ssymbuf2 != NULL)
     {
-      if (isym->st_shndx == (unsigned int) shndx1)
+      /* Optimized faster version.  */
+      bfd_size_type lo, hi, mid;
+      struct elf_symbol *symp;
+      struct elf_symbuf_symbol *ssym, *ssymend;
+
+      lo = 0;
+      hi = ssymbuf1->count;
+      ssymbuf1++;
+      count1 = 0;
+      while (lo < hi)
 	{
-	  if (count1 == 0)
-	    isymstart1 = isym;
-	  count1++;
+	  mid = (lo + hi) / 2;
+	  if ((unsigned int) shndx1 < ssymbuf1[mid].st_shndx)
+	    hi = mid;
+	  else if ((unsigned int) shndx1 > ssymbuf1[mid].st_shndx)
+	    lo = mid + 1;
+	  else
+	    {
+	      count1 = ssymbuf1[mid].count;
+	      ssymbuf1 += mid;
+	      break;
+	    }
 	}
 
-      if (count1 && isym->st_shndx != (unsigned int) shndx1)
-	break;
-    }
+      lo = 0;
+      hi = ssymbuf2->count;
+      ssymbuf2++;
+      count2 = 0;
+      while (lo < hi)
+	{
+	  mid = (lo + hi) / 2;
+	  if ((unsigned int) shndx2 < ssymbuf2[mid].st_shndx)
+	    hi = mid;
+	  else if ((unsigned int) shndx2 > ssymbuf2[mid].st_shndx)
+	    lo = mid + 1;
+	  else
+	    {
+	      count2 = ssymbuf2[mid].count;
+	      ssymbuf2 += mid;
+	      break;
+	    }
+	}
 
-  count2 = 0;
-  for (isym = isymbuf2, isymend = isym + symcount2;
-       isym < isymend; isym++)
-    {
-      if (isym->st_shndx == (unsigned int) shndx2)
+      if (count1 == 0 || count2 == 0 || count1 != count2)
+	goto done;
+
+      symtable1 = bfd_malloc (count1 * sizeof (struct elf_symbol));
+      symtable2 = bfd_malloc (count2 * sizeof (struct elf_symbol));
+      if (symtable1 == NULL || symtable2 == NULL)
+	goto done;
+
+      symp = symtable1;
+      for (ssym = ssymbuf1->ssym, ssymend = ssym + count1;
+	   ssym < ssymend; ssym++, symp++)
 	{
-	  if (count2 == 0)
-	    isymstart2 = isym;
-	  count2++;
+	  symp->u.ssym = ssym;
+	  symp->name = bfd_elf_string_from_elf_section (bfd1,
+							hdr1->sh_link,
+							ssym->st_name);
 	}
 
-      if (count2 && isym->st_shndx != (unsigned int) shndx2)
-	break;
+      symp = symtable2;
+      for (ssym = ssymbuf2->ssym, ssymend = ssym + count2;
+	   ssym < ssymend; ssym++, symp++)
+	{
+	  symp->u.ssym = ssym;
+	  symp->name = bfd_elf_string_from_elf_section (bfd2,
+							hdr2->sh_link,
+							ssym->st_name);
+	}
+
+      /* Sort symbol by name.  */
+      qsort (symtable1, count1, sizeof (struct elf_symbol),
+	     elf_sym_name_compare);
+      qsort (symtable2, count1, sizeof (struct elf_symbol),
+	     elf_sym_name_compare);
+
+      for (i = 0; i < count1; i++)
+	/* Two symbols must have the same binding, type and name.  */
+	if (symtable1 [i].u.ssym->st_info != symtable2 [i].u.ssym->st_info
+	    || symtable1 [i].u.ssym->st_other != symtable2 [i].u.ssym->st_other
+	    || strcmp (symtable1 [i].name, symtable2 [i].name) != 0)
+	  goto done;
+
+      result = TRUE;
+      goto done;
     }
 
-  if (count1 == 0 || count2 == 0 || count1 != count2)
+  symtable1 = bfd_malloc (symcount1 * sizeof (struct elf_symbol));
+  symtable2 = bfd_malloc (symcount2 * sizeof (struct elf_symbol));
+  if (symtable1 == NULL || symtable2 == NULL)
     goto done;
 
-  symtable1 = bfd_malloc (count1 * sizeof (struct elf_symbol));
-  symtable2 = bfd_malloc (count1 * sizeof (struct elf_symbol));
+  /* Count definitions in the section.  */
+  count1 = 0;
+  for (isym = isymbuf1, isymend = isym + symcount1; isym < isymend; isym++)
+    if (isym->st_shndx == (unsigned int) shndx1)
+      symtable1[count1++].u.isym = isym;
 
-  if (symtable1 == NULL || symtable2 == NULL)
+  count2 = 0;
+  for (isym = isymbuf2, isymend = isym + symcount2; isym < isymend; isym++)
+    if (isym->st_shndx == (unsigned int) shndx2)
+      symtable2[count2++].u.isym = isym;
+
+  if (count1 == 0 || count2 == 0 || count1 != count2)
     goto done;
 
-  symp = symtable1;
-  for (isym = isymstart1, isymend = isym + count1;
-       isym < isymend; isym++)
-    {
-      symp->sym = isym;
-      symp->name = bfd_elf_string_from_elf_section (bfd1,
-						    hdr1->sh_link,
-						    isym->st_name);
-      symp++;
-    }
- 
-  symp = symtable2;
-  for (isym = isymstart2, isymend = isym + count1;
-       isym < isymend; isym++)
-    {
-      symp->sym = isym;
-      symp->name = bfd_elf_string_from_elf_section (bfd2,
-						    hdr2->sh_link,
-						    isym->st_name);
-      symp++;
-    }
-  
+  for (i = 0; i < count1; i++)
+    symtable1[i].name
+      = bfd_elf_string_from_elf_section (bfd1, hdr1->sh_link,
+					 symtable1[i].u.isym->st_name);
+
+  for (i = 0; i < count2; i++)
+    symtable2[i].name
+      = bfd_elf_string_from_elf_section (bfd2, hdr2->sh_link,
+					 symtable2[i].u.isym->st_name);
+
   /* Sort symbol by name.  */
   qsort (symtable1, count1, sizeof (struct elf_symbol),
 	 elf_sym_name_compare);
@@ -8949,8 +9064,8 @@ bfd_elf_match_symbols_in_sections (asect
 
   for (i = 0; i < count1; i++)
     /* Two symbols must have the same binding, type and name.  */
-    if (symtable1 [i].sym->st_info != symtable2 [i].sym->st_info
-	|| symtable1 [i].sym->st_other != symtable2 [i].sym->st_other
+    if (symtable1 [i].u.isym->st_info != symtable2 [i].u.isym->st_info
+	|| symtable1 [i].u.isym->st_other != symtable2 [i].u.isym->st_other
 	|| strcmp (symtable1 [i].name, symtable2 [i].name) != 0)
       goto done;
 
@@ -8961,13 +9076,10 @@ done:
     free (symtable1);
   if (symtable2)
     free (symtable2);
-  if (info->reduce_memory_overheads)
-    {
-      if (isymbuf1)
-	free (isymbuf1);
-      if (isymbuf2)
-	free (isymbuf2);
-    }
+  if (isymbuf1)
+    free (isymbuf1);
+  if (isymbuf2)
+    free (isymbuf2);
 
   return result;
 }


	Jakub


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