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

[Pedro Alves <pedro@codesourcery.com>]

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