Re: git merge performance problem..

From: Linus Torvalds <torvalds@osdl.org>
Date: Jul 16, 2006, 04:43 UTC
Message-ID: <Pine.LNX.4.64.0607152136010.2438@evo.osdl.org>
In-Reply-To: <7vlkqukwhb.fsf@assigned-by-dhcp.cox.net>

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

Show 8 quoted lines

> Junio C Hamano <junkio@cox.net> writes:
> >
> > 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.

Show 5 quoted lines

> 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