From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 5715 invoked by alias); 7 Sep 2009 22:00:33 -0000 Received: (qmail 5691 invoked by uid 22791); 7 Sep 2009 22:00:28 -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 22:00:19 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 8D5702BABA3; Mon, 7 Sep 2009 18:00:17 -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 VL3Rw6lF5ySO; Mon, 7 Sep 2009 18:00:17 -0400 (EDT) Received: from joel.gnat.com (localhost.localdomain [127.0.0.1]) by rock.gnat.com (Postfix) with ESMTP id 498042BAB72; Mon, 7 Sep 2009 18:00:17 -0400 (EDT) Received: by joel.gnat.com (Postfix, from userid 1000) id C028DF589B; Mon, 7 Sep 2009 15:00:12 -0700 (PDT) Date: Mon, 07 Sep 2009 22:00:00 -0000 From: Joel Brobecker To: Pedro Alves Cc: gdb-patches@sourceware.org, Doug Evans Subject: Re: [RFA/PATCH] PR/9711: quadratic slowdown for deep stack traces Message-ID: <20090907220012.GK30677@adacore.com> References: <20090903183658.GJ4343@adacore.com> <20090907203321.GI30677@adacore.com> <200909072156.53133.pedro@codesourcery.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="/NkBOFFp2J2Af1nK" Content-Disposition: inline In-Reply-To: <200909072156.53133.pedro@codesourcery.com> 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/msg00171.txt.bz2 --/NkBOFFp2J2Af1nK Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-length: 654 > Hmmm, nowhere in the patch is the actual reason this is > needed explained. Could you have some of that? Good idea, Pedro. How's the attached? + /* Try using the frame stash first. Finding it there removes the need + to perform the search by looping over all frames, which can be very + CPU-intensive if the number of frames is very high (the loop is O(n) + and get_prev_frame performs a series of checks that are relatively + expensive). This optimization is particularly useful when this function + is called from another function which already loops over all frames, + making the overall behavior O(n^2). */ -- Joel --/NkBOFFp2J2Af1nK Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="frame-stash.diff" Content-length: 3102 commit c371d018e314b3ffd4ae03a029db5ffac8e9fa8c 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..1aea11b 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,17 @@ frame_find_by_id (struct frame_id id) if (!frame_id_p (id)) return NULL; + /* Try using the frame stash first. Finding it there removes the need + to perform the search by looping over all frames, which can be very + CPU-intensive if the number of frames is very high (the loop is O(n) + and get_prev_frame performs a series of checks that are relatively + expensive). This optimization is particularly useful when this function + is called from another function which already loops over all frames, + making the overall behavior O(n^2). */ + 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 +1332,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"); } --/NkBOFFp2J2Af1nK--