Re: Bottlenecks in git merge

From: Petr Baudis <pasky@suse.cz>
Date: Jan 31, 2006, 23:35 UTC
Message-ID: <20060131233504.GB31278@pasky.or.cz>
In-Reply-To: <7vk6cgq9ny.fsf@assigned-by-dhcp.cox.net>

Dear diary, on Wed, Feb 01, 2006 at 12:06:57AM CET, I got a letter where Junio C Hamano <junkio@cox.net> said that...

Show 38 quoted lines

> "Peter Eriksen" <s022018@student.dtu.dk> writes:
> 
> > 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.
> 
> > 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