From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 4924 invoked by alias); 8 Sep 2009 00:06:43 -0000 Received: (qmail 4805 invoked by uid 22791); 8 Sep 2009 00:06:41 -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; Tue, 08 Sep 2009 00:06:34 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 753072BABA6; Mon, 7 Sep 2009 20:06:32 -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 VkUy1hiEGn0F; Mon, 7 Sep 2009 20:06:32 -0400 (EDT) Received: from joel.gnat.com (localhost.localdomain [127.0.0.1]) by rock.gnat.com (Postfix) with ESMTP id 27D352BABA5; Mon, 7 Sep 2009 20:06:32 -0400 (EDT) Received: by joel.gnat.com (Postfix, from userid 1000) id 39797F589B; Mon, 7 Sep 2009 17:06:27 -0700 (PDT) Date: Tue, 08 Sep 2009 00:06: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: <20090908000627.GN30677@adacore.com> References: <20090903183658.GJ4343@adacore.com> <200909072156.53133.pedro@codesourcery.com> <20090907220012.GK30677@adacore.com> <200909072321.12505.pedro@codesourcery.com> <20090907231213.GM30677@adacore.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="3siQDZowHQqNOShm" Content-Disposition: inline In-Reply-To: <20090907231213.GM30677@adacore.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/msg00179.txt.bz2 --3siQDZowHQqNOShm Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-length: 817 [with the patch, this time...] > Fine with me, although I wouldn't mind a reference to which is the > the "another function" talked about here (--- my thinking is that it > should be "easy" to get here when touching the problematic caller in > question. If it is grep-easy, the merrier. If the reference in the > comment ends up out-of-date at some point, then it just means the > that a good time to rethink the stash as been > reached). Just a "(see foo_func)" would be fine. Anyway, thanks! I usually am not a big fan of putting references to other calling functions inside comments, but I don't mind much. New version attached. I am hoping to commit this on Wednesday (still hoping that we have every blocking item dealt with by then, although it looks like it's going to be a bit of a stretch). -- Joel --3siQDZowHQqNOShm Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="frame-stash.diff" Content-length: 3175 commit 14beb7b013684bffdd7bb6a95761eff7ec6b2955 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..53b26a6 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,18 @@ 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 (such as value_fetch_lazy, case + VALUE_LVAL (val) == lval_register) 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 +1333,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"); } --3siQDZowHQqNOShm--