git merge performance problem..

Junio, I think there is something wrong with git-merge. It sometimes takes up to ten seconds, and it's stuck at the

	git-show-branch --independent "$head" "$@"

call.

I don't know quite what that thing is even meant to do (we do already know the parents, why do we do something special here?) but even apart from that, the whole thing must be doing something seriously wrong, since it takes so long. Does it check the whole commit history?

		Linus

Linus Torvalds <torvalds@osdl.org> writes:

The code is to cull redundant parents primarily in octopus and is not strictly necessary. Can I have the $head and $@ (the other merge parents, but in your case you never do an octopus so that would be the other branch head) to see what is going on please? It should not descend down the history all the way but with the recent changes to the object marking/unmarking code it is possible we might have broken something.

Junio C Hamano <junkio@cox.net> writes:

Wrong. The commit log says it was to remove redundant parents; I think this as a reaction after seeing a few incorrectly made merge commits in the kernel archive.

Disregard this request please. I see a few commits that this step takes a long time to process in the kernel archive. The last merge before you left to Ottawa was one of them.

b5032a5 48ce8b0

I do not think we need to do the --independent check there especially for two-head cases because we have already done fast-forward and up-to-date tests when we get there, so let's revert that part from commit 6ea2334.

-- >8 --

On Sat, 15 Jul 2006, Junio C Hamano wrote:

Arguing with yourself? ;)

But that should already have been handled by the fact that we did the merge-base improvements. So I don't really see why we'd need the extremely heavy git-show-branch.

I think the problems we had with rmk generating patches that had two parents but really were _meant_ to be regular patches were due to an independent problem, namely that we'd commit with a stale MERGE_HEAD from a previous (failed) merge that was never done.

I think. It's a long time ago.

Yup.

And your patch will obviously fix it (by not calling git-show-branch at all), but I'm still left wondering why git-show-branch took that long in the first place. Half a minute when traversing the whole commit history only takes three seconds (as per my previous email)?

Now, as long as nothing I use actually ends up using git-show-branch, I won't care, but maybe a sign that something else can be improved?

Traditionally, what has made things _that_ slow has almost always been logic that traverses all sides of a merge, without having the logic to ignore already-seen commits (so each merge basically doubles the number of commits we will traverse, and the problem size goes from O(n+m) to O(m^2) where 'n' is number of commits, and 'm' is number of merges.

Or is git-show-branch doing something else really expensive?

		Linus

Linus Torvalds <torvalds@osdl.org> writes:

Yes, I was kind of tired ;-)

I instrumented builtin-show-branch.c::join_revs() and commit.c::merge-bases(), and run another problematic case between commits 1d3737 and 7f2857. They traverse exactly the same commits in the same order. After all in two head case they are essentially the same algorithm, modulo that the heuristics with horizon effect has not been removed from join_revs() yet.

Similarly, "merge-base --all" vs "show-branch --merge-base" between these commits has the same issue. Although they traverse exactly the same set of commits, the former takes 10x longer for some reason.

And (drumroll please), thanks to gprof, the guilty party turns out to be insert_by_date() in mark_seen().

I think this will fix both problems.

-- >8 -- show-branch: fix performance problem.

The core function used in show-branch, join_revs(), was supposed to be exactly the same algorithm as merge_bases(), except that it was a version enhanced for use with more than two heads. However, it needed to mark and keep a list of all the commits it has seen, because it needed them for its semi-graphical output. The function to implement this list, mark_seen(), stupidly used insert_by_date(), when it did not need to keep the list sorted during its processing. This made "show-branch --merge-base" more than 20x slower compared to "merge-base --all" in some cases (e.g. between b5032a5 and 48ce8b0 in the Linux 2.6 kernel archive). The performance of "show-branch --independent" suffered from the same reason.

This patch sorts the resulting list after the list traversal just once to fix these problems.

Signed-off-by: Junio C Hamano <junkio@cox.net>

---

On Sat, 15 Jul 2006, Junio C Hamano wrote:

I think it was commit b20e481 that I reacted to this time, merging b5032a5 and 48ce8b0.

Ie, lookie here:

	[torvalds@evo linux]$ time git merge-base --all b5032a5 48ce8b0
	672c6108a51bf559d19595d9f8193dfd81f0f752
	
	real    0m1.426s
	user    0m1.404s
	sys     0m0.016s

so it can find a merge-base in 1.4 seconds, which should certainly guarantee that they are independent. Then:

	[torvalds@evo linux]$ time git-show-branch --independent b5032a5 48ce8b0
	b5032a50aea76b6230db74b1d171a7f56b204bb7
	48ce8b056c88920c8ac187781048f5dae33c81b9
	
	real    0m30.657s
	user    0m30.414s
	sys     0m0.076s

Whee. Half a minute. Ok, so this is on my laptop (I'm oat the airport right now), so it was probably twice as fast on my desktop, but that is still not acceptable.

I really don't know what it's doing, because

	[torvalds@evo linux]$ time git-rev-list b5032a5 48ce8b0 > /dev/null 
	
	real    0m3.248s
	user    0m2.588s
	sys     0m0.036s

so it's really doing something very expensive - more so than just parsing the commits.

		Linus