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

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

From
JLJean-Jacques Lafay <jeanjacques.lafay@gmail.com>
Date
Nov 12, 2012, 22:27 UTC
Message-ID
<CA+TMuX2p4ck0qXijH+OOcBoveBC42U8PqnXdisau57RXwt1isg@mail.gmail.com>
In-Reply-To
<20121111165431.GA25884@sigill.intra.peff.net>
2012/11/11 Jeff King <peff@peff.net>:
Show 7 quoted lines
> On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote:
>
> 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).

I guess the optimal algorithm may also depend on the commit graph general shape, but intuitively, I'd say that the critical factor is the number and distribution of tags. As soon as you have a significant number of tags (let's say 1% of the commits are tagged, evenly distributed), you'll quickly end up with every commit marked as containing or not the target commit, so that each additional tag check is cheap.

This suggests a complexity of O(number of commits) more often then not, however you choose to traverse the graph.

At least on my almost-real-life repo*, with ~140,000 commits and ~2,000 tags, tag --contains takes a few seconds, of course more than the worst-case test on a 40,000 commit / 1 tag repo, but still in the same order of magnitude.

* : meaning we're in the process of migrating from clearcase (deep
sighs allowed !), and for now I kept almost everything in a single git
repo, which may not be the eventual choice
Jean-Jacques.
Previous: Johannes SchindelinNext: Jeff King
Message 7 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.