Subject: Performance problems in diffcore rename

From: Shawn Pearce <[email-masked]>
Date: Wed, 13 Dec 2006 22:39:26 -0500

Originally I had thought I was running into an infinite loop in
git-merge-recursive while trying to merge two branches together
which have been troublesome in the past.

That's not the case.  I spent some time debugging it tonight on
the private (unpublishable) repository that is showing the problem.
What is actually occuring is one of the branches has 6735 files
added between the merge base and its tip, and the other branch
has roughly the same number.

git-merge-recursive very quickly goes down into the diffcore code to
perform rename detection, at which point we come up with 6735 files
for rename_dst_nr (in diffcore_rename) and we almost immediately
wind up with contents_too = 1, which means we are now doing full
content comparsions in is_exact_match.

What really hurts is when we go into diff_populate_filespec we
proceed to take the optimization that Junio added in 6973dcae,
which is to favor mmap'ing the working tree file over inflating
the blob from the ODB.

Except that in my case I'm running on Cygwin/Windows 2000 and almost
everything is packed.  So inflating the blob out of the ODB is a
thousand times faster than opening the working directory file and
mmap'ing it.  If I modify work_tree_matches to always return false
the merge goes through in under 3 seconds.

Running the same merge on Solaris doesn't show the problem at all,
as that OS has reasonably well performing open and mmap syscalls.

But looking at is_exact_match I'm now wondering why we bother
to open the working tree file at all here.  Its almost like
we are missing the following, as both src and dst are coming out
of tree objects and therefore their sha1's should match.

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 57a74b6..29480ca 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -105,6 +105,8 @@ static int is_exact_match(struct diff_filespec *src,
 		return 1;
 	if (!contents_too)
 		return 0;
+	if (src->sha1_valid && dst->sha1_valid)
+		return 0;
 	if (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))
 		return 0;
 	if (src->size != dst->size)

--