Re: Bottlenecks in git merge

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