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

[Joel Brobecker <brobecker@adacore.com>]

> AFAIR, the real problem showed up while debugging GDB itself, when I
> made it go into infinite recursion loop. Making programs spin into the
> ground via infinite recursion is not that uncommon (IMHO) and when
> that happens, you do get 100_000 or more frames, and usually you only
> care about the outermost 10 of so. It is quite annoying if GDB takes
> several minutes to tell you what these 10 interesting frames are.

I should probably say that I am not contesting the fact that the problem
can happen in real life. I did assume that, given the requirements
for it to happen, the problem was not that common, and perhaps I was
mistaken. It's always hard to say how common an issue is.

That being said, here are the current parameters:

  - I will submit a patch tomorrow that implements the first idea
    that I floated. Namely, if the previous frame has already been
    computed, then have get_prev_frame return that.  This cuts down
    most of the time spent during the register value computation
    (roughly 60% with 10_000 frames).

  - I don't see how, right now, we could get rid of the quadratic
    behavior. It's embedded in the current design: We now get register
    values, and values cannot store the frame directly, it has to be
    the frame ID. This means a frame lookup from ID, which is the
    second loop causing the n^2 behavior.

I am hoping that Daniel, who has more experience than I do in the
area of unwinding, might be able to suggest something that would
help us get rid of the double loop. But, assuming that my patch
is approved, do you think that we should delay the release in order
to get this changed into an O(n) behavior?

-- 
Joel