threads / discuss / 43134

Performance problems in diffcore rename

Subject: Performance problems in diffcore rename

## tl;dr

4 messages between Dec 14, 2006 and Dec 14, 2006.

replies: 3people: 2as markdown or json

Shawn Pearce· Dec 14, 2006, 03:39 UTC · lore

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)
Junio C Hamano· Dec 14, 2006, 06:14 UTC · re: Shawn Pearce · lore

Re: Performance problems in diffcore rename

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))
Shawn Pearce· Dec 14, 2006, 06:16 UTC · re: Junio C Hamano · lore

Re: Performance problems in diffcore rename

Junio C Hamano <junkio@cox.net> wrote:
Show 27 quoted lines
> 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...

Shawn Pearce· Dec 14, 2006, 09:11 UTC · re: Junio C Hamano · lore

Re: Performance problems in diffcore rename

Junio C Hamano <junkio@cox.net> wrote:
Show 27 quoted lines
> 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.

← back to recent threads