Re: Bottlenecks in git merge

From: Linus Torvalds <torvalds@osdl.org>
Date: Jan 31, 2006, 23:45 UTC
Message-ID: <Pine.LNX.4.64.0601311533040.7301@g5.osdl.org>
In-Reply-To: <7vk6cgq9ny.fsf@assigned-by-dhcp.cox.net>

On Tue, 31 Jan 2006, Junio C Hamano wrote:

> 
> I am actually surprised that recursive is not much slower than
> resolve.  I expected to see bigger difference for a merge like
> this.

Well, if most of the cost is just the trivial single-file merges and the fact that we have to update a ton of files from an old version (and it probably is), the difference between the trivial and the recursive merge is not going to be huge.

Show 9 quoted lines

> With an up-to-date index that has small changes from v2.6.12,
> merging these two revisions using read-tree -m to do the trivial
> merge (the part that comes before recursive/resolve) leaves
> about 850 files to be resolved in the working tree.  For these
> files, you need to do an equivalent of merge-one-file to merge
> the differences (in this particular case, most of them are
> "removed in one but unchanged in the other" kind).  In addition,
> you have to checkout the result of the merge, which means you
> need to update at least 10,723 files.

It would be interesting to see how big the "resolve 850 files" part is vs the "check out 10k+ files" is.

In particular, if the "resolve 850 files" is a noticeable portion of it, then the right thing to do may be to just re-write git-merge-one-file.sh in C. Right now, almost _all_ of the expense of that thing is just the shell interpreter startup. The actual actions it does are usually fairly cheap.

(yes, a real three-way merge is more expensive, but I suspect that even that isn't much more expensive than starting up an invocation of "bash". The other actions that merge-one-file does are _really_ trivial).

In fact, we could hardcode the "git-merge-one-file" behaviour inside "git-merge-index".

Now, that won't help "recursive" (which doesn't use git-merge-one-file at all, and does it all by hand), but it would be an interesting test to make, becuase if it makes the simpler "-s resolve" merge even faster, then we know that this is likely a large portion of the time.

Then, somebody would have to consider what to do about git-merge-recursive. For example, if the _common_ case is "modified in both, but differently", and they merge cleanly, maybe the recursive merge could handle those separately and fast with a special "git-merge-one-file" invocation (just to cut down the number of files that it needs to think more about).

		Linus