Re: Git commit generation numbers

From: Jeff King <peff@peff.net>
Date: Jul 16, 2011, 00:40 UTC
Message-ID: <20110716004034.GA32230@sigill.intra.peff.net>
In-Reply-To: <CA+55aFzE-okH9gaEyuSFdorK-7v3odpsk65ZTqCMHFz80n65ug@mail.gmail.com>

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

Show 30 quoted lines

> On Fri, Jul 15, 2011 at 2:17 PM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> >
> > 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