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 - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html