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