Re: [patch] Accelerate blocks sorting

[Michael Snyder <msnyder@vmware.com>]

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