Re: More info on PR/9711 (quadratic slowdown for deep stack traces)

[Daniel Jacobowitz <drow@false.org>]

On Tue, Sep 01, 2009 at 01:48:15PM -0700, Joel Brobecker wrote:
> One improvement I'm looking at is the fact that get_prev_frame is
> doing redundant checks when the previous frame has already been
> computed. So I'm currently testing the idea of adding:
> 
>   if (this_frame->prev_p)
>     return this_frame->prev;
> 
> (before doing the various checks and then calling get_prev_frame_1).
> Does anyone see why this would be a problem? It does not change the

This almost, almost works.  I can see two problems:

* Can the results of those checks ever change?  For instance, does
"set backtrace past-main off" flush the stack frame?  If not, it won't
take effect right away after this change.

* There are places that call get_prev_frame_1 directly.  So one frame
past main may be in the chain, but we usually don't want it.

Now, the results of the checks could be cached in the frame object...

> There might be some other micro optimizations that we could do,
> I haven't looked further. But to break the quadratic behavior,
> I suspect we need to avoid the call to frame_find_by_id, which means
> that we would net to have prev_register routine return the frame in
> addition to the value - I think that we would have to be very careful
> with what we do with the frame.

Have frame_find_by_id keep a cache with the same lifetime as
current_frame.  If it saves the last frame it returned, we can try
that frame and the previous frame before going on to searching from
the current frame.

Also, have frame_find_by_id use get_prev_frame_1?  I'm not sure why we
don't.  You'd have to look at the callers, but I can't see the problem.

-- 
Daniel Jacobowitz
CodeSourcery