This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
[patch] Accelerate blocks sorting
- From: Jan Kratochvil <jan dot kratochvil at redhat dot com>
- To: gdb-patches at sourceware dot org
- Date: Mon, 22 Jun 2009 19:38:56 +0200
- Subject: [patch] Accelerate blocks sorting
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