Optimize run_diff_files()' rename detection
cover Optimize run_diff_files()' rename detection
Just another patch from Git for Windows' branch thicket...
Jeff Hostetler (1):
diffcore-rename: speed up register_rename_src
diffcore-rename.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)
base-commit: 8104ec994ea3849a968b4667d072fedd1e688642
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-142%2Fdscho%2Fregister_rename_src-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-142/dscho/register_rename_src-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/142
Signature · 1 line
gitgitgadget
PATCH 1/1 diffcore-rename: speed up register_rename_src
From: Jeff Hostetler <[email protected]>
Teach register_rename_src() to see if new file pair can simply be appended to the rename_src[] array before performing the binary search to find the proper insertion point.
This is a performance optimization. This routine is called during run_diff_files in status and the caller is iterating over the sorted index, so we should expect to be able to append in the normal case. The existing insert logic is preserved so we don't have to assume that, but simply take advantage of it if possible.
--- diffcore-rename.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)
diffcore-rename.c +13 -0
@@ -82,6 +82,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p) first =0 ; last = rename_src_nr; + +if (last >0 ) { +struct diff_rename_src *src = &(rename_src[last-1 ]); +int cmp =strcmp (one->path, src->p->one->path); +if (!cmp) +return src; +if (cmp >0 ) { + first = last; + goto append_it; + } + } +while (last > first) {int next = (last + first) >>1 ;struct diff_rename_src *src = &(rename_src[next]);
@@ -95,6 +107,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p) first = next+1 ; } +append_it:/* insert to make it at "first" */ ALLOC_GROW (rename_src, rename_src_nr +1 , rename_src_alloc); rename_src_nr++;
Signature · 1 line
gitgitgadget
Re: [PATCH 1/1] diffcore-rename: speed up register_rename_src
Am 08.06.19 um 16:42 schrieb Jeff Hostetler via GitGitGadget:
Quoted 27 lines
From: Jeff Hostetler <[email protected]>
Teach
register_rename_src()to see if new file pair can simply be appended to the rename_src[] array before performing the binary search to find the proper insertion point.This is a performance optimization. This routine is called during
run_diff_filesin status and the caller is iterating over the sorted index, so we should expect to be able to append in the normal case. The existing insert logic is preserved so we don't have to assume that, but simply take advantage of it if possible.Signed-off-by Jeff Hostetler <[email protected]>Signed-off-by Johannes Schindelin <[email protected]>--- diffcore-rename.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)diffcore-rename.c +0
-0@@ -82,6 +82,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p) first =0 ;
diffcore-rename.c static struct diff_rename_src *register_rename_src(struct diff_filepair *p) · line 93
Quoted 10 lines
diffcore-rename.c +9
-0last = rename_src_nr; + +if (last >0 ) { +struct diff_rename_src *src = &(rename_src[last-1 ]); +int cmp =strcmp (one->path, src->p->one->path); +if (!cmp) +return src; +if (cmp >0 ) { + first = last; + goto append_it;
The goto is not necessary from a logical point of view; the binary search is skipped even without it because the loop condition below is not met anymore.
diffcore-rename.c static struct diff_rename_src *register_rename_src(struct diff_filepair *p) · line 94
Quoted 1 line
diffcore-rename.c +1
-0+ }
You could decrement "last" at this point as a micro-optimization, to use all three possible outcomes of the comparison to make some progress.
Not sure if any of that would have a _measurable_ impact, though, so I don't mind the patch going in as is.
diffcore-rename.c static struct diff_rename_src *register_rename_src(struct diff_filepair *p) · line 98
Quoted 4 lines
diffcore-rename.c +2
-0+ } +while (last > first) {int next = (last + first) >>1 ;
Hmm, "last" and "first" are ints as well, so this will give weird results when "last" > INT_MAX / 2. I thought 19716b21a4 ("cleanup: fix possible overflow errors in binary search", 2017-10-08) got us rid of those, but git grep -n '(.*+.*) >> 1' actually finds some more cases:
builtin/ls-files.c:376: int next = (last + first) >> 1; diffcore-rename.c:26: int next = (last + first) >> 1; diffcore-rename.c:86: int next = (last + first) >> 1;
dir.c:704: int cmp, next = (last + first) >> 1;
name-hash.c:349: int mid = (begin + end) >> 1;
read-cache.c:552: int next = (last + first) >> 1;
sh-i18n--envsubst.c:252: size_t j = (j1 + j2) >> 1;
(Not caused by this patch, of course, just noticed it in the context.)
diffcore-rename.c static struct diff_rename_src *register_rename_src(struct diff_filepair *p) · line 113
Quoted 10 lines
diffcore-rename.c +1
-0struct diff_rename_src *src = &(rename_src[next]);@@ -95,6 +107,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p) first = next+1 ; } +append_it:/* insert to make it at "first" */ ALLOC_GROW (rename_src, rename_src_nr +1 , rename_src_alloc); rename_src_nr++;
Anyway, this here should work as well (and fix the possible overflow), but may be too terse and quirky:
diffcore-rename.c +2 -3
@@ -76,14 +76,13 @@ static int rename_src_nr, rename_src_alloc;static struct diff_rename_src *register_rename_src (struct diff_filepair *p) { -int first, last; +int first, last, next;struct diff_filespec *one = p->one;unsigned short score = p->score; first =0 ; last = rename_src_nr; -while (last > first) { -int next = (last + first) >>1 ; +for (next = last -1 ; last > first; next = first + (last - first) /2 ) {struct diff_rename_src *src = &(rename_src[next]);int cmp =strcmp (one->path, src->p->one->path);if (!cmp)
Re: [PATCH 1/1] diffcore-rename: speed up register_rename_src
In reply to Jeff Hostetler via GitGitGadgetQuoted 7 lines · Jeff Hostetler via GitGitGadget
From: Jeff Hostetler <[email protected]>
Teach
register_rename_src()to see if new file pair can simply be appended to the rename_src[] array before performing the binary search to find the proper insertion point.
Quoted 6 lines
This is a performance optimization. This routine is called during
run_diff_filesin status and the caller is iterating over the sorted index, so we should expect to be able to append in the normal case. The existing insert logic is preserved so we don't have to assume that, but simply take advantage of it if possible.
Could you add a command and performance figures to the commit message to show off the benefits of this patch?
From the description it's clear that it's a performance optimization, but it's unclear whether it has a noticeable, or at least measurable effect, or it's "only" a micro-optimization.
I tried something more substantial than a simple 'git status':
# without this patch $ time perf record -g ./git log --oneline -m --name-only v2.20.0 >/dev/null [ ... ]
real 2m4.320s
user 2m0.913s
sys 0m2.284s
$ perf report -g none |grep -E '(diffcore_rename|register_rename_src)'
52.40% 0.79% git git [.] diffcore_rename
0.01% 0.01% git git [.] register_rename_srcbut it looks like that while more than half of the considerable runtime is spent detecting renames, the time spent in register_rename_src(), the function optimized in this patch, is negligible.
Quoted 39 lines
Signed-off-by Jeff Hostetler <[email protected]>Signed-off-by Johannes Schindelin <[email protected]>--- diffcore-rename.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)diffcore-rename.c +13
-0@@ -82,6 +82,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p) first =0 ; last = rename_src_nr; + +if (last >0 ) { +struct diff_rename_src *src = &(rename_src[last-1 ]); +int cmp =strcmp (one->path, src->p->one->path); +if (!cmp) +return src; +if (cmp >0 ) { + first = last; + goto append_it; + } + } +while (last > first) {int next = (last + first) >>1 ;struct diff_rename_src *src = &(rename_src[next]);@@ -95,6 +107,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p) first = next+1 ; } +append_it:/* insert to make it at "first" */ ALLOC_GROW (rename_src, rename_src_nr +1 , rename_src_alloc); rename_src_nr++;Signature · 1 line
gitgitgadget
Re: [PATCH 1/1] diffcore-rename: speed up register_rename_src
In reply to René ScharfeQuoted 27 lines · René Scharfe
Am 08.06.19 um 16:42 schrieb Jeff Hostetler via GitGitGadget:
Quoted 26 lines
From: Jeff Hostetler <[email protected]>
Teach
register_rename_src()to see if new file pair can simply be appended to the rename_src[] array before performing the binary search to find the proper insertion point.This is a performance optimization. This routine is called during
run_diff_filesin status and the caller is iterating over the sorted index, so we should expect to be able to append in the normal case. The existing insert logic is preserved so we don't have to assume that, but simply take advantage of it if possible.Signed-off-by Jeff Hostetler <[email protected]>Signed-off-by Johannes Schindelin <[email protected]>--- diffcore-rename.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)diffcore-rename.c +0
-0@@ -82,6 +82,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)
Quoted 15 lines
diffcore-rename.c static struct diff_rename_src *register_rename_src(struct diff_filepair *p) · line 93
Quoted 11 lines
diffcore-rename.c +9
-0first =0 ; last = rename_src_nr; + +if (last >0 ) { +struct diff_rename_src *src = &(rename_src[last-1 ]); +int cmp =strcmp (one->path, src->p->one->path); +if (!cmp) +return src; +if (cmp >0 ) { + first = last; + goto append_it;The goto is not necessary from a logical point of view; the binary search is skipped even without it because the loop condition below is not met anymore.
Perhaps this is just a personal style thing, but I prefer the goto because it makes it clear that we know the answer and are done searching. I know it's a small thing and I know we do it all the time, but setting state here in just the right way as to defeat the loop would work, but is a little less clear. But again, that is a personal style thing I guess.
Quoted 7 lines
diffcore-rename.c static struct diff_rename_src *register_rename_src(struct diff_filepair *p) · line 94
Quoted 1 line
diffcore-rename.c +1
-0+ }You could decrement "last" at this point as a micro-optimization, to use all three possible outcomes of the comparison to make some progress.
Not sure if any of that would have a _measurable_ impact, though, so I don't mind the patch going in as is.
Yes, it looks like we could decrement "last" here. And yes, I suspect it would have minimal impact. I'll pass on that in this series to keep it focused on the advertised goal of simply appending if possible.
Quoted 47 lines
diffcore-rename.c static struct diff_rename_src *register_rename_src(struct diff_filepair *p) · line 98
Quoted 5 lines
diffcore-rename.c +2
-0+ } +while (last > first) {int next = (last + first) >>1 ;Hmm, "last" and "first" are ints as well, so this will give weird results when "last" >
INT_MAX/ 2. I thought19716b21a4("cleanup: fix possible overflow errors in binary search", 2017-10-08) got us rid of those, but git grep -n '(.*+.*) >> 1' actually finds some more cases:builtin/ls-files.c:376: int next = (last + first) >> 1; diffcore-rename.c:26: int next = (last + first) >> 1; diffcore-rename.c:86: int next = (last + first) >> 1; dir.c:704: int cmp, next = (last + first) >> 1; name-hash.c:349: int mid = (begin + end) >> 1; read-cache.c:552: int next = (last + first) >> 1; sh-i18n--envsubst.c:252: size_t j = (j1 + j2) >> 1;(Not caused by this patch, of course, just noticed it in the context.)
diffcore-rename.c static struct diff_rename_src *register_rename_src(struct diff_filepair *p) · line 113
Quoted 10 lines
diffcore-rename.c +1
-0struct diff_rename_src *src = &(rename_src[next]);@@ -95,6 +107,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p) first = next+1 ; } +append_it:/* insert to make it at "first" */ ALLOC_GROW (rename_src, rename_src_nr +1 , rename_src_alloc); rename_src_nr++;Anyway, this here should work as well (and fix the possible overflow), but may be too terse and quirky:
diffcore-rename.c +1
-1@@ -76,14 +76,13 @@ static int rename_src_nr, rename_src_alloc;static struct diff_rename_src *register_rename_src (struct diff_filepair *p) { -int first, last; +int first, last, next;struct diff_filespec *one = p->one;
diffcore-rename.c static int rename_src_nr, rename_src_alloc; · line 88
Quoted 10 lines
diffcore-rename.c +1
-2unsigned short score = p->score; first =0 ; last = rename_src_nr; -while (last > first) { -int next = (last + first) >>1 ; +for (next = last -1 ; last > first; next = first + (last - first) /2 ) {struct diff_rename_src *src = &(rename_src[next]);int cmp =strcmp (one->path, src->p->one->path);if (!cmp)
I'd like to limit the scope of this patch series to just the advertised topic and save the arithmetic fixes to another patch series like 19716b21a4.
Jeff
Quoted 5 lines · Johannes Schindelin via GitGitGadget
Just another patch from Git for Windows' branch thicket...
Jeff Hostetler (1):
diffcore-rename: speed upregister_rename_src
Quoted 9 lines
diffcore-rename.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)base-commit:
8104ec994ea3849a968b4667d072fedd1e688642
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-142%2Fdscho%2Fregister_rename_src-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-142/dscho/register_rename_src-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/142
For the sake of full disclosure, we added this patch to Git for Windows in December 2016.
It was discussed on the mailing list in April 2017 [1] but it was shelved for various reasons.
Let me put this one on hold while I dig up my notes from 2016 and re-review of the original mailing list suggestions and see where I want to take this patch going forward.
Jeff
Re: [PATCH 1/1] diffcore-rename: speed up register_rename_src
In reply to SZEDER GáborQuoted 35 lines · SZEDER Gábor
Quoted 7 lines · Jeff Hostetler via GitGitGadget
From: Jeff Hostetler <[email protected]>
Teach
register_rename_src()to see if new file pair can simply be appended to the rename_src[] array before performing the binary search to find the proper insertion point.Quoted 6 lines
This is a performance optimization. This routine is called during
run_diff_filesin status and the caller is iterating over the sorted index, so we should expect to be able to append in the normal case. The existing insert logic is preserved so we don't have to assume that, but simply take advantage of it if possible.Could you add a command and performance figures to the commit message to show off the benefits of this patch?
From the description it's clear that it's a performance optimization,
but it's unclear whether it has a noticeable, or at least measurable effect, or it's "only" a micro-optimization.I tried something more substantial than a simple 'git status':
# without this patch $ time perf record -g ./git log --oneline -m --name-only v2.20.0 >/dev/null [ ... ]real 2m4.320s user 2m0.913s sys 0m2.284s $ perf report -g none |grep -E '(diffcore_rename|register_rename_src)' 52.40% 0.79% git git [.] diffcore_rename 0.01% 0.01% git git [.] register_rename_src
Quoted 5 lines
but it looks like that while more than half of the considerable runtime is spent detecting renames, the time spent in
register_rename_src(), the function optimized in this patch, is negligible.
I just wanted to send an ACK. I'll include perf numbers and more clarity after I dig up my notes on this.
Jeff