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

Pedro Alves
2009-09-07T22:21:26Z

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