Re: git merge performance problem..

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

Junio C Hamano [off-list ref] writes:

quoted

The code is to cull redundant parents primarily in octopus and
is not strictly necessary.

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.

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.

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

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