Re: Why is "git tag --contains" so slow?

From: Jeff King <peff@peff.net>
Date: Jul 1, 2010, 15:03 UTC
Message-ID: <20100701150331.GA12851@sigill.intra.peff.net>
In-Reply-To: <20100701121711.GF1333@thunk.org>

On Thu, Jul 01, 2010 at 08:17:11AM -0400, tytso@mit.edu wrote:

Show 5 quoted lines

> Yeah, I'm not talking about the tag and branch names that show up in
> the top gitk box (and which you can also get via git log --annotate).
> I'm specifically talking about what you get with:
> 
> 	git tags --contains <commit-id>

I think there is room for improving the speed of "git tag --contains". Consider these two similar operations:

  $ time git name-rev HEAD~200
  HEAD~200 tags/v1.7.1-rc2~2

  real    0m0.060s
  user    0m0.048s
  sys     0m0.012s

  $ time git tag --contains HEAD~200
  v1.7.1
  v1.7.1-rc2
  v1.7.1.1
  v1.7.2-rc0
  v1.7.2-rc1

  real    0m2.179s
  user    0m2.156s
  sys     0m0.020s

Obviously the latter is producing the full list of tags, but both should have to do a traversal starting at each tag ref.

It looks like "git tag --contains" is implemented as something like:

  for ref in `git tag -l`; do
    if `git merge-base $ref $commit | grep $commit`; then
      echo $ref
    fi
  done

except in C. But you can see we'll do a full merge-base calculation for each tag. And that merge-base calculation may potentially go quite far back in history.

The name-rev code has a simple heuristic that it stops traversing when the timestamp of the traversed commit gets more than a day behind that of $commit. This doesn't do well with clock skew, but can save a lot of time in practice. We should perhaps consider something like that here.

I suspect we could do even better by sharing information between traversals. That is, walk the graph from each ref, but retain marks on commits between each walk. For a commit c, if walking down each parent gets us to a root without hitting $commit, then we can mark "c" as not possibly containing the commit. We can cut short any walk when we hit a "c" that is already marked. So by traversing from "v1.7.1", if we find that we do not contain $commit, we will have already marked v1.7.0, v1.6.*, etc, and will not need to traverse them again.

When you do find one that contains $commit, you can also mark it as "definitely contains", and you can stop a traversal that definitely contains. So if we see something is in v1.7.0, then the traversal from v1.7.1 only needs to go as far back as v1.7.0.

-Peff