bdiff stack overflow patch

[Matt Mackall]

On Tue, 2009-12-08 at 23:06 +0100, Benoit Boissinot wrote:
> On Tue, Dec 08, 2009 at 10:42:34PM +0100, Martin Geisler wrote:
> > Benoit Boissinot <bboissin at gmail.com> writes:
> > 
> > > On Tue, Dec 8, 2009 at 8:23 PM, Alistair Bell <alistair at bellsonline.com> wrote:
> > >> Hi all,
> > >>
> > >> As mentioned in http://mercurial.selenic.com/bts/issue1940 I found
> > >> that I was getting a stack overflow in bdiff. You could possibly blame
> > >> GCC 3.4.6 for not recognizing that it should optimize the code as tail
> > >> recursion, but I converted the tail recursion to iteration and the
> > >> problems went away.
> > >
> > > Really gcc 3.4.6? Could you check if using the 4.x series has better results?
> > >
> > > Gcc 3.4 is really old, I'm not sure we should take the patch,
> > > especially given the code isn't tail-recursive, so it will stay
> > > recursive anyway.
> > 
> > You're saying that GCC 4.x would also have to output recursive code. Is
> > that not a good argument for why we *should* take the patch?
> 
> No. It only removes one call, so the patch doesn't change the worst case
> recursion depth.

Actually, it does if the recursion tree is unbalanced. A balanced
recursion is likely to only have a stack depth of 10-20 frames. An
unbalanced one might run out of memory in really pessimal situations.
Which seems to be what's happening here? I suspect this patch might
actually greatly improve our worst-case.

-- 
http://selenic.com : development and support for Mercurial and Linux