Re: Bottlenecks in git merge

[Linus Torvalds <torvalds@osdl.org>]

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.

> 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