Re: Comments on recursive merge..

From: Linus Torvalds <torvalds@osdl.org>
Date: Nov 9, 2005, 16:30 UTC
Message-ID: <Pine.LNX.4.64.0511090800330.3247@g5.osdl.org>
In-Reply-To: <7v4q6mgm1l.fsf@assigned-by-dhcp.cox.net>

On Wed, 9 Nov 2005, Junio C Hamano wrote:

Show 6 quoted lines

> 
> As you pointed out, still_interesting means "after we are done
> with this commit, do we still have something interesting to be
> processed?", and the later "extra < 0" check compensates for
> this.  After I pop the last interesting commit, I still look at
> its parents and push them back into the list.

That "extra" check only helps once. If we ever hit the "extra--", it's gone.

In other words, follow this:

 - we start out with "extra = 0" (default value)
 - we've got one "interesting" commit left, and we just popped it.
 - we now have "still_interesting = 0"
 - the commit has just one parent, and it's not something we've seen 
   before, so we add it to the seen list and decrement "extra", which is 
   now -1. We then insert it back to the list.
 - we go back up, pop the thing we just got, and now there are again no 
   interesting commits on the list any more, so "still_interesting = 0".
 - now "extra" is -1, and we break out of the loop without ever 
   percolating the flags of this commit to its parents.

No?

> It seems to be doing the right thing after all.  I hate to admit it, but 
> I have been having hard time figuring out how this thing works X-<.  In 
> the meantime, I've checked commits from linux-2.6 history that have more 
> than one merge-base candidates.

I'm not very impressed by "it works for the seven cases I tried".

It's entirely possible that there _is_ some reason it always works, but if so, I'd like to understand it. More likely, it works in _practice_ because the only way to trigger anything else is likely such a perverse commit history that you'd never see it, but hey..

Also, I don't think this has necessarily anything to do with "multiple merge bases". As far as I can tell, we can find a potential "merge base" that starts the culling of uniniteresting things, but some other branch (that we haven't followed yet - perhaps the one we just broke out of early) may end up causing an _earlier_ commit to turn out to also be a merge-base, and the merge-base we found originally turns out to be a parent of the new one, and thus totally uninteresting.

See what I'm saying? Even with just _one_ well-defined merge base, we might hit it.

It so happens that because we traverse the commit history in date order, we almost never (but the keyword here is _almost_) hit the case where a child of a commit ends up being parsed _after_ the commit that is its parent. That only happens when there are non-synchronized clocks etc, and there are very few cases of that in the kernel tree.

Just to see how rare that is, do this:

	git-rev-list --pretty=raw HEAD |
		grep '^committer' |
		cut -d'>' -f2 |
		cut -d' ' -f2 > date-list

which basically generates the list of dates of commits in the kernel tree, sorted in the natural order that we always traverse the commits in.

Now, do

	sort -nr date-list | diff -u date-list -

to see how often the dates are off. I'm seeing only _three_ commits that have time-warps (ie they were "earlier" than one of their parents). Out of 13,000+.

So walking things in date order _almost_ always does the right thing just by mistake (well, it's not "mistake", of course. It's by design: it's the closest we can get to a nice balanced walk. But the point is that it's still just a heuristic, not something we can absolutely depend on).

And THAT was the reason for the problem with the original git-merge-base algorithm. Not multiple merge-bases (which was admittedly another problem), but the fact that it didn't give the right merge-base at all due to time warps.

(Again - it may be that there's something in show-branch that makes the optimization valid, but I just don't understand it).

			Linus