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

[Jeff King <peff@peff.net>]

On Tue, Jul 06, 2010 at 04:31:43PM +0100, Will Palmer wrote:

> Is it wrong to expect that git perform poorly in the edge-cases (hugely
> skewed timestamps), but that it perform /correctly/ in all cases?

When you put it that way, yes, I think the ideal behavior is that we are
always correct, fast in the common case, and slow for edge cases.

But there are some fuzzy areas here:

  1. Is clock skew more than a day (or some number of seconds, whatever
     it may be) an edge case, or is it simply breakage in the repo? In
     an ideal world, it would simply be an edge case that causes
     slowdown. But git already implements traversal-cutoff based on
     date, at least in "git name-rev", so this is not a new issue. I
     know we also look at the date for some other traversals (in fact, I
     see lots of other cutoffs that don't even seem to have the one-day
     slop). But I haven't looked closely enough to see just what will
     break with a huge skew.

  2. Not implementing traversal-cutoff based on date doesn't slow just
     edge cases. It slows _all_ cases, by a factor of a hundred, on the
     off chance that you might have an edge case.

     By pre-calculating the per-repo max skew during clone and gc, you
     can turn it into your "always correct, slower for edge cases". But:

       a. It makes clone and gc a bit slower, even for non-edge cases.

       b. It is not _always_ correct, as you have a lag period between
          when skew is introduced into your repo (either by commit or by
          fetch) and when you gc it. But it's closer.

     And of course it's just complex, and I tend to shy away from
     complexity when I can. The question to me comes back to (1) above.
     Is massive clock skew a breakage that should produce a few
     incorrect results, or is it something we should always handle?

-Peff