From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23157 invoked by alias); 7 Sep 2009 20:33:34 -0000 Received: (qmail 23144 invoked by uid 22791); 7 Sep 2009 20:33:33 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from rock.gnat.com (HELO rock.gnat.com) (205.232.38.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 07 Sep 2009 20:33:28 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 884D52BABF0; Mon, 7 Sep 2009 16:33:26 -0400 (EDT) Received: from rock.gnat.com ([127.0.0.1]) by localhost (rock.gnat.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id sLYJ2BOgsPCP; Mon, 7 Sep 2009 16:33:26 -0400 (EDT) Received: from joel.gnat.com (localhost.localdomain [127.0.0.1]) by rock.gnat.com (Postfix) with ESMTP id 4BABE2BABEB; Mon, 7 Sep 2009 16:33:26 -0400 (EDT) Received: by joel.gnat.com (Postfix, from userid 1000) id 8C3C4F589B; Mon, 7 Sep 2009 13:33:21 -0700 (PDT) Date: Mon, 07 Sep 2009 20:33:00 -0000 From: Joel Brobecker To: Doug Evans Cc: gdb-patches@sourceware.org Subject: Re: [RFA/PATCH] PR/9711: quadratic slowdown for deep stack traces Message-ID: <20090907203321.GI30677@adacore.com> References: <20090903183658.GJ4343@adacore.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="qMm9M+Fa2AknHoGS" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.18 (2008-05-17) 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-09/txt/msg00166.txt.bz2 --qMm9M+Fa2AknHoGS Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-length: 292 > Nit: It seems like there's a redundant call to frame_id_eq in frame_find_by_id. Ooops, you're right. Thanks for catching this! Here is a new patch. I used "frame_stash" to avoid the confusion with the "cache" terminology used in that unit. Currently testing on x86_64-linux... -- Joel --qMm9M+Fa2AknHoGS Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="frame-stash.diff" Content-length: 2649 commit a3c2d4a05dbfd2762b092a2d9e4cdede3acd92d6 Author: Joel Brobecker Date: Thu Sep 3 11:16:44 2009 -0700 Avoid quadratic behavior when computing the value of a register. * frame.c (frame_stash): New static constant. (frame_stash_add, frame_stash_find, frame_stash_invalidate): New functions. (get_frame_id): Minor reformatting. Add the frame to the frame stash. (frame_find_by_id): Search the frame stash first before walking all frames starting from te current_frame. (reinit_frame_stash): Add call to frame_stash_invalidate (); diff --git a/gdb/frame.c b/gdb/frame.c index 67e0607..974a39d 100644 --- a/gdb/frame.c +++ b/gdb/frame.c @@ -122,6 +122,40 @@ struct frame_info enum unwind_stop_reason stop_reason; }; +/* A frame stash used to speed up frame lookups. */ + +/* We currently only stash one frame at a time, as this seems to be + sufficient for now. */ +static struct frame_info *frame_stash = NULL; + +/* Add the following FRAME to the frame stash. */ + +static void +frame_stash_add (struct frame_info *frame) +{ + frame_stash = frame; +} + +/* Search the frame stash for an entry with the given frame ID. + If found, return that frame. Otherwise return NULL. */ + +static struct frame_info * +frame_stash_find (struct frame_id id) +{ + if (frame_stash && frame_id_eq (frame_stash->this_id.value, id)) + return frame_stash; + + return NULL; +} + +/* Invalidate the frame stash by removing all entries in it. */ + +static void +frame_stash_invalidate (void) +{ + frame_stash = NULL; +} + /* Flag to control debugging. */ int frame_debug; @@ -279,9 +313,8 @@ struct frame_id get_frame_id (struct frame_info *fi) { if (fi == NULL) - { - return null_frame_id; - } + return null_frame_id; + if (!fi->this_id.p) { if (frame_debug) @@ -300,6 +333,9 @@ get_frame_id (struct frame_info *fi) fprintf_unfiltered (gdb_stdlog, " }\n"); } } + + frame_stash_add (fi); + return fi->this_id.value; } @@ -514,6 +550,11 @@ frame_find_by_id (struct frame_id id) if (!frame_id_p (id)) return NULL; + /* Try using the frame cache first. */ + frame = frame_stash_find (id); + if (frame) + return frame; + for (frame = get_current_frame (); ; frame = prev_frame) { struct frame_id this = get_frame_id (frame); @@ -1285,6 +1326,7 @@ reinit_frame_cache (void) current_frame = NULL; /* Invalidate cache */ select_frame (NULL); + frame_stash_invalidate (); if (frame_debug) fprintf_unfiltered (gdb_stdlog, "{ reinit_frame_cache () }\n"); } --qMm9M+Fa2AknHoGS--