git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Jeff King <peff@peff.net>
Date
Nov 11, 2012, 16:54 UTC
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:
Show 15 quoted lines
> >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
Previous: René ScharfeNext: Johannes Schindelin
Message 5 of 15 in “Re: [PATCH] git tag --contains : avoid stack overflow”
  1. Philip OakleyNov 10, 2012
  2. Jean-Jacques LafayNov 10, 2012
  3. Pat ThoytsNov 10, 2012
  4. René ScharfeNov 11, 2012
  5. Jeff KingNov 11, 2012
  6. Johannes SchindelinNov 11, 2012
  7. Jean-Jacques LafayNov 12, 2012
  8. Jeff KingNov 12, 2012
  9. Johannes SchindelinNov 13, 2012
  10. Jeff KingNov 13, 2012
  11. Johannes SchindelinNov 13, 2012
  12. Jeff KingNov 13, 2012
  13. Johannes SchindelinNov 13, 2012
  14. Junio C HamanoNov 13, 2012
  15. Jeff KingNov 13, 2012

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.