Re: Git commit generation numbers

On Fri, Jul 15, 2011 at 04:10:23PM -0700, Linus Torvalds wrote:

On Fri, Jul 15, 2011 at 2:17 PM, Linus Torvalds
[off-list ref] wrote:

quoted

For example, for the "git tag --contains" thing, what's the
performance effect of just skipping tags that are much older than the
commit we ask for?

Hmm.

Maybe there is something seriously wrong with this trivial patch, but
it gave the right results for the test-cases I threw at it, and passes
the tests.

Before:

   [torvalds@i5 linux]$ time git tag --contains v2.6.24 > correct

   real	0m7.548s
   user	0m7.344s
   sys	0m0.116s

After:

   [torvalds@i5 linux]$ time ~/git/git tag --contains v2.6.24 > date-cut-off

   real	0m0.161s
   user	0m0.140s
   sys	0m0.016s

and 'correct' and 'date-cut-off' both give the same answer.

Without even looking carefully at your patches for any minor mistakes, I
can tell you that the speedup you're seeing is approximately right.
Because it's almost exactly the same optimization I made in my
timestamp-based patches (links to which I sent you earlier today).

However, you can make it even faster. The "tag --contains" code will ask
"is_descendant_of" repeatedly for the same set of "want" commits. So you
end up traversing some parts of the graph over and over. My patches
share the marks over a set of contains traversals, so you only ever
touch each commit once. And that's what my patches do.

With yours, on my box:

  $ time git tag --contains HEAD~1000 >/dev/null
  real    0m0.113s
  user    0m0.104s
  sys     0m0.008s

and mine:

  $ time git tag --contains HEAD~1000 >/dev/null
  real    0m0.035s
  user    0m0.020s
  sys     0m0.012s

I suspect you can make the difference even more prominent by having more
tags, or by having multiple "want" commits.

-Peff