Performance problems in diffcore rename

Performance problems in diffcore rename

[Shawn Pearce]

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)

-- 

Re: Performance problems in diffcore rename

[Junio C Hamano]

Shawn Pearce <spearce@spearce.org> writes:

> But looking at is_exact_match I'm now wondering why we bother
> to open the working tree file at all here.

You are right.  When we _know_ both SHA-1 can be trusted, we
should be able to do just this, regardless of contents_too
(whose only purpose is to delay comparing a cache dirty working
tree file with something else):

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 57a74b6..677db85 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -100,9 +100,8 @@ static int is_exact_match(struct diff_filespec *src,
 			  struct diff_filespec *dst,
 			  int contents_too)
 {
-	if (src->sha1_valid && dst->sha1_valid &&
-	    !hashcmp(src->sha1, dst->sha1))
-		return 1;
+	if (src->sha1_valid && dst->sha1_valid)
+		return !hashcmp(src->sha1, dst->sha1);
 	if (!contents_too)
 		return 0;
 	if (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))

Re: Performance problems in diffcore rename

[Shawn Pearce]

Junio C Hamano <junkio@cox.net> wrote:
> Shawn Pearce <spearce@spearce.org> writes:
> 
> > But looking at is_exact_match I'm now wondering why we bother
> > to open the working tree file at all here.
> 
> You are right.  When we _know_ both SHA-1 can be trusted, we
> should be able to do just this, regardless of contents_too
> (whose only purpose is to delay comparing a cache dirty working
> tree file with something else):
> 
> diff --git a/diffcore-rename.c b/diffcore-rename.c
> index 57a74b6..677db85 100644
> --- a/diffcore-rename.c
> +++ b/diffcore-rename.c
> @@ -100,9 +100,8 @@ static int is_exact_match(struct diff_filespec *src,
>  			  struct diff_filespec *dst,
>  			  int contents_too)
>  {
> -	if (src->sha1_valid && dst->sha1_valid &&
> -	    !hashcmp(src->sha1, dst->sha1))
> -		return 1;
> +	if (src->sha1_valid && dst->sha1_valid)
> +		return !hashcmp(src->sha1, dst->sha1);
>  	if (!contents_too)
>  		return 0;
>  	if (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))
> 

Have you tested the above patch?  I have the exact same one in
my working directory right now and its failing a huge number of
the tests.  At least great minds think alike that we can make this
optimization here, but there's something amiss...

-- 

Re: Performance problems in diffcore rename

[Shawn Pearce]

Junio C Hamano <junkio@cox.net> wrote:
> Shawn Pearce <spearce@spearce.org> writes:
> 
> > But looking at is_exact_match I'm now wondering why we bother
> > to open the working tree file at all here.
> 
> You are right.  When we _know_ both SHA-1 can be trusted, we
> should be able to do just this, regardless of contents_too
> (whose only purpose is to delay comparing a cache dirty working
> tree file with something else):
> 
> diff --git a/diffcore-rename.c b/diffcore-rename.c
> index 57a74b6..677db85 100644
> --- a/diffcore-rename.c
> +++ b/diffcore-rename.c
> @@ -100,9 +100,8 @@ static int is_exact_match(struct diff_filespec *src,
>  			  struct diff_filespec *dst,
>  			  int contents_too)
>  {
> -	if (src->sha1_valid && dst->sha1_valid &&
> -	    !hashcmp(src->sha1, dst->sha1))
> -		return 1;
> +	if (src->sha1_valid && dst->sha1_valid)
> +		return !hashcmp(src->sha1, dst->sha1);
>  	if (!contents_too)
>  		return 0;
>  	if (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))
> 

OK, I've stared at this problem for hours.  The above patch breaks
a number of test cases (such as ./t4005-diff-rename-2.sh) as it
causes the rename/copy detection to come out differently.

It turns out the difference is not filling in the size field of
struct diff_filespec.  By bypassing that step in is_exact_match
during the second pass we are altering the outcome.

--