git-merge-recursive, was Re: [ANNOUNCE] Example Cogito Addon - cogito-bundle

On Fri, 20 Oct 2006, Linus Torvalds wrote:

On Fri, 20 Oct 2006, Aaron Bentley wrote:

quoted

Agreed.  We start by comparing BASE and OTHER, so all those comparisons
are in-memory operations that don't hit disk.  Only for files where BASE
and OTHER differ do we even examine the THIS version.

Git just slurps in all three trees. I actually think that the current 
merge-recursive.c does it the stupid way (ie it expands all trees 
recursively, regardless of whether it's needed or not), but I should 
really check with Dscho, since I had nothing to do with that code.

AFAIR yes, it does the dumb thing, namely it does not take advantage of 
trees being identical when their SHA1s are identical.

This will be a _tremendous_ speed-up.

quoted

quoted

So recursive basically generates the matrix of similarity for the 
new/deleted files, and tries to match them up, and there you have your 
renames - without ever looking at the history of how you ended up where 
you are.

So in the simple case, you compare unmatched THIS, OTHER and BASE files
to find the renames?

Right. Some cases are easy: if one of the branches only added files (which 
is relatively common), that obviously cannot be a rename. So you don't 
even have to compare all possible combinarions - you know you don't have 
renames from one branch to the other ;)

But I'm not even the authorative person to explain all the details of the 
current recursive merge, and I might have missed something. Dscho? 
Fredrik? Anything you want to add?

Not me. Only that there is much potential for optimization (meaning 
performance, not the basic algorithm).

Ciao,
Dscho