From: Jeff King Date: Sun, 11 Nov 2012 16:54:31 GMT Subject: Re: [PATCH] git tag --contains : avoid stack overflow Message-ID: <20121111165431.GA25884@sigill.intra.peff.net> In-Reply-To: <509FD668.20609@lsrfire.ath.cx> 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. -Peff -- *** 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