[patch] Accelerate blocks sorting

[patch] Accelerate blocks sorting

[Jan Kratochvil]

Hi,

GDB has been reported as hanging on crashed webkit.
https://bugzilla.redhat.com/show_bug.cgi?id=507267

Time of (using webkitgtk-debuginfo-1.1.8-1.fc11.x86_64)
	gdb -nx -ex 'info line *0x350080' ~/t/libwebkit-1.0.so.2.6.0.debug </dev/null

the patch reduces from 40.1s to 4.6s.  (0x350080 is in a CU of 0x8d6ed bytes.)

Regression tested on {x86_64,i686}-fedora-linux-gnu.


Thanks,
Jan


2009-06-22  Jan Kratochvil  <jan.kratochvil@redhat.com>

	Accelerate blocks sorting while reading debug info.
	* buildsym.c (block_compar): New function.
	(end_symtab): Replace the bubble sort by a qsort based code.

--- gdb-6.8.50.20090302/gdb/buildsym.c-orig	2009-06-22 15:20:39.000000000 +0200
+++ gdb-6.8.50.20090302/gdb/buildsym.c	2009-06-22 17:50:54.000000000 +0200
@@ -900,6 +900,19 @@ watch_main_source_file_lossage (void)
     }
 }
 
+/* Helper function for qsort.  Parametes are `struct block *' pointers,
+   function sorts them in descending order by their BLOCK_START.  */
+
+static int
+block_compar (const void *ap, const void *bp)
+{
+  const struct block *a = *(const struct block **) ap;
+  const struct block *b = *(const struct block **) bp;
+
+  return (BLOCK_START (b) > BLOCK_START (a))
+	 - (BLOCK_START (b) < BLOCK_START (a));
+}
+
 /* Finish the symbol definitions for one main source file, close off
    all the lexical contexts for that file (creating struct block's for
    them), then make the struct symtab for that file and put it in the
@@ -953,32 +966,28 @@ end_symtab (CORE_ADDR end_addr, struct o
      OBJF_REORDERED is true, then sort the pending blocks.  */
   if ((objfile->flags & OBJF_REORDERED) && pending_blocks)
     {
-      /* FIXME!  Remove this horrid bubble sort and use merge sort!!! */
-      int swapped;
-      do
-	{
-	  struct pending_block *pb, *pbnext;
+      unsigned count = 0;
+      struct pending_block *pb;
+      struct block **barray, **bp;
+      struct cleanup *back_to;
 
-	  pb = pending_blocks;
-	  pbnext = pb->next;
-	  swapped = 0;
+      for (pb = pending_blocks; pb != NULL; pb = pb->next)
+	count++;
 
-	  while (pbnext)
-	    {
-	      /* swap blocks if unordered! */
+      barray = xmalloc (sizeof (*barray) * count);
+      back_to = make_cleanup (xfree, barray);
 
-	      if (BLOCK_START (pb->block) < BLOCK_START (pbnext->block))
-		{
-		  struct block *tmp = pb->block;
-		  pb->block = pbnext->block;
-		  pbnext->block = tmp;
-		  swapped = 1;
-		}
-	      pb = pbnext;
-	      pbnext = pbnext->next;
-	    }
-	}
-      while (swapped);
+      bp = barray;
+      for (pb = pending_blocks; pb != NULL; pb = pb->next)
+	*bp++ = pb->block;
+
+      qsort (barray, count, sizeof (*barray), block_compar);
+
+      bp = barray;
+      for (pb = pending_blocks; pb != NULL; pb = pb->next)
+	pb->block = *bp++;
+
+      do_cleanups (back_to);
     }
 
   /* Cleanup any undefined types that have been left hanging around

Re: [patch] Accelerate blocks sorting

[Michael Snyder]

Jan Kratochvil wrote:
> Hi,
> 
> GDB has been reported as hanging on crashed webkit.
> https://bugzilla.redhat.com/show_bug.cgi?id=507267
> 
> Time of (using webkitgtk-debuginfo-1.1.8-1.fc11.x86_64)
> 	gdb -nx -ex 'info line *0x350080' ~/t/libwebkit-1.0.so.2.6.0.debug </dev/null
> 
> the patch reduces from 40.1s to 4.6s.  (0x350080 is in a CU of 0x8d6ed bytes.)
> 
> Regression tested on {x86_64,i686}-fedora-linux-gnu.

Is it actually hanging?  Or is it just taking a long time?

The patch looks ok at first glance, but I'm a little confused
about the problem being fixed.


> 2009-06-22  Jan Kratochvil  <jan.kratochvil@redhat.com>
> 
> 	Accelerate blocks sorting while reading debug info.
> 	* buildsym.c (block_compar): New function.
> 	(end_symtab): Replace the bubble sort by a qsort based code.
> 
> --- gdb-6.8.50.20090302/gdb/buildsym.c-orig	2009-06-22 15:20:39.000000000 +0200
> +++ gdb-6.8.50.20090302/gdb/buildsym.c	2009-06-22 17:50:54.000000000 +0200
> @@ -900,6 +900,19 @@ watch_main_source_file_lossage (void)
>      }
>  }
>  
> +/* Helper function for qsort.  Parametes are `struct block *' pointers,
> +   function sorts them in descending order by their BLOCK_START.  */
> +
> +static int
> +block_compar (const void *ap, const void *bp)
> +{
> +  const struct block *a = *(const struct block **) ap;
> +  const struct block *b = *(const struct block **) bp;
> +
> +  return (BLOCK_START (b) > BLOCK_START (a))
> +	 - (BLOCK_START (b) < BLOCK_START (a));
> +}
> +
>  /* Finish the symbol definitions for one main source file, close off
>     all the lexical contexts for that file (creating struct block's for
>     them), then make the struct symtab for that file and put it in the
> @@ -953,32 +966,28 @@ end_symtab (CORE_ADDR end_addr, struct o
>       OBJF_REORDERED is true, then sort the pending blocks.  */
>    if ((objfile->flags & OBJF_REORDERED) && pending_blocks)
>      {
> -      /* FIXME!  Remove this horrid bubble sort and use merge sort!!! */
> -      int swapped;
> -      do
> -	{
> -	  struct pending_block *pb, *pbnext;
> +      unsigned count = 0;
> +      struct pending_block *pb;
> +      struct block **barray, **bp;
> +      struct cleanup *back_to;
>  
> -	  pb = pending_blocks;
> -	  pbnext = pb->next;
> -	  swapped = 0;
> +      for (pb = pending_blocks; pb != NULL; pb = pb->next)
> +	count++;
>  
> -	  while (pbnext)
> -	    {
> -	      /* swap blocks if unordered! */
> +      barray = xmalloc (sizeof (*barray) * count);
> +      back_to = make_cleanup (xfree, barray);
>  
> -	      if (BLOCK_START (pb->block) < BLOCK_START (pbnext->block))
> -		{
> -		  struct block *tmp = pb->block;
> -		  pb->block = pbnext->block;
> -		  pbnext->block = tmp;
> -		  swapped = 1;
> -		}
> -	      pb = pbnext;
> -	      pbnext = pbnext->next;
> -	    }
> -	}
> -      while (swapped);
> +      bp = barray;
> +      for (pb = pending_blocks; pb != NULL; pb = pb->next)
> +	*bp++ = pb->block;
> +
> +      qsort (barray, count, sizeof (*barray), block_compar);
> +
> +      bp = barray;
> +      for (pb = pending_blocks; pb != NULL; pb = pb->next)
> +	pb->block = *bp++;
> +
> +      do_cleanups (back_to);
>      }
>  
>    /* Cleanup any undefined types that have been left hanging around

Re: [patch] Accelerate blocks sorting

[Jan Kratochvil]

On Mon, 22 Jun 2009 20:14:34 +0200, Michael Snyder wrote:
> Jan Kratochvil wrote:
>> GDB has been reported as hanging on crashed webkit.
>> https://bugzilla.redhat.com/show_bug.cgi?id=507267
>>
>> Time of (using webkitgtk-debuginfo-1.1.8-1.fc11.x86_64)
>> 	gdb -nx -ex 'info line *0x350080' ~/t/libwebkit-1.0.so.2.6.0.debug </dev/null
>>
>> the patch reduces from 40.1s to 4.6s.  (0x350080 is in a CU of 0x8d6ed bytes.)


> Is it actually hanging?  Or is it just taking a long time?
[...]
> but I'm a little confused about the problem being fixed.

I do not know, provided updated GDB to the bugreporter, he may respond.

This patch may be completely unrelated to the bugreport.  Nonetheless it can
be proven by my testcase it improves the performance in specific cases a lot.

(I believe it should make this libwebkit case acceptably slow - as GDB
currently is already slow while reading debug info in general.)


> The patch looks ok at first glance,

Thanks for the review but not sure if it was a check-in approval.


Thanks,
Jan

Re: [patch] Accelerate blocks sorting

[Tom Tromey]

>>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:

Jan> GDB has been reported as hanging on crashed webkit.
Jan> https://bugzilla.redhat.com/show_bug.cgi?id=507267

This is also http://sourceware.org/bugzilla/show_bug.cgi?id=9988

Jan> +  return (BLOCK_START (b) > BLOCK_START (a))
Jan> +	 - (BLOCK_START (b) < BLOCK_START (a));

This expression needs parens around it, according to GNU rules.

Jan> +      barray = xmalloc (sizeof (*barray) * count);
Jan> +      back_to = make_cleanup (xfree, barray);

I think you don't actually need a cleanup here, as nothing here can
call error.  However, if you want to leave it, that is also ok with
me.

This is ok with a fix to the formatting nit.

Tom

Re: [patch] Accelerate blocks sorting

[Jan Kratochvil]

On Mon, 22 Jun 2009 20:26:26 +0200, Tom Tromey wrote:
> This is also http://sourceware.org/bugzilla/show_bug.cgi?id=9988

Forgot to search for it again, sorry.


> Jan> +  return (BLOCK_START (b) > BLOCK_START (a))
> Jan> +	 - (BLOCK_START (b) < BLOCK_START (a));
> 
> This expression needs parens around it, according to GNU rules.

GNU Coding Standards provides this sample code line:
         return ++x + bar ();

Moreover it has no sample code (and found no rules) with `return' using parens.
GDB uses `return' with parens a lot but I find it a GNU style violation by GDB
fixing it along in the patches.

Sure no problem to change it but is there any backing for such parens?



> I think you don't actually need a cleanup here, as nothing here can
> call error.  However, if you want to leave it, that is also ok with
> me.

I did not notice, still I find the code safer that way.


Thanks,
Jan

Re: [patch] Accelerate blocks sorting

[Tom Tromey]

>>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:

Jan> +  return (BLOCK_START (b) > BLOCK_START (a))
Jan> +	 - (BLOCK_START (b) < BLOCK_START (a));

Tom> This expression needs parens around it, according to GNU rules.

Jan> GNU Coding Standards provides this sample code line:
Jan>          return ++x + bar ();

Jan> Moreover it has no sample code (and found no rules) with `return'
Jan> using parens.  GDB uses `return' with parens a lot but I find it
Jan> a GNU style violation by GDB fixing it along in the patches.

Jan> Sure no problem to change it but is there any backing for such parens?

Yeah.  It isn't the return, but the splitting.
From (info "(standards) Formatting") :

       Insert extra parentheses so that Emacs will indent the code properly.
    For example, the following indentation looks nice if you do it by hand,

         v = rup->ru_utime.tv_sec*1000 + rup->ru_utime.tv_usec/1000
             + rup->ru_stime.tv_sec*1000 + rup->ru_stime.tv_usec/1000;

    but Emacs would alter it.  Adding a set of parentheses produces
    something that looks equally nice, and which Emacs will preserve:

         v = (rup->ru_utime.tv_sec*1000 + rup->ru_utime.tv_usec/1000
              + rup->ru_stime.tv_sec*1000 + rup->ru_stime.tv_usec/1000);

And, yes, the GNU style is partly defined as "make it work nicely in
Emacs".

Tom> I think you don't actually need a cleanup here, as nothing here can
Tom> call error.  However, if you want to leave it, that is also ok with
Tom> me.

Jan> I did not notice, still I find the code safer that way.

Sounds good.

Tom

Re: [patch] Accelerate blocks sorting

[Jan Kratochvil]

On Mon, 22 Jun 2009 21:26:37 +0200, Tom Tromey wrote:
> Yeah.  It isn't the return, but the splitting.

I see it now, thanks for looking it up.

Checked-in.


Thanks,
Jan


http://sourceware.org/ml/gdb-cvs/2009-06/msg00135.html

--- src/gdb/ChangeLog	2009/06/22 18:17:01	1.10619
+++ src/gdb/ChangeLog	2009/06/22 19:50:10	1.10620
@@ -1,4 +1,10 @@
-2009-05-07  Sami Wagiaalla  <swagiaal@redhat.com>
+2009-06-22  Jan Kratochvil  <jan.kratochvil@redhat.com>
+
+	PR gdb/9988:
+	* buildsym.c (block_compar): New function.
+	(end_symtab): Replace the bubble sort by a qsort based code.
+
+2009-06-22  Sami Wagiaalla  <swagiaal@redhat.com>
 
 	* MAINTAINERS (Write After Approval): Add self.
 
--- src/gdb/buildsym.c	2009/06/17 18:41:50	1.71
+++ src/gdb/buildsym.c	2009/06/22 19:50:10	1.72
@@ -899,6 +899,19 @@
     }
 }
 
+/* Helper function for qsort.  Parametes are `struct block *' pointers,
+   function sorts them in descending order by their BLOCK_START.  */
+
+static int
+block_compar (const void *ap, const void *bp)
+{
+  const struct block *a = *(const struct block **) ap;
+  const struct block *b = *(const struct block **) bp;
+
+  return ((BLOCK_START (b) > BLOCK_START (a))
+	  - (BLOCK_START (b) < BLOCK_START (a)));
+}
+
 /* Finish the symbol definitions for one main source file, close off
    all the lexical contexts for that file (creating struct block's for
    them), then make the struct symtab for that file and put it in the
@@ -952,32 +965,28 @@
      OBJF_REORDERED is true, then sort the pending blocks.  */
   if ((objfile->flags & OBJF_REORDERED) && pending_blocks)
     {
-      /* FIXME!  Remove this horrid bubble sort and use merge sort!!! */
-      int swapped;
-      do
-	{
-	  struct pending_block *pb, *pbnext;
+      unsigned count = 0;
+      struct pending_block *pb;
+      struct block **barray, **bp;
+      struct cleanup *back_to;
 
-	  pb = pending_blocks;
-	  pbnext = pb->next;
-	  swapped = 0;
+      for (pb = pending_blocks; pb != NULL; pb = pb->next)
+	count++;
 
-	  while (pbnext)
-	    {
-	      /* swap blocks if unordered! */
+      barray = xmalloc (sizeof (*barray) * count);
+      back_to = make_cleanup (xfree, barray);
 
-	      if (BLOCK_START (pb->block) < BLOCK_START (pbnext->block))
-		{
-		  struct block *tmp = pb->block;
-		  pb->block = pbnext->block;
-		  pbnext->block = tmp;
-		  swapped = 1;
-		}
-	      pb = pbnext;
-	      pbnext = pbnext->next;
-	    }
-	}
-      while (swapped);
+      bp = barray;
+      for (pb = pending_blocks; pb != NULL; pb = pb->next)
+	*bp++ = pb->block;
+
+      qsort (barray, count, sizeof (*barray), block_compar);
+
+      bp = barray;
+      for (pb = pending_blocks; pb != NULL; pb = pb->next)
+	pb->block = *bp++;
+
+      do_cleanups (back_to);
     }
 
   /* Cleanup any undefined types that have been left hanging around