Re: [PATCH] Use binary search instead of linear search in corefile.c of gprof

Re: [PATCH] Use binary search instead of linear search in corefile.c of gprof

[Dongsheng Xing]

Hi, Tristan,

    Thank you. I have updated the patch with bsearch(). 

    Best Regards, 
    Homer

--- On Mon, 6/15/09, Tristan Gingold <gingold@adacore.com> wrote:

> > 
> > Hi!
> > 
> >    This patch replace linear search by
> binary search in core_create_syms_from().
> > 
> Just being curious: if you sort with qsort(), why don't you
> search with bsearch() ?
> 

diff -rup binutils-2.19.51.origin/gprof/cg_print.c binutils-2.19.51/gprof/cg_print.c
--- binutils-2.19.51.origin/gprof/cg_print.c	2009-06-14 21:00:29.000000000 +0800
+++ binutils-2..19.51/gprof/cg_print.c	2009-06-15 22:42:54.000000000 +0800
@@ -1212,6 +1212,16 @@ order_and_dump_functions_by_arcs (the_ar
       }
 }
 
+/* Compare two function_map struct based on file name.
+   We want to sort in ascending order.  */
+
+static int
+cmp_symbol_map (const PTR l, const PTR r)
+{
+  return strcmp (((struct function_map *) l)->file_name, 
+		  ((struct function_map *) r)->file_name);
+}
+
 /* Print a suggested .o ordering for files on a link line based
    on profiling information.  This uses the function placement
    code for the bulk of its work.  */
@@ -1245,6 +1255,7 @@ cg_print_file_ordering ()
     }
 
   /* Now output any .o's that didn't have any text symbols.  */
+  qsort (symbol_map, symbol_map_count, sizeof (struct function_map), cmp_symbol_map);
   last = NULL;
   for (index = 0; index < symbol_map_count; index++)
     {
diff -rup binutils-2.19.51.origin/gprof/corefile.c binutils-2.19.51/gprof/corefile.c
--- binutils-2.19.51.origin/gprof/corefile.c	2009-06-15 19:03:48.000000000 +0800
+++ binutils-2.19.51/gprof/corefile.c	2009-06-15 22:44:38.000000000 +0800
@@ -61,12 +61,23 @@ parse_error (const char *filename)
   done (1);
 }
 
+/* Compare two function_map struct based on function name.
+   We want to sort in ascending order.  */
+
+static int
+cmp_symbol_map (const PTR l, const PTR r)
+{
+  return strcmp (((struct function_map *) l)->function_name, 
+		  ((struct function_map *) r)->function_name);
+}
+
 static void
 read_function_mappings (const char *filename)
 {
   FILE *file = fopen (filename, "r");
   char dummy[1024];
   int count = 0;
+  unsigned int i;
 
   if (!file)
     {
@@ -144,6 +155,14 @@ read_function_mappings (const char *file
 
   /* Record the size of the map table for future reference.  */
   symbol_map_count = count;
+
+  for (i = 0; i < symbol_map_count; ++i)
+    {
+      if (i == 0 || strcmp (symbol_map[i].file_name, symbol_map[i - 1].file_name))
+	symbol_map[i].is_first = 1;
+    }
+
+  qsort (symbol_map, symbol_map_count, sizeof (struct function_map), cmp_symbol_map);
 }
 
 
@@ -532,6 +551,12 @@ core_create_syms_from (const char * sym_
   free (name);
 }
 
+static int
+search_mapped_symbol(const PTR l, const PTR r)
+{
+    return strcmp ((const char *)l, ((const struct function_map *)r)->function_name);
+}
+
 /* Read in symbol table from core.
    One symbol per function is entered.  */
 
@@ -541,8 +566,8 @@ core_create_function_syms ()
   bfd_vma min_vma = ~(bfd_vma) 0;
   bfd_vma max_vma = 0;
   int class;
-  long i, found, skip;
-  unsigned int j;
+  long i;
+  struct function_map *found;
 
   /* Pass 1 - determine upper bound on number of function names.  */
   symtab.len = 0;
@@ -552,23 +577,11 @@ core_create_function_syms ()
       if (!core_sym_class (core_syms[i]))
 	continue;
 
-      /* This should be replaced with a binary search or hashed
-	 search.  Gross.
-
-	 Don't create a symtab entry for a function that has
+      /* Don't create a symtab entry for a function that has
 	 a mapping to a file, unless it's the first function
 	 in the file.  */
-      skip = 0;
-      for (j = 0; j < symbol_map_count; j++)
-	if (!strcmp (core_syms[i]->name, symbol_map[j].function_name))
-	  {
-	    if (j > 0 && ! strcmp (symbol_map [j].file_name,
-				   symbol_map [j - 1].file_name))
-	      skip = 1;
-	    break;
-	  }
-
-      if (!skip)
+      found = bsearch(core_syms[i]->name, symbol_map, symbol_map_count, sizeof (struct function_map), search_mapped_symbol);
+      if (found == NULL || found->is_first)
 	++symtab.len;
     }
 
@@ -598,25 +611,9 @@ core_create_function_syms ()
 	  continue;
 	}
 
-      /* This should be replaced with a binary search or hashed
-	 search.  Gross..   */
-      skip = 0;
-      found = 0;
-
-      for (j = 0; j < symbol_map_count; j++)
-	if (!strcmp (core_syms[i]->name, symbol_map[j].function_name))
-	  {
-	    if (j > 0 && ! strcmp (symbol_map [j].file_name,
-				   symbol_map [j - 1].file_name))
-	      skip = 1;
-	    else
-	      found = j;
-	    break;
-	  }
-
-      if (skip)
+      found = bsearch(core_syms[i]->name, symbol_map, symbol_map_count, sizeof (struct function_map), search_mapped_symbol);
+      if (found && !found->is_first)
 	continue;
-
       sym_init (symtab.limit);
 
       /* Symbol offsets are always section-relative.  */
@@ -625,10 +622,9 @@ core_create_function_syms ()
       if (sym_sec)
 	symtab.limit->addr += bfd_get_section_vma (sym_sec->owner, sym_sec);
 
-      if (symbol_map_count
-	  && !strcmp (core_syms[i]->name, symbol_map[found].function_name))
+      if (found)
 	{
-	  symtab.limit->name = symbol_map[found].file_name;
+	  symtab.limit->name = found->file_name;
 	  symtab.limit->mapped = 1;
 	}
       else
diff -rup binutils-2.19.51.origin/gprof/corefile.h binutils-2.19.51/gprof/corefile.h
--- binutils-2.19.51.origin/gprof/corefile.h	2009-06-14 21:00:29.000000000 +0800
+++ binutils-2.19.51/gprof/corefile.h	2009-06-15 19:11:24.000000000 +0800
@@ -26,6 +26,7 @@ struct function_map
 {
   char *function_name;
   char *file_name;
+  unsigned int is_first:1;	/* Is this the first symbol in an object file?  */
 };
 
 extern struct function_map * symbol_map;

Re: [PATCH] Use binary search instead of linear search in corefile.c of gprof

[Nick Clifton]

Hi Homer,

>     Thank you. I have updated the patch with bsearch(). 

Thanks - I have applied your patch, along with the changelog entry below.

Please note for future submissions: it really helps if you can include a 
ChangeLog entry along with a patch.

Cheers
   Nick

gprof/ChangeLog
2009-06-16  Homer Xing  <homer.xing@yahoo.com>

	* corefile.c (cmp_symbol_map): New function.
	(read_function_mappins): Use qsort to sort the symbols.
	(search_mapped_symbol): New function.
	(core_create_function_syms): Use bsearch to find symbols.
	* corefile.h (struct function_map): Add new bit-field: is_first.
	* cg_print.c (cmp_symbol_map): New function.
	(cg_print_file_ordering): Sort the symbol map.

Re: [PATCH] Use binary search instead of linear search in corefile.c of gprof

[Tristan Gingold]

On Jun 15, 2009, at 3:11 PM, Dongsheng Xing wrote:

>
> Hi!
>
>    This patch replace linear search by binary search in  
> core_create_syms_from().
>
>    This is implemented by qsort(symbol_map) in  
> read_function_mappings() by function name, thus we can do binary  
> search in core_create_function_syms() based on function name.

Just being curious: if you sort with qsort(), why don't you search  
with bsearch() ?

[PATCH] Use binary search instead of linear search in corefile.c of gprof

[Dongsheng Xing]

Hi!

    This patch replace linear search by binary search in core_create_syms_from(). 

    This is implemented by qsort(symbol_map) in read_function_mappings() by function name, thus we can do binary search in core_create_function_syms() based on function name. 
    
    But in the original version, core_create_function_syms() need to know whether a symbol is the first symbol in object file. It did this by check whether symbol_map[j].file_name==symbol_map[j-1].file_name. Since symbol_map is sorted, this method does not work. So a field `is_first:1' is added into struct function_map.

    qsort() is added into cg_print_file_ordering(), since cg_print_file_ordering() requires that symbol_map is sorted by file_name.

    Cheers, 
    Homer

diff -rup binutils-2.19.51.origin/gprof/cg_print.c binutils-2.19.51/gprof/cg_print.c
--- binutils-2.19.51.origin/gprof/cg_print.c	2009-06-14 21:00:29.000000000 +0800
+++ binutils-2.19.51/gprof/cg_print.c	2009-06-15 20:45:35.000000000 +0800
@@ -1212,6 +1212,16 @@ order_and_dump_functions_by_arcs (the_ar
       }
 }
 
+/* Compare two function_map struct based on file name.
+   We want to sort in ascending order.  */
+
+static int
+cmp_symbol_map (const PTR left, const PTR right)
+{
+  return strcmp ( ((const struct function_map *) left )->file_name, 
+		   ((const struct function_map *) right)->file_name);
+}
+
 /* Print a suggested .o ordering for files on a link line based
    on profiling information.  This uses the function placement
    code for the bulk of its work.  */
@@ -1245,6 +1255,7 @@ cg_print_file_ordering ()
     }
 
   /* Now output any .o's that didn't have any text symbols.  */
+  qsort (symbol_map, symbol_map_count, sizeof (struct function_map), cmp_symbol_map);
   last = NULL;
   for (index = 0; index < symbol_map_count; index++)
     {
@@ -1259,7 +1270,6 @@ cg_print_file_ordering ()
 	{
 	  if (! symtab.base[index2].mapped)
 	    continue;
-
 	  if (!strcmp (symtab.base[index2].name, symbol_map[index].file_name))
 	    break;
 	}
diff -rup binutils-2.19.51.origin/gprof/corefile.c binutils-2.19.51/gprof/corefile.c
--- binutils-2.19.51.origin/gprof/corefile.c	2009-06-15 19:03:48.000000000 +0800
+++ binutils-2.19.51/gprof/corefile.c	2009-06-15 20:53:44.000000000 +0800
@@ -61,12 +61,23 @@ parse_error (const char *filename)
   done (1);
 }
 
+/* Compare two function_map struct based on function name.
+   We want to sort in ascending order.  */
+
+static int
+cmp_symbol_map (const PTR left, const PTR right)
+{
+  return strcmp ( ((const struct function_map *) left )->function_name, 
+		   ((const struct function_map *) right)->function_name);
+}
+
 static void
 read_function_mappings (const char *filename)
 {
   FILE *file = fopen (filename, "r");
   char dummy[1024];
   int count = 0;
+  unsigned int i;
 
   if (!file)
     {
@@ -144,6 +155,14 @@ read_function_mappings (const char *file
 
   /* Record the size of the map table for future reference.  */
   symbol_map_count = count;
+
+  for (i = 0; i < symbol_map_count; ++i)
+    {
+      if (i == 0 || strcmp (symbol_map[i].file_name, symbol_map[i - 1].file_name))
+	symbol_map[i].is_first = 1;
+    }
+
+  qsort (symbol_map, symbol_map_count, sizeof (struct function_map), cmp_symbol_map);
 }
 
 
@@ -532,6 +551,26 @@ core_create_syms_from (const char * sym_
   free (name);
 }
 
+static int
+search_mapped_symbol(const char *name)
+{
+  int low, high, mid, t;
+  low = 0;
+  high = symbol_map_count - 1;
+  while (low <= high)
+    {
+      mid = (low + high) / 2;
+      t = strcmp (name, symbol_map[mid].function_name);
+      if (!t)
+	return mid;
+      else if (t < 0)
+	high = mid - 1;
+      else
+	low = mid + 1;
+    }
+  return -1;
+}
+
 /* Read in symbol table from core.
    One symbol per function is entered.  */
 
@@ -541,8 +580,7 @@ core_create_function_syms ()
   bfd_vma min_vma = ~(bfd_vma) 0;
   bfd_vma max_vma = 0;
   int class;
-  long i, found, skip;
-  unsigned int j;
+  long i, found;
 
   /* Pass 1 - determine upper bound on number of function names.  */
   symtab.len = 0;
@@ -552,23 +590,11 @@ core_create_function_syms ()
       if (!core_sym_class (core_syms[i]))
 	continue;
 
-      /* This should be replaced with a binary search or hashed
-	 search.  Gross.
-
-	 Don't create a symtab entry for a function that has
+      /* Don't create a symtab entry for a function that has
 	 a mapping to a file, unless it's the first function
 	 in the file.  */
-      skip = 0;
-      for (j = 0; j < symbol_map_count; j++)
-	if (!strcmp (core_syms[i]->name, symbol_map[j].function_name))
-	  {
-	    if (j > 0 && ! strcmp (symbol_map [j].file_name,
-				   symbol_map [j - 1].file_name))
-	      skip = 1;
-	    break;
-	  }
-
-      if (!skip)
+      found = search_mapped_symbol (core_syms[i]->name);
+      if (found == -1 || symbol_map[found].is_first)
 	++symtab.len;
     }
 
@@ -598,23 +624,8 @@ core_create_function_syms ()
 	  continue;
 	}
 
-      /* This should be replaced with a binary search or hashed
-	 search.  Gross.   */
-      skip = 0;
-      found = 0;
-
-      for (j = 0; j < symbol_map_count; j++)
-	if (!strcmp (core_syms[i]->name, symbol_map[j].function_name))
-	  {
-	    if (j > 0 && ! strcmp (symbol_map [j].file_name,
-				   symbol_map [j - 1].file_name))
-	      skip = 1;
-	    else
-	      found = j;
-	    break;
-	  }
-
-      if (skip)
+      found = search_mapped_symbol (core_syms[i]->name);
+      if (found != -1 && symbol_map[found].is_first == 0)
 	continue;
 
       sym_init (symtab.limit);
@@ -625,8 +636,7 @@ core_create_function_syms ()
       if (sym_sec)
 	symtab.limit->addr += bfd_get_section_vma (sym_sec->owner, sym_sec);
 
-      if (symbol_map_count
-	  && !strcmp (core_syms[i]->name, symbol_map[found].function_name))
+      if (symbol_map_count && found != -1)
 	{
 	  symtab.limit->name = symbol_map[found].file_name;
 	  symtab.limit->mapped = 1;
diff -rup binutils-2.19.51.origin/gprof/corefile.h binutils-2.19.51/gprof/corefile.h
--- binutils-2.19.51.origin/gprof/corefile.h	2009-06-14 21:00:29.000000000 +0800
+++ binutils-2.19.51/gprof/corefile.h	2009-06-15 19:11:24.000000000 +0800
@@ -26,6 +26,7 @@ struct function_map
 {
   char *function_name;
   char *file_name;
+  unsigned int is_first:1;	/* Is this the first symbol in an object file?  */
 };
 
 extern struct function_map * symbol_map;