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

On Mon, Nov 12, 2012 at 11:27:14PM +0100, Jean-Jacques Lafay wrote:

We can do much better than O(number of commits), though, if we stop traversing down a path when its timestamp shows that it is too old to contain the commits we are searching for. The problem is that the timestamps cannot always be trusted, because they are generated on machines with wrong clocks, or by buggy software. This could be solved by calculating and caching a "generation" number, but last time it was discussed there was a lot of arguing and nothing got done.

Another approach, used by the merge-base calculation, is to treat parents in a breadth-first way, but sort them by timestamp, and walk backwards to find the merge-base (and if you get to a merge-base, you can stop). In that case, bad timestamps may cause you to look at extra commits (because you process a commit prematurely and end up going deeper than the merge base), but it can never give you a wrong answer.

Thinking on it more, though, the merge-base style of computation would mean you always have to walk backwards to the oldest tag. Which is in the same order of magnitude as the number of commits, assuming you have tags near the start of history. So I think we will always want to keep a cutoff, anyway, and there is not much point in switching off of a depth-first approach (but of course it does make sense to use iteration instead of recursion to do so).

Try "git rev-list --count --all" to get a sense of how long O(# of commits) takes. Before the depth-first implementation, "tag --contains" was O(commits * tags) in the worst case. With depth first, it's O(commits), and then with the timestamp cutoff, it's really O(commits since needle), where "needle" is the oldest thing you're looking for. Here are those numbers on linux-2.6 (with linux-stable tags):

  [to get a sense of the repo size]
  $ git for-each-ref refs/tags | wc -l
  909
  $ git rev-list --count --all
  363413

  [this is O(commits)]
  $ time git rev-list --count --all
  real    0m4.034s
  user    0m3.960s
  sys     0m0.056s

  [before depth-first, ffc4b80^; you can see that it is much worse than
   O(commits), though not as bad as the worst case (because finding the
   merge bases for recent tags is not O(commits)]
  $ time git tag --contains HEAD~200
  real    0m42.838s
  user    0m42.527s
  sys     0m0.156s

  [after depth-first, ffc4b80; you can see that this is O(commits),
   because we will go depth-first down to the roots, but do only a
   single traversal]
  $ time git tag --contains HEAD~200
  real    0m3.939s
  user    0m3.784s
  sys     0m0.140s

  [with my generation patches; much faster]
  $ time git tag --contains HEAD~200
  real    0m0.037s
  user    0m0.020s
  sys     0m0.012s

I was thinking we had merged the timestamp cutoff (which has the same performance characteristics as generations, just with the skew issue) to master, but it looks like we didn't.

-Peff