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

[Joel Brobecker <brobecker@adacore.com>]

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

[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

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

commit 14beb7b013684bffdd7bb6a95761eff7ec6b2955
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..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");
 }