{"thread":{"id":"51267","subject":"[PATCH 0/1] Optimize run_diff_files()' rename detection","startedAt":"2019-06-08T14:42:45Z","lastAt":"2019-06-10T14:55:34Z","messageCount":7,"participants":["Johannes Schindelin via GitGitGadget","Jeff Hostetler via GitGitGadget","René Scharfe","SZEDER Gábor","Jeff Hostetler"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"376858","messageId":"pull.142.git.gitgitgadget@gmail.com","threadId":"51267","inReplyTo":null,"subject":"[PATCH 0/1] Optimize run_diff_files()' rename detection","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-06-08T14:42:41Z","receivedAt":"2019-06-08T14:42:45Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Just another patch from Git for Windows' branch thicket...\n\nJeff Hostetler (1):\n diffcore-rename: speed up register_rename_src\n\n diffcore-rename.c | 13 +++++++++++++\n 1 file changed, 13 insertions(+)\n\n\nbase-commit: 8104ec994ea3849a968b4667d072fedd1e688642\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-142%2Fdscho%2Fregister_rename_src-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-142/dscho/register_rename_src-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/142\n-- \ngitgitgadget\n"},{"id":"376859","messageId":"4ac75dd3635e39f9faa67fb1e88897663e3dc6cd.1560004960.git.gitgitgadget@gmail.com","threadId":"51267","inReplyTo":"pull.142.git.gitgitgadget@gmail.com","subject":"[PATCH 1/1] diffcore-rename: speed up register_rename_src","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-06-08T14:42:42Z","receivedAt":"2019-06-08T14:42:46Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nTeach register_rename_src() to see if new file pair\ncan simply be appended to the rename_src[] array before\nperforming the binary search to find the proper insertion\npoint.\n\nThis is a performance optimization. This routine is called\nduring run_diff_files in status and the caller is iterating\nover the sorted index, so we should expect to be able to\nappend in the normal case. The existing insert logic is\npreserved so we don't have to assume that, but simply take\nadvantage of it if possible.\n\nSigned-off-by: Jeff Hostetler \nSigned-off-by: Johannes Schindelin \n---\n diffcore-rename.c | 13 +++++++++++++\n 1 file changed, 13 insertions(+)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 07bd34b631..5bfc5f6c22 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -82,6 +82,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n \n \tfirst = 0;\n \tlast = rename_src_nr;\n+\n+\tif (last > 0) {\n+\t\tstruct diff_rename_src *src = &(rename_src[last-1]);\n+\t\tint cmp = strcmp(one->path, src->p->one->path);\n+\t\tif (!cmp)\n+\t\t\treturn src;\n+\t\tif (cmp > 0) {\n+\t\t\tfirst = last;\n+\t\t\tgoto append_it;\n+\t\t}\n+\t}\n+\n \twhile (last > first) {\n \t\tint next = (last + first) >> 1;\n \t\tstruct diff_rename_src *src = &(rename_src[next]);\n@@ -95,6 +107,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n \t\tfirst = next+1;\n \t}\n \n+append_it:\n \t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n \trename_src_nr++;\n-- \ngitgitgadget\n"},{"id":"376868","messageId":"bcaff0ce-365d-1d17-6ea0-7e3b52fc928b@web.de","threadId":"51267","inReplyTo":"4ac75dd3635e39f9faa67fb1e88897663e3dc6cd.1560004960.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/1] diffcore-rename: speed up register_rename_src","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2019-06-08T22:27:51Z","receivedAt":"2019-06-08T22:28:20Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 08.06.19 um 16:42 schrieb Jeff Hostetler via GitGitGadget:\n> From: Jeff Hostetler \n>\n> Teach register_rename_src() to see if new file pair\n> can simply be appended to the rename_src[] array before\n> performing the binary search to find the proper insertion\n> point.\n>\n> This is a performance optimization. This routine is called\n> during run_diff_files in status and the caller is iterating\n> over the sorted index, so we should expect to be able to\n> append in the normal case. The existing insert logic is\n> preserved so we don't have to assume that, but simply take\n> advantage of it if possible.\n>\n> Signed-off-by: Jeff Hostetler \n> Signed-off-by: Johannes Schindelin \n> ---\n> diffcore-rename.c | 13 +++++++++++++\n> 1 file changed, 13 insertions(+)\n>\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 07bd34b631..5bfc5f6c22 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -82,6 +82,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n>\n> \tfirst = 0;\n> \tlast = rename_src_nr;\n> +\n> +\tif (last > 0) {\n> +\t\tstruct diff_rename_src *src = &(rename_src[last-1]);\n> +\t\tint cmp = strcmp(one->path, src->p->one->path);\n> +\t\tif (!cmp)\n> +\t\t\treturn src;\n> +\t\tif (cmp > 0) {\n> +\t\t\tfirst = last;\n> +\t\t\tgoto append_it;\n\nThe goto is not necessary from a logical point of view; the binary\nsearch is skipped even without it because the loop condition below is\nnot met anymore.\n\n> +\t\t}\n\nYou could decrement \"last\" at this point as a micro-optimization, to use\nall three possible outcomes of the comparison to make some progress.\n\nNot sure if any of that would have a _measurable_ impact, though, so I\ndon't mind the patch going in as is.\n\n> +\t}\n> +\n> \twhile (last > first) {\n> \t\tint next = (last + first) >> 1;\n\nHmm, \"last\" and \"first\" are ints as well, so this will give weird results\nwhen \"last\" > INT_MAX / 2. I thought 19716b21a4 (\"cleanup: fix possible\noverflow errors in binary search\", 2017-10-08) got us rid of those, but\ngit grep -n '(.*+.*) >> 1' actually finds some more cases:\n\n builtin/ls-files.c:376: int next = (last + first) >> 1;\n diffcore-rename.c:26: int next = (last + first) >> 1;\n diffcore-rename.c:86: int next = (last + first) >> 1;\n dir.c:704: int cmp, next = (last + first) >> 1;\n name-hash.c:349: int mid = (begin + end) >> 1;\n read-cache.c:552: int next = (last + first) >> 1;\n sh-i18n--envsubst.c:252: size_t j = (j1 + j2) >> 1;\n\n(Not caused by this patch, of course, just noticed it in the context.)\n\n> \t\tstruct diff_rename_src *src = &(rename_src[next]);\n> @@ -95,6 +107,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n> \t\tfirst = next+1;\n> \t}\n>\n> +append_it:\n> \t/* insert to make it at \"first\" */\n> \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n> \trename_src_nr++;\n>\n\nAnyway, this here should work as well (and fix the possible overflow),\nbut may be too terse and quirky:\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 07bd34b631..f2a9007e08 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -76,14 +76,13 @@ static int rename_src_nr, rename_src_alloc;\n\n static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n {\n-\tint first, last;\n+\tint first, last, next;\n \tstruct diff_filespec *one = p->one;\n \tunsigned short score = p->score;\n\n \tfirst = 0;\n \tlast = rename_src_nr;\n-\twhile (last > first) {\n-\t\tint next = (last + first) >> 1;\n+\tfor (next = last - 1; last > first; next = first + (last - first) / 2) {\n \t\tstruct diff_rename_src *src = &(rename_src[next]);\n \t\tint cmp = strcmp(one->path, src->p->one->path);\n \t\tif (!cmp)\n"},{"id":"376922","messageId":"20190610122632.GA4012@szeder.dev","threadId":"51267","inReplyTo":"4ac75dd3635e39f9faa67fb1e88897663e3dc6cd.1560004960.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/1] diffcore-rename: speed up register_rename_src","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-06-10T12:26:33Z","receivedAt":"2019-06-10T12:26:41Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Sat, Jun 08, 2019 at 07:42:42AM -0700, Jeff Hostetler via GitGitGadget wrote:\n> From: Jeff Hostetler \n> \n> Teach register_rename_src() to see if new file pair\n> can simply be appended to the rename_src[] array before\n> performing the binary search to find the proper insertion\n> point.\n> \n> This is a performance optimization. This routine is called\n> during run_diff_files in status and the caller is iterating\n> over the sorted index, so we should expect to be able to\n> append in the normal case. The existing insert logic is\n> preserved so we don't have to assume that, but simply take\n> advantage of it if possible.\n\nCould you add a command and performance figures to the commit message\nto show off the benefits of this patch?\n\nFrom the description it's clear that it's a performance optimization,\nbut it's unclear whether it has a noticeable, or at least measurable\neffect, or it's \"only\" a micro-optimization.\n\nI tried something more substantial than a simple 'git status':\n\n # without this patch\n $ time perf record -g ./git log --oneline -m --name-only v2.20.0 >/dev/null\n [ ... ]\n \n real 2m4.320s\n user 2m0.913s\n sys 0m2.284s\n $ perf report -g none |grep -E '(diffcore_rename|register_rename_src)'\n 52.40% 0.79% git git [.] diffcore_rename\n 0.01% 0.01% git git [.] register_rename_src\n\nbut it looks like that while more than half of the considerable\nruntime is spent detecting renames, the time spent in\nregister_rename_src(), the function optimized in this patch, is\nnegligible.\n\n\n> Signed-off-by: Jeff Hostetler \n> Signed-off-by: Johannes Schindelin \n> ---\n> diffcore-rename.c | 13 +++++++++++++\n> 1 file changed, 13 insertions(+)\n> \n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 07bd34b631..5bfc5f6c22 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -82,6 +82,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n> \n> \tfirst = 0;\n> \tlast = rename_src_nr;\n> +\n> +\tif (last > 0) {\n> +\t\tstruct diff_rename_src *src = &(rename_src[last-1]);\n> +\t\tint cmp = strcmp(one->path, src->p->one->path);\n> +\t\tif (!cmp)\n> +\t\t\treturn src;\n> +\t\tif (cmp > 0) {\n> +\t\t\tfirst = last;\n> +\t\t\tgoto append_it;\n> +\t\t}\n> +\t}\n> +\n> \twhile (last > first) {\n> \t\tint next = (last + first) >> 1;\n> \t\tstruct diff_rename_src *src = &(rename_src[next]);\n> @@ -95,6 +107,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n> \t\tfirst = next+1;\n> \t}\n> \n> +append_it:\n> \t/* insert to make it at \"first\" */\n> \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n> \trename_src_nr++;\n> -- \n> gitgitgadget\n"},{"id":"376929","messageId":"bf63c8cc-7146-6f13-cb77-785763fb77c8@jeffhostetler.com","threadId":"51267","inReplyTo":"bcaff0ce-365d-1d17-6ea0-7e3b52fc928b@web.de","subject":"Re: [PATCH 1/1] diffcore-rename: speed up register_rename_src","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2019-06-10T14:23:11Z","receivedAt":"2019-06-10T14:23:15Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 6/8/2019 6:27 PM, René Scharfe wrote:\n> Am 08.06.19 um 16:42 schrieb Jeff Hostetler via GitGitGadget:\n>> From: Jeff Hostetler \n>>\n>> Teach register_rename_src() to see if new file pair\n>> can simply be appended to the rename_src[] array before\n>> performing the binary search to find the proper insertion\n>> point.\n>>\n>> This is a performance optimization. This routine is called\n>> during run_diff_files in status and the caller is iterating\n>> over the sorted index, so we should expect to be able to\n>> append in the normal case. The existing insert logic is\n>> preserved so we don't have to assume that, but simply take\n>> advantage of it if possible.\n>>\n>> Signed-off-by: Jeff Hostetler \n>> Signed-off-by: Johannes Schindelin \n>> ---\n>> diffcore-rename.c | 13 +++++++++++++\n>> 1 file changed, 13 insertions(+)\n>>\n>> diff --git a/diffcore-rename.c b/diffcore-rename.c\n>> index 07bd34b631..5bfc5f6c22 100644\n>> --- a/diffcore-rename.c\n>> +++ b/diffcore-rename.c\n>> @@ -82,6 +82,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n>>\n>> \tfirst = 0;\n>> \tlast = rename_src_nr;\n>> +\n>> +\tif (last > 0) {\n>> +\t\tstruct diff_rename_src *src = &(rename_src[last-1]);\n>> +\t\tint cmp = strcmp(one->path, src->p->one->path);\n>> +\t\tif (!cmp)\n>> +\t\t\treturn src;\n>> +\t\tif (cmp > 0) {\n>> +\t\t\tfirst = last;\n>> +\t\t\tgoto append_it;\n> \n> The goto is not necessary from a logical point of view; the binary\n> search is skipped even without it because the loop condition below is\n> not met anymore.\n\nPerhaps this is just a personal style thing, but I prefer the\ngoto because it makes it clear that we know the answer and are\ndone searching. I know it's a small thing and I know we do it\nall the time, but setting state here in just the right way as\nto defeat the loop would work, but is a little less clear. But\nagain, that is a personal style thing I guess.\n\n\n>> +\t\t}\n> \n> You could decrement \"last\" at this point as a micro-optimization, to use\n> all three possible outcomes of the comparison to make some progress.\n> \n> Not sure if any of that would have a _measurable_ impact, though, so I\n> don't mind the patch going in as is.\n\nYes, it looks like we could decrement \"last\" here. And yes, I\nsuspect it would have minimal impact. I'll pass on that in this\nseries to keep it focused on the advertised goal of simply\nappending if possible.\n\n> \n>> +\t}\n>> +\n>> \twhile (last > first) {\n>> \t\tint next = (last + first) >> 1;\n> \n> Hmm, \"last\" and \"first\" are ints as well, so this will give weird results\n> when \"last\" > INT_MAX / 2. I thought 19716b21a4 (\"cleanup: fix possible\n> overflow errors in binary search\", 2017-10-08) got us rid of those, but\n> git grep -n '(.*+.*) >> 1' actually finds some more cases:\n> \n> builtin/ls-files.c:376: int next = (last + first) >> 1;\n> diffcore-rename.c:26: int next = (last + first) >> 1;\n> diffcore-rename.c:86: int next = (last + first) >> 1;\n> dir.c:704: int cmp, next = (last + first) >> 1;\n> name-hash.c:349: int mid = (begin + end) >> 1;\n> read-cache.c:552: int next = (last + first) >> 1;\n> sh-i18n--envsubst.c:252: size_t j = (j1 + j2) >> 1;\n> \n> (Not caused by this patch, of course, just noticed it in the context.)\n> \n>> \t\tstruct diff_rename_src *src = &(rename_src[next]);\n>> @@ -95,6 +107,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n>> \t\tfirst = next+1;\n>> \t}\n>>\n>> +append_it:\n>> \t/* insert to make it at \"first\" */\n>> \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n>> \trename_src_nr++;\n>>\n> \n> Anyway, this here should work as well (and fix the possible overflow),\n> but may be too terse and quirky:\n> \n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 07bd34b631..f2a9007e08 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -76,14 +76,13 @@ static int rename_src_nr, rename_src_alloc;\n> \n> static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n> {\n> -\tint first, last;\n> +\tint first, last, next;\n> \tstruct diff_filespec *one = p->one;\n> \tunsigned short score = p->score;\n> \n> \tfirst = 0;\n> \tlast = rename_src_nr;\n> -\twhile (last > first) {\n> -\t\tint next = (last + first) >> 1;\n> +\tfor (next = last - 1; last > first; next = first + (last - first) / 2) {\n> \t\tstruct diff_rename_src *src = &(rename_src[next]);\n> \t\tint cmp = strcmp(one->path, src->p->one->path);\n> \t\tif (!cmp)\n> \n\nI'd like to limit the scope of this patch series to just\nthe advertised topic and save the arithmetic fixes to\nanother patch series like 19716b21a4.\n\nJeff\n"},{"id":"376930","messageId":"bd404b8b-7747-3e29-8d14-ed2f04d12292@jeffhostetler.com","threadId":"51267","inReplyTo":"pull.142.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/1] Optimize run_diff_files()' rename detection","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2019-06-10T14:43:36Z","receivedAt":"2019-06-10T14:43:38Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 6/8/2019 10:42 AM, Johannes Schindelin via GitGitGadget wrote:\n> Just another patch from Git for Windows' branch thicket...\n> \n> Jeff Hostetler (1):\n> diffcore-rename: speed up register_rename_src\n> \n> diffcore-rename.c | 13 +++++++++++++\n> 1 file changed, 13 insertions(+)\n> \n> \n> base-commit: 8104ec994ea3849a968b4667d072fedd1e688642\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-142%2Fdscho%2Fregister_rename_src-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-142/dscho/register_rename_src-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/142\n> \n\nFor the sake of full disclosure, we added this patch\nto Git for Windows in December 2016.\n\nIt was discussed on the mailing list in April 2017 [1] but\nit was shelved for various reasons.\n\nLet me put this one on hold while I dig up my notes from 2016\nand re-review of the original mailing list suggestions and\nsee where I want to take this patch going forward.\n\nJeff\n\n\n[1] \nhttps://public-inbox.org/git/20170418194421.22453-1-git@jeffhostetler.com/\n"},{"id":"376931","messageId":"9c3e18d3-00f4-834f-6a7a-42fd45e69b0e@jeffhostetler.com","threadId":"51267","inReplyTo":"20190610122632.GA4012@szeder.dev","subject":"Re: [PATCH 1/1] diffcore-rename: speed up register_rename_src","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2019-06-10T14:55:30Z","receivedAt":"2019-06-10T14:55:34Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 6/10/2019 8:26 AM, SZEDER Gábor wrote:\n> On Sat, Jun 08, 2019 at 07:42:42AM -0700, Jeff Hostetler via GitGitGadget wrote:\n>> From: Jeff Hostetler \n>>\n>> Teach register_rename_src() to see if new file pair\n>> can simply be appended to the rename_src[] array before\n>> performing the binary search to find the proper insertion\n>> point.\n>>\n>> This is a performance optimization. This routine is called\n>> during run_diff_files in status and the caller is iterating\n>> over the sorted index, so we should expect to be able to\n>> append in the normal case. The existing insert logic is\n>> preserved so we don't have to assume that, but simply take\n>> advantage of it if possible.\n> \n> Could you add a command and performance figures to the commit message\n> to show off the benefits of this patch?\n> \n> From the description it's clear that it's a performance optimization,\n> but it's unclear whether it has a noticeable, or at least measurable\n> effect, or it's \"only\" a micro-optimization.\n> \n> I tried something more substantial than a simple 'git status':\n> \n> # without this patch\n> $ time perf record -g ./git log --oneline -m --name-only v2.20.0 >/dev/null\n> [ ... ]\n> \n> real 2m4.320s\n> user 2m0.913s\n> sys 0m2.284s\n> $ perf report -g none |grep -E '(diffcore_rename|register_rename_src)'\n> 52.40% 0.79% git git [.] diffcore_rename\n> 0.01% 0.01% git git [.] register_rename_src\n> \n> but it looks like that while more than half of the considerable\n> runtime is spent detecting renames, the time spent in\n> register_rename_src(), the function optimized in this patch, is\n> negligible.\n> \n\nI just wanted to send an ACK. I'll include perf numbers\nand more clarity after I dig up my notes on this.\n\nJeff\n\n"}]}