Re: Re: [PATCH] git tag --contains : avoid stack overflow

[Johannes Schindelin <Johannes.Schindelin@gmx.de>]

Hi,

On Sun, 11 Nov 2012, Jeff King wrote:

> On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote:
> 
> > >However, I couldn't reproduce it on Linux : where the windows
> > >implementations crashes at a ~32000 depth (*not* exactly 32768, mind
> > >you), on linux it happily went through 100000 commits. I didn't take
> > >time to look much further, but maybe on my 64 bit Linux VM, the
> > >process can afford to reserve a much bigger address range for the
> > >stack of each thread than the 1Mb given to 32 bit processes on
> > >windows.  Jean-Jacques.
> > 
> > I can reproduce it on Linux (Debian testing amd64) with ulimit -s 1000
> > to reduce the stack size from its default value of 8MB.
> > 
> > After reverting ffc4b8012d9a4f92ef238ff72c0d15e9e1b402ed (tag: speed
> > up --contains calculation) the test passes even with the smaller
> > stack, but it makes "git tag --contains" take thrice the time as
> > before.
> 
> Right, I am not too surprised.  That function replaced the original
> algorithm with a much faster depth-first recursive one. I haven't looked
> closely yet at Jean-Jacques' iterative adaptation, but that direction
> seems like a good fix for now.
> 
> Ultimately, I have some ideas for doing this in a breadth-first way,
> which would make it more naturally iterative. It would involve having N
> bits of storage per commit to check N tags, but it would mean that we
> could get accurate answers in the face of clock skew (like the
> merge-base calculation, it would merely get slower in the face of skew).
> 
> But since I haven't worked on that at all, fixing the depth-first
> algorithm to be iterative makes sense to me.

Have you tried the latest tag-contains branch of
git://github.com/msysgit/git/? It contains a couple of brush-ups and a
re-write of the recursion (which I hope is right, I had only time to work
on it during an unwanted layover at O'Hare). The SHA-1 is
fc4f42787a0dd0022d202627681362081a66ef70.

Ciao,
Johannes

-- 
*** Please reply-to-all at all times ***
*** (do not pretend to know who is subscribed and who is not) ***
*** Please avoid top-posting. ***
The msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.

You received this message because you are subscribed to the Google
Groups "msysGit" group.
To post to this group, send email to msysgit@googlegroups.com
To unsubscribe from this group, send email to
msysgit+unsubscribe@googlegroups.com
For more options, and view previous threads, visit this group at
http://groups.google.com/group/msysgit?hl=en_US?hl=en