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

[Joel Brobecker]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: frame.diff
Type: text/x-diff
Size: 2682 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/gdb-patches/attachments/20090903/69ddea12/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: frame-cache.h
Type: text/x-chdr
Size: 450 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/gdb-patches/attachments/20090903/69ddea12/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: frame-cache.c
Type: text/x-csrc
Size: 823 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/gdb-patches/attachments/20090903/69ddea12/attachment-0002.bin>