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

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

[Joel Brobecker]

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

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

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

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");
 }

[-- Attachment #3: frame-cache.h --]
[-- Type: text/x-chdr, Size: 450 bytes --]

#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);

[-- Attachment #4: frame-cache.c --]
[-- Type: text/x-csrc, Size: 823 bytes --]

#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;
}

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

[Tom Tromey]

>>>>> "Joel" == Joel Brobecker <brobecker@adacore.com> writes:

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

Joel> I'll also attach a couple of files that move the new frame cache
Joel> to a different file (frame-cache.c). I think it's cleaner, but the issue
Joel> is that we cannot access the frame ID from the frame since struct frame
Joel> is opaque.

I actually prefer the version where the code is in frame.c, because I
think of this cache as an implementation detail of the frame code.
But, 6 of one, I'd support either version.

Joel> Any suggestion of a new name for my frame_cache?

The word "memoize" came to mind.

Joel> Any objection to me checking in this patch?

Not from me, it seems like a good idea.

Tom

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

[Doug Evans]

On Thu, Sep 3, 2009 at 11:36 AM, Joel Brobecker<brobecker@adacore.com> wrote:
> 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 ();

Hi.

Nit: It seems like there's a redundant call to frame_id_eq in frame_find_by_id.

+/* 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;
+}

@@ -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);

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

[Joel Brobecker]

[-- 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");
 }

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

[Doug Evans]

On Mon, Sep 7, 2009 at 1:33 PM, Joel Brobecker<brobecker@adacore.com> wrote:
> I used "frame_stash" to avoid the confusion with the "cache" terminology
> used in that unit.

"works for me"

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

[Pedro Alves]

On Monday 07 September 2009 21:33:21, Joel Brobecker wrote:
> > 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...
> 

Hmmm, nowhere in the patch is the actual reason this is
needed explained.  Could you have some of that?

+  /* Try using the frame cache first.  */
+  frame = frame_stash_find (id);
+  if (frame)
+    return frame;

I guess here would be a good place to explain it.  At least update
the comment to refer to stash instead of cache.  :-)

-- 
Pedro Alves

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

[Joel Brobecker]

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

> 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

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

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

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

[Pedro Alves]

On Monday 07 September 2009 23:00:12, Joel Brobecker wrote:
> > 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).  */

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!

-- 
Pedro Alves

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

[Joel Brobecker]

> 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

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

[Joel Brobecker]

[-- 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");
 }

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

[Joel Brobecker]

>         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 ();

FYI: Now checked in.

-- 
Joel