{"thread":{"id":"43134","subject":"Performance problems in diffcore rename","startedAt":"2006-12-14T03:39:26Z","lastAt":"2006-12-14T09:11:45Z","messageCount":4,"participants":["Shawn Pearce","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"293895","messageId":"20061214033925.GA1408@spearce.org","threadId":"43134","inReplyTo":null,"subject":"Performance problems in diffcore rename","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-12-14T03:39:26Z","receivedAt":"2006-12-14T03:39:26Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Originally I had thought I was running into an infinite loop in\ngit-merge-recursive while trying to merge two branches together\nwhich have been troublesome in the past.\n\nThat's not the case. I spent some time debugging it tonight on\nthe private (unpublishable) repository that is showing the problem.\nWhat is actually occuring is one of the branches has 6735 files\nadded between the merge base and its tip, and the other branch\nhas roughly the same number.\n\ngit-merge-recursive very quickly goes down into the diffcore code to\nperform rename detection, at which point we come up with 6735 files\nfor rename_dst_nr (in diffcore_rename) and we almost immediately\nwind up with contents_too = 1, which means we are now doing full\ncontent comparsions in is_exact_match.\n\nWhat really hurts is when we go into diff_populate_filespec we\nproceed to take the optimization that Junio added in 6973dcae,\nwhich is to favor mmap'ing the working tree file over inflating\nthe blob from the ODB.\n\nExcept that in my case I'm running on Cygwin/Windows 2000 and almost\neverything is packed. So inflating the blob out of the ODB is a\nthousand times faster than opening the working directory file and\nmmap'ing it. If I modify work_tree_matches to always return false\nthe merge goes through in under 3 seconds.\n\n\nRunning the same merge on Solaris doesn't show the problem at all,\nas that OS has reasonably well performing open and mmap syscalls.\n\n\nBut looking at is_exact_match I'm now wondering why we bother\nto open the working tree file at all here. Its almost like\nwe are missing the following, as both src and dst are coming out\nof tree objects and therefore their sha1's should match.\n\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 57a74b6..29480ca 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -105,6 +105,8 @@ static int is_exact_match(struct diff_filespec *src,\n \t\treturn 1;\n \tif (!contents_too)\n \t\treturn 0;\n+\tif (src->sha1_valid && dst->sha1_valid)\n+\t\treturn 0;\n \tif (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))\n \t\treturn 0;\n \tif (src->size != dst->size)\n\n-- \n"},{"id":"295289","messageId":"7v7iwvatrt.fsf@assigned-by-dhcp.cox.net","threadId":"43134","inReplyTo":"20061214033925.GA1408@spearce.org","subject":"Re: Performance problems in diffcore rename","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-12-14T06:14:30Z","receivedAt":"2006-12-14T06:14:30Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> But looking at is_exact_match I'm now wondering why we bother\n> to open the working tree file at all here.\n\nYou are right. When we _know_ both SHA-1 can be trusted, we\nshould be able to do just this, regardless of contents_too\n(whose only purpose is to delay comparing a cache dirty working\ntree file with something else):\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 57a74b6..677db85 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -100,9 +100,8 @@ static int is_exact_match(struct diff_filespec *src,\n \t\t\t struct diff_filespec *dst,\n \t\t\t int contents_too)\n {\n-\tif (src->sha1_valid && dst->sha1_valid &&\n-\t !hashcmp(src->sha1, dst->sha1))\n-\t\treturn 1;\n+\tif (src->sha1_valid && dst->sha1_valid)\n+\t\treturn !hashcmp(src->sha1, dst->sha1);\n \tif (!contents_too)\n \t\treturn 0;\n \tif (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))\n"},{"id":"294617","messageId":"20061214061652.GA1747@spearce.org","threadId":"43134","inReplyTo":"7v7iwvatrt.fsf@assigned-by-dhcp.cox.net","subject":"Re: Performance problems in diffcore rename","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-12-14T06:16:52Z","receivedAt":"2006-12-14T06:16:52Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Shawn Pearce writes:\n> \n> > But looking at is_exact_match I'm now wondering why we bother\n> > to open the working tree file at all here.\n> \n> You are right. When we _know_ both SHA-1 can be trusted, we\n> should be able to do just this, regardless of contents_too\n> (whose only purpose is to delay comparing a cache dirty working\n> tree file with something else):\n> \n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 57a74b6..677db85 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -100,9 +100,8 @@ static int is_exact_match(struct diff_filespec *src,\n> \t\t\t struct diff_filespec *dst,\n> \t\t\t int contents_too)\n> {\n> -\tif (src->sha1_valid && dst->sha1_valid &&\n> -\t !hashcmp(src->sha1, dst->sha1))\n> -\t\treturn 1;\n> +\tif (src->sha1_valid && dst->sha1_valid)\n> +\t\treturn !hashcmp(src->sha1, dst->sha1);\n> \tif (!contents_too)\n> \t\treturn 0;\n> \tif (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))\n> \n\nHave you tested the above patch? I have the exact same one in\nmy working directory right now and its failing a huge number of\nthe tests. At least great minds think alike that we can make this\noptimization here, but there's something amiss...\n\n-- \n"},{"id":"294268","messageId":"20061214091145.GB1747@spearce.org","threadId":"43134","inReplyTo":"7v7iwvatrt.fsf@assigned-by-dhcp.cox.net","subject":"Re: Performance problems in diffcore rename","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-12-14T09:11:45Z","receivedAt":"2006-12-14T09:11:45Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Shawn Pearce writes:\n> \n> > But looking at is_exact_match I'm now wondering why we bother\n> > to open the working tree file at all here.\n> \n> You are right. When we _know_ both SHA-1 can be trusted, we\n> should be able to do just this, regardless of contents_too\n> (whose only purpose is to delay comparing a cache dirty working\n> tree file with something else):\n> \n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 57a74b6..677db85 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -100,9 +100,8 @@ static int is_exact_match(struct diff_filespec *src,\n> \t\t\t struct diff_filespec *dst,\n> \t\t\t int contents_too)\n> {\n> -\tif (src->sha1_valid && dst->sha1_valid &&\n> -\t !hashcmp(src->sha1, dst->sha1))\n> -\t\treturn 1;\n> +\tif (src->sha1_valid && dst->sha1_valid)\n> +\t\treturn !hashcmp(src->sha1, dst->sha1);\n> \tif (!contents_too)\n> \t\treturn 0;\n> \tif (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))\n> \n\nOK, I've stared at this problem for hours. The above patch breaks\na number of test cases (such as ./t4005-diff-rename-2.sh) as it\ncauses the rename/copy detection to come out differently.\n\nIt turns out the difference is not filling in the size field of\nstruct diff_filespec. By bypassing that step in is_exact_match\nduring the second pass we are altering the outcome.\n\n-- \n"}]}