Re: Bottlenecks in git merge

Dear diary, on Wed, Feb 01, 2006 at 12:06:57AM CET, I got a letter
where Junio C Hamano [off-list ref] said that...

"Peter Eriksen" [off-list ref] writes:

quoted

Recursive (default):  4m22.282s
Resolve (-s resolve): 3m23.548s

What is taking so long?

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

quoted

git checkout -b test v2.6.12
change_readme
git commit -a -m "Work, work, work"
time git merge $STRATEGY "Merging happily." HEAD v2.6.15

You are merging a variant of v2.6.12 and v2.6.15.  Each of these
two official revisions has roughly 18,000 files, and they differ
at 10,723 files among them.

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.

I suspect that it might make things quite faster if we resolved
case 8 and 10 (see either Documentation/technical/trivial-merge
or t/t1000) in index for this particular case, but it has
correctness issues.  A merge strategy may want to say "This file
was removed by the other branch while it stayed on our branch;
but this is not a remove but actually a rename", and do
something different from what merge-one-file does, and resolving
these cases in index closes the door for that possibility.

What about letting the file-handler actually tell merge-index what to
do? merge-index could make a fifo at fd 3 for it (we might fork a
special buffering process for it to avoid PIPE_BUF issues) and let it
write there a sequence of lines like:

	path\0{add|remove|update} {workingcopy|<sha1> <mode>}

That would avoid many in-file-handler forks and especially perpetual
reloading and rewriting of the index file, which _seems_ to be the main
time waster according to my somewhat fuzzy benchmarks.

-- 
				Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
Of the 3 great composers Mozart tells us what it's like to be human,
Beethoven tells us what it's like to be Beethoven and Bach tells us
what it's like to be the universe.  -- Douglas Adams