Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

From: Jeff King <peff@peff.net>
Date: Jul 15, 2011, 20:40 UTC
Message-ID: <20110715204002.GC356@sigill.intra.peff.net>
In-Reply-To: <7vpqlb1k1g.fsf@alter.siamese.dyndns.org>

On Fri, Jul 15, 2011 at 11:22:03AM -0700, Junio C Hamano wrote:

Show 7 quoted lines

> > +	/* stop searching if we go too far back in time */
> > +	if (commit_generation(candidate) < cutoff)
> > +		return 0;
> > +
> 
> Here, the "generation number" was the commit timestamp of the commit in
> your earlier round, but now it is not.

Yes.

Show 5 quoted lines

> [...]
> What you are trying to say in this series is that "If a tag points at a
> commit X (i.e. candidate), another commit Y (i.e. "want") that is much
> younger than cannot possibly be included by it, because a tag was made on
> commit X way before Y was created". You cut off by "age".

More or less. Given two ages, X and Y, you cannot know right off the bat whether one is an ancestor of the other. You can only know that the higher generation cannot possibly be an ancestor of the lower generation.

So yes, in some cases we will see that the tag has generation 5, and the "want" commit has generation 10, and we will know there is no point in traversing backwards from 5.

But we may also see a tag with generation 10, and a want commit with generation 5. In that case, we have to explore backwards, looking to either find the commit, or to pass a point where we hit a commit with generation less than 5, at which point we know the want commit cannot be an ancestor.

So if you have a history like:

    B
   /
  A--C--D--...--Z

and you want to know if "B" is in "Z", you will have to traverse all the way from Z to A before realizing that B cannot be in it. That will have the same complexity as finding a merge base (because the merge-base would breadth-first traverse, looking at the highest age first, and would therefore touch the same sequence of commits).

Show 16 quoted lines

> The heuristics would work efficiently to check what tags point at a
> relatively recent commit (e.g. when trying to see which releases are
> affected and needing a fix by a recently discovered bug introduced by
> commit Y) by discarding tags for ancient releases. In such a scenario, the
> timestamp of a tagged and ancient commit X on a side branch that was never
> merged in the mainline that leads to commit Y (i.e. "want"), in an ideal
> world without clock skews, will be way older than the timestamp of commit
> Y. In other words, if you use timestamp as "age", even though X and Y do
> not relate to each other directly, except that they may share an ancient
> common ancestor, their "age"s can be compared and you could apply your
> heuristics to optimize.
> 
> But if you use the generation number as "age", even in an ideal world
> without clock skew nor miscomputed generation number, you no longer can
> compare "age" of X and Y.  The ancient side branch that led to X may have
> tons more commits than the history leading to Y.

Yes, there are cases where commit timestamps can save us some traversal work over generation numbers. But I think there are also cases where the reverse is true.

Your example is of a long side branch with very old commits. But you could also have a short side branch with a very recent commit (think recent bugfix forked from an old version). Then with commit timestamps we need to go to the merge base to realize we are talking about something very old. With a generation number, you can easily see that the short branch's generation is very low.

Using both as a cutoff (if we assumed we had both, and that they were both implicitly accurate) would let you optimize for either situation. In practice, timestamps are either good enough that we don't need generation numbers, or are considered to be strictly less accurate than generation numbers.

So I think we will end up with one or the other. Of all of the complaints I have seen over the use of timestamps for cutoffs, I don't think performance of these corner cases has been an issue.

Show 6 quoted lines

>    So how about marking commits (using the metainfo-cache facility) that
>    has an ancestor (not necessarily its direct parent) that records a
>    younger timestamp (e.g. 1 is such a commit, as its ancestors include
>    things like 2 and 4)? There should be relatively small number of them,
>    and still_interesting() logic can be told to dig through such commits
>    even if everybody is uninteresting in the active list.

You don't even need metainfo-cache for this. The number of commits is very small, so the existing "notes-cache" is plenty fast. I even posted a patch for this already:

  http://article.gmane.org/gmane.comp.version-control.git/176642

Show 5 quoted lines

>  * As to "tag --contains", when timestamp based heuristics breaks down is
>    when a tagged commit incorrectly records way young timestamp or the
>    "want" commit records way old timetsamp. I haven't thought things
>    through, but the same metainfo-cache may be useful to detect which
>    commit to dig through ignoring the cutoff heuristics.

It can also break down if intermediate commits are wrong, because we have to traverse backwards, and we may erroneously cutoff early.

For example:

   A--B--C

   timestamp(A) = 2
   timestamp(B) = 1 # skewed!
   timestamp(C) = 3

If tag=C and want=A, then we traverse backwards from C. We can't stop immediately because we know that 2 < 3. But we go back to B, and see that 2 > 1, and assume that A cannot possibly be an ancestor of B.

You can push through another N commits of slop (where N=1 would be fine in this case). But you can always have a run of N+1 skewed commits (and the higher N, the more time you are wasting). From earlier measurements posted to the list, most repos have runs less than a dozen commits. Linux-2.6 is actually the second highest of those measured, with a run of 80. The mesa repo apparently has a run of 1520. See:

  http://article.gmane.org/gmane.comp.version-control.git/160163

and the surrounding thread (Jonathan did some measurements, too; he didn't include a "longest run", but he does include "total number of skewed commits", which obviously provides an upper bound on a run).

-Peff