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

[Johannes Schindelin]

On Fri, 20 Oct 2006, Linus Torvalds wrote:

> On Fri, 20 Oct 2006, Aaron Bentley wrote:
> > 
> > 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.

> > > 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