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

From: tytso@mit.edu <tytso@mit.edu>
Date: Jul 4, 2010, 00:55 UTC
Message-ID: <20100704005543.GB6384@thunk.org>
In-Reply-To: <20100703080618.GA10483@sigill.intra.peff.net>

On Sat, Jul 03, 2010 at 04:06:19AM -0400, Jeff King wrote:

> 
> I noticed that my improved time for "git tag --contains" was similar to
> the total time for "git rev-list --all >/dev/null". Can you try timing
> that? My suspicion is that it is going to be about 2.9 seconds for you.

I'm at home, so getting access to my work machine is a bit of a pain, so I replicated the experiment at home.

% time /tmp/git.1.7.2-rc1 tag --contains 307ae18 | wc -l 13

real 0m13.706s user 0m13.542s sys 0m0.150s

% time /tmp/git.patch.1 tag --contains 307ae18 | wc -l 13

real 0m2.869s user 0m2.703s sys 0m0.163s

% time /tmp/git.patch.1 rev-list --all  > /dev/null

real 0m3.074s user 0m2.920s sys 0m0.147s

> Try the patch below, which adds a date cutoff similar to the one used in
> name-rev. It's much faster in my tests:

Yep, much faster indeed:

% time /tmp/git.patch.2 tag --contains 307ae18 | wc -l 13

real 0m0.054s user 0m0.030s sys 0m0.023s

> The obvious downside is that it stops looking down a path in the face of
> extreme clock skew. We could perhaps allow a "--contains=thorough" to
> spend a little more time to achieve a better answer (i.e., ignore the
> cutoff date).

Yep, it does blow up in the face of the extreme clock skew in some of the ext4 commits in the Linux kernel tree. (Sorry about that; mea culpa, I didn't realize at the time this was a problem, and it was my workflow using the guilt program which happened to introduce them.)

In any case, because of the ext4 commits, I can show a test case which doesn't work well with your date cutoff patch:

#!/bin/sh

for i in $(git log --reverse --oneline v2.6.32..v2.6.35-rc3 fs/ext4 fs/jbd2 |
      	       awk '{print $1}')
do
    echo -n "$i "
    /tmp/git.patch.2 tag --contains $i | head -1
done

You won't see any problems after v2.6.34; I fixed my workflow once I was told it was causing git problems.

If you replace this with the unpatched git, or with git with your first patch, it will be of course much slower, but it will print out all of the tags that would be expected given a topographical examination of the commit graph. Whether this is a bug in git or a bug that I introduced into the Linux kernel git tree is of course an open question. However, if we do want to allow git operations to work quickly --- and I agree this is a good thing; the speedups that this can allow are quite significant --- maybe we should teach "git commit" to either print a warning or outright refuse to introduce clock skews in the first place.

(Or maybe we have git config options that can enable or disable optimizations that depend on the lack of clock skews; but I could understand people not wanting to maintian the extra code paths.)

	   	      	      	 	  - Ted