Re: [RFA/PATCH] PR/9711: quadratic slowdown for deep stack traces

Joel Brobecker
2009-09-07T20:33:34Z

[-- Attachment #1: Type: text/plain, Size: 292 bytes --]

> 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

[-- Attachment #2: frame-stash.diff --]
[-- Type: text/x-diff, Size: 2649 bytes --]

commit a3c2d4a05dbfd2762b092a2d9e4cdede3acd92d6
Author: Joel Brobecker <brobecker@adacore.com>
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");
}