From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 30183 invoked by alias); 22 Jun 2009 17:39:13 -0000 Received: (qmail 30167 invoked by uid 22791); 22 Jun 2009 17:39:11 -0000 X-SWARE-Spam-Status: No, hits=-2.4 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,SPF_PASS X-Spam-Check-By: sourceware.org Received: from mx2.redhat.com (HELO mx2.redhat.com) (66.187.237.31) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 22 Jun 2009 17:39:01 +0000 Received: from int-mx2.corp.redhat.com (int-mx2.corp.redhat.com [172.16.27.26]) by mx2.redhat.com (8.13.8/8.13.8) with ESMTP id n5MHcxbK000891 for ; Mon, 22 Jun 2009 13:38:59 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx2.corp.redhat.com (8.13.1/8.13.1) with ESMTP id n5MHcwWe026083 for ; Mon, 22 Jun 2009 13:38:59 -0400 Received: from host0.dyn.jankratochvil.net (sebastian-int.corp.redhat.com [172.16.52.221]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id n5MHcvIB021470 for ; Mon, 22 Jun 2009 13:38:58 -0400 Received: from host0.dyn.jankratochvil.net (localhost [127.0.0.1]) by host0.dyn.jankratochvil.net (8.14.3/8.14.3) with ESMTP id n5MHcvUT006746 for ; Mon, 22 Jun 2009 19:38:57 +0200 Received: (from jkratoch@localhost) by host0.dyn.jankratochvil.net (8.14.3/8.14.3/Submit) id n5MHcu2s006745 for gdb-patches@sourceware.org; Mon, 22 Jun 2009 19:38:56 +0200 Date: Mon, 22 Jun 2009 17:39:00 -0000 From: Jan Kratochvil To: gdb-patches@sourceware.org Subject: [patch] Accelerate blocks sorting Message-ID: <20090622173856.GA6649@host0.dyn.jankratochvil.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.19 (2009-01-05) X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2009-06/txt/msg00568.txt.bz2 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 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