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

[Joel Brobecker <brobecker at adacore dot com>]

Re: http://www.sourceware.org/ml/gdb/2009-09/msg00009.html

This patch implements a suggestion from Daniel to cache the last
frame whose ID was accessed. This is useful in the case where we
do get_prev_register that returns a value that points to the next
frame.  This reduces the time from 30+ seconds to under 0.5 sec
when dealing with 10,000 iterations in the example provided by the PR.

We only cache one frame at a time, since this is sufficient to fix
the quadratic behavior (I don't like introducing optimizations unless
I can measure the improvement).

My only complaint with this patch is that it introduces a slight
confusion: The current code says we "cache" all the frames when it
talks about the frame chain corresponding to the backtrace. My patch
introduces a "frame cache".  I'm OK with renaming my cache into
something else, but couldn't find a better name.

I'll also attach a couple of files that move the new frame cache
to a different file (frame-cache.c). I think it's cleaner, but the issue
is that we cannot access the frame ID from the frame since struct frame
is opaque.  As a result, one has to pass the frame ID in addition to
the frame itself when adding it to the frame cache. The code is actually
smaller if kept in frame.c, so in the end I chose the simpler approach,
but I don't mind using frame-cache.c instead if others think it's better.

Any suggestion of a new name for my frame_cache? Any objection to me
checking in this patch? I'm planning on checking in this patch by the
end of the week if no one objects.

2009-09-03  Joel Brobecker  <brobecker@adacore.com>

        Avoid quadratic behavior when computing the value of a register.
        * frame.c (frame_cache): New static constant.
        (frame_cache_add, frame_cache_find, frame_cache_invalidate):
        New functions.
        (get_frame_id): Minor reformatting. Add the frame to the frame cache.
        (frame_find_by_id): Search the frame cache first before walking all
        frames starting from te current_frame.
        (reinit_frame_cache): Add call to frame_cache_invalidate ();

Tested on x86_64-linux.

-- 
Joel

commit d918a8fb8cbca3b3ac6c73fc62b38d21f5b70386
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_cache): New static constant.
        (frame_cache_add, frame_cache_find, frame_cache_invalidate):
        New functions.
        (get_frame_id): Minor reformatting. Add the frame to the frame cache.
        (frame_find_by_id): Search the frame cache first before walking all
        frames starting from te current_frame.
        (reinit_frame_cache): Add call to frame_cache_invalidate ();

diff --git a/gdb/frame.c b/gdb/frame.c
index 67e0607..c12be5e 100644
--- a/gdb/frame.c
+++ b/gdb/frame.c
@@ -122,6 +122,37 @@ struct frame_info
   enum unwind_stop_reason stop_reason;
 };
 
+/* A Frame cache used to speed up frame lookups.  */
+
+/* We currently only cache one frame, as this seems to be sufficient
+   for now.  */
+static struct frame_info *frame_cache = NULL;
+
+/* Add the following FRAME to the frame cache.  */
+static void
+frame_cache_add (struct frame_info *frame)
+{
+  frame_cache = frame;
+}
+
+/* Search the frame cache for an entry with the given frame ID.
+   If found, return that frame.  Otherwise return NULL.  */
+static struct frame_info *
+frame_cache_find (struct frame_id id)
+{
+  if (frame_cache && frame_id_eq (frame_cache->this_id.value, id))
+    return frame_cache;
+
+  return NULL;
+}
+
+/* Invalidate the frame cache by removing all entries in the cache.  */
+static void
+frame_cache_invalidate (void)
+{
+  frame_cache = NULL;
+}
+
 /* Flag to control debugging.  */
 
 int frame_debug;
@@ -279,9 +310,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 +330,9 @@ get_frame_id (struct frame_info *fi)
 	  fprintf_unfiltered (gdb_stdlog, " }\n");
 	}
     }
+
+  frame_cache_add (fi);
+
   return fi->this_id.value;
 }
 
@@ -514,6 +547,11 @@ frame_find_by_id (struct frame_id id)
   if (!frame_id_p (id))
     return NULL;
 
+  /* Try using the frame cache first.  */
+  frame = frame_cache_find (id);
+  if (frame && frame_id_eq (frame->this_id.value, id))
+    return frame;
+
   for (frame = get_current_frame (); ; frame = prev_frame)
     {
       struct frame_id this = get_frame_id (frame);
@@ -1285,6 +1323,7 @@ reinit_frame_cache (void)
 
   current_frame = NULL;		/* Invalidate cache */
   select_frame (NULL);
+  frame_cache_invalidate ();
   if (frame_debug)
     fprintf_unfiltered (gdb_stdlog, "{ reinit_frame_cache () }\n");
 }

#include "defs.h"
#include "frame.h"

/* Add the following FRAME to the frame cache.  */
void frame_cache_add (struct frame_info *frame, struct frame_id id);

/* Search the frame cache for an entry with the given frame ID.
   If found, return that frame.  Otherwise return NULL.  */
struct frame_info *frame_cache_find (struct frame_id id);

/* Invalidate the frame cache by removing all entries in the cache.  */
void frame_cache_invalidate (void);

#include "defs.h"
#include "frame-cache.h"

struct frame_cache_entry
{
  struct frame_id id;
  struct frame_info *frame;
};

/* The current implementation currently only caches one frame.  */
struct frame_cache_entry frame_cache;

void
frame_cache_add (struct frame_info *frame, struct frame_id id)
{
  frame_cache.id = id;
  frame_cache.frame = frame;
}

struct frame_info *
frame_cache_find (struct frame_id id)
{
  if (frame_id_eq (frame_cache.id, id))
    return frame_cache.frame;
  return NULL;
}

void frame_cache_invalidate (void)
{
  frame_cache.id = null_frame_id;
  frame_cache.frame = NULL;
}

/* Provide a prototype to silence -Wmissing-prototypes.  */
extern initialize_file_ftype _initialize_frame_cache;

void
_initialize_frame_cache (void)
{
  frame_cache.id = null_frame_id;
  frame_cache.frame = NULL;
}