# Re: [PATCH 1/1] Bypass expensive content comparsion during rename detection. 6 messages from 2006-12-14 to 2006-12-14. Participants: Johannes Schindelin, Shawn Pearce, Shawn O. Pearce. Thread: https://gitlist.dev/t/43061 ## Shawn O. Pearce, 2006-12-14 10:07 Subject: [PATCH 1/1] Bypass expensive content comparsion during rename detection. Message-ID: <20061214100746.GA31191@spearce.org> URL: https://gitlist.dev/e/20061214100746.GA31191%40spearce.org ``` When comparing file contents during the second loop through a rename detection attempt we can skip the expensive byte-by-byte comparsion if both source and destination files have valid SHA1 values. This improves performance by avoiding either an expensive open/mmap to read the working tree copy, or an expensive inflate of a blob object. Unfortunately we still have to at least initialize the sizes of the source and destination files even if the SHA1 values don't match. Failing to initialize the sizes causes a number of test cases to fail and start reporting different copy/rename behavior than was expected. Signed-off-by: Shawn O. Pearce --- diffcore-rename.c | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-) diff --git a/diffcore-rename.c b/diffcore-rename.c index 57a74b6..91fa2be 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -109,6 +109,8 @@ static int is_exact_match(struct diff_filespec *src, return 0; if (src->size != dst->size) return 0; + if (src->sha1_valid && dst->sha1_valid) + return !hashcmp(src->sha1, dst->sha1); if (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0)) return 0; if (src->size == dst->size && -- ``` ## Johannes Schindelin, 2006-12-14 10:53 Subject: Re: [PATCH 1/1] Bypass expensive content comparsion during rename detection. Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0612141151220.3635%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: <20061214100746.GA31191@spearce.org> ``` Hi, On Thu, 14 Dec 2006, Shawn O. Pearce wrote: > When comparing file contents during the second loop through a rename > detection attempt we can skip the expensive byte-by-byte comparsion if > both source and destination files have valid SHA1 values. This improves > performance by avoiding either an expensive open/mmap to read the > working tree copy, or an expensive inflate of a blob object. > > Unfortunately we still have to at least initialize the sizes of the > source and destination files even if the SHA1 values don't match. > Failing to initialize the sizes causes a number of test cases to fail > and start reporting different copy/rename behavior than was expected. It has a wrong feel to it when you say we have to check the sizes first. After all, we are heavily relying on the hashes being different, including the case when the sizes are different. So, the order of the checks should _not_ matter. I suspect that somewhere sha1_valid should be set to 0, but isn't. Ciao, ``` ## Shawn Pearce, 2006-12-14 11:08 Subject: Re: [PATCH 1/1] Bypass expensive content comparsion during rename detection. Message-ID: <20061214110858.GE1747@spearce.org> URL: https://gitlist.dev/e/20061214110858.GE1747%40spearce.org In-Reply-To: ``` Johannes Schindelin wrote: > On Thu, 14 Dec 2006, Shawn O. Pearce wrote: > > Unfortunately we still have to at least initialize the sizes of the > > source and destination files even if the SHA1 values don't match. > > Failing to initialize the sizes causes a number of test cases to fail > > and start reporting different copy/rename behavior than was expected. > > It has a wrong feel to it when you say we have to check the sizes first. > After all, we are heavily relying on the hashes being different, including > the case when the sizes are different. So, the order of the checks should > _not_ matter. I suspect that somewhere sha1_valid should be set to 0, but > isn't. Yes. :-) I'll admit, I don't understand the diffcore rename code very well so I'm treading around in code that I'm not used to. I'm not sure why the size member of diff_filespec needs to be initialized to get rename and copy detection to work properly, but it apparently does. My first version of the patch had the hash comparsion right after we called diff_populate_filespec to get the size data. But then I realized that very often the sizes will be different and the src->size != dst->size comparsion will tend to be true most of the time, thus saving us a (relatively) expensive hash comparsion, which we know must fail anyway if the sizes differed. -- ``` ## Shawn Pearce, 2006-12-14 11:13 Subject: Re: [PATCH 1/1] Bypass expensive content comparsion during rename detection. Message-ID: <20061214111304.GF1747@spearce.org> URL: https://gitlist.dev/e/20061214111304.GF1747%40spearce.org In-Reply-To: <20061214110858.GE1747@spearce.org> ``` Shawn Pearce wrote: > I'll admit, I don't understand the diffcore rename code very well > so I'm treading around in code that I'm not used to. I'm not sure > why the size member of diff_filespec needs to be initialized to get > rename and copy detection to work properly, but it apparently does. This chunk of code is probably a perfect example of why side-effects can be so bad. Its fast because the size information is loaded once and reused later on; its horrible to maintain because you don't realize that this simple predicate is actually doing something that matters downstream even though it returned false! -- ``` ## Johannes Schindelin, 2006-12-14 11:18 Subject: Re: [PATCH 1/1] Bypass expensive content comparsion during rename detection. Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0612141214440.3635%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: <20061214110858.GE1747@spearce.org> ``` Hi, On Thu, 14 Dec 2006, Shawn Pearce wrote: > My first version of the patch had the hash comparsion right after we > called diff_populate_filespec to get the size data. But then I realized > that very often the sizes will be different and the src->size != > dst->size comparsion will tend to be true most of the time, thus saving > us a (relatively) expensive hash comparsion, which we know must fail > anyway if the sizes differed. Ah! I misunderstood. Since the call to diff_populate_filespec was not visible in the hunk, I erroneously assumed that you meant to _check_ the sizes before checking the hashes. But your explanation makes lots of sense to me. May I request a short comment above the new code, like "let diff_populate_filespec() do its thing since we need the filesize later on anyway, and having that, do the cheaper filesize check before the more expensive hashcmp()"? Ciao, Dscho ``` ## Shawn Pearce, 2006-12-14 11:50 Subject: Re: [PATCH 1/1] Bypass expensive content comparsion during rename detection. Message-ID: <20061214115054.GJ1747@spearce.org> URL: https://gitlist.dev/e/20061214115054.GJ1747%40spearce.org In-Reply-To: ``` Johannes Schindelin wrote: > Hi, > > On Thu, 14 Dec 2006, Shawn Pearce wrote: > > > My first version of the patch had the hash comparsion right after we > > called diff_populate_filespec to get the size data. But then I realized > > that very often the sizes will be different and the src->size != > > dst->size comparsion will tend to be true most of the time, thus saving > > us a (relatively) expensive hash comparsion, which we know must fail > > anyway if the sizes differed. > > Ah! I misunderstood. Since the call to diff_populate_filespec was not > visible in the hunk, I erroneously assumed that you meant to _check_ the > sizes before checking the hashes. > > But your explanation makes lots of sense to me. May I request a short > comment above the new code, like "let diff_populate_filespec() do its > thing since we need the filesize later on anyway, and having that, do the > cheaper filesize check before the more expensive hashcmp()"? -- 8> -- Bypass expensive content comparsion during rename detection. When comparing file contents during the second loop through a rename detection attempt we can skip the expensive byte-by-byte comparsion if both source and destination files have valid SHA1 values. This improves performance by avoiding either an expensive open/mmap to read the working tree copy, or an expensive inflate of a blob object. Unfortunately we still have to at least initialize the sizes of the source and destination files even if the SHA1 values don't match. Failing to initialize the sizes causes a number of test cases to fail and start reporting different copy/rename behavior than was expected. Signed-off-by: Shawn O. Pearce --- diffcore-rename.c | 9 +++++++++ 1 files changed, 9 insertions(+), 0 deletions(-) diff --git a/diffcore-rename.c b/diffcore-rename.c index 57a74b6..f7748ce 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -109,6 +109,15 @@ static int is_exact_match(struct diff_filespec *src, return 0; if (src->size != dst->size) return 0; + /* Although we can avoid a byte-by-byte comparsion by checking + * hashes we needed to allow diff_populate_filespec to fill in + * the size members, as we need that later on to correctly do + * rename and copy detection. Not filling in size before we + * return back when contents_too is true causes all sorts of + * havoc (been there, done that, lets not try it again). + */ + if (src->sha1_valid && dst->sha1_valid) + return !hashcmp(src->sha1, dst->sha1); if (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0)) return 0; if (src->size == dst->size && -- 1.4.4.2.g72f5 ```