{"thread":{"id":"45610","subject":"[PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list","startedAt":"2017-04-05T19:56:17Z","lastAt":"2017-04-07T04:30:21Z","messageCount":10,"participants":["git@jeffhostetler.com","Stefan Beller","Jeff King","Jeff Hostetler","Jonathan Nieder"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"316230","messageId":"20170405195600.54801-2-git@jeffhostetler.com","threadId":"45610","inReplyTo":"20170405195600.54801-1-git@jeffhostetler.com","subject":"[PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-05T19:55:59Z","receivedAt":"2017-04-05T19:56:17Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nUse ALLOC_GROW() macro when reallocing a string_list array\nrather than simply increasing it by 32.  This is a performance\noptimization.\n\nDuring status on a very large repo and there are many changes,\na significant percentage of the total run time was spent\nreallocing the wt_status.changes array.\n\nThis change decreased the time in wt_status_collect_changes_worktree()\nfrom 125 seconds to 45 seconds on my very large repository.\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n string-list.c | 6 ++----\n 1 file changed, 2 insertions(+), 4 deletions(-)\n\ndiff --git a/string-list.c b/string-list.c\nindex 45016ad..cd4c4e0 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -41,10 +41,8 @@ static int add_entry(int insert_at, struct string_list *list, const char *string\n \tif (exact_match)\n \t\treturn -1 - index;\n \n-\tif (list->nr + 1 >= list->alloc) {\n-\t\tlist->alloc += 32;\n-\t\tREALLOC_ARRAY(list->items, list->alloc);\n-\t}\n+\tif (list->nr + 1 >= list->alloc)\n+\t\tALLOC_GROW(list->items, list->nr+1, list->alloc);\n \tif (index < list->nr)\n \t\tmemmove(list->items + index + 1, list->items + index,\n \t\t\t\t(list->nr - index)\n-- \n2.9.3\n\n"},{"id":"316231","messageId":"20170405195600.54801-1-git@jeffhostetler.com","threadId":"45610","inReplyTo":null,"subject":"[PATCH v1 0/2] string-list: use ALLOC_GROW macro when reallocing","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-05T19:55:58Z","receivedAt":"2017-04-05T19:56:19Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nUse ALLOC_GROW() macro when reallocating a string_list array\nrather than simply increasing it by 32.  This helps performance\nof status on very large repos on Windows.\n\nJeff Hostetler (2):\n  string-list: use ALLOC_GROW macro when reallocing string_list\n  p0005-status: time status on very large repo\n\n string-list.c          |  6 ++---\n t/perf/p0005-status.sh | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 72 insertions(+), 4 deletions(-)\n create mode 100644 t/perf/p0005-status.sh\n\n-- \n2.9.3\n\n"},{"id":"316232","messageId":"20170405195600.54801-3-git@jeffhostetler.com","threadId":"45610","inReplyTo":"20170405195600.54801-1-git@jeffhostetler.com","subject":"[PATCH v1 2/2] p0005-status: time status on very large repo","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-05T19:56:00Z","receivedAt":"2017-04-05T19:56:20Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n t/perf/p0005-status.sh | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 70 insertions(+)\n create mode 100644 t/perf/p0005-status.sh\n\ndiff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh\nnew file mode 100644\nindex 0000000..4a25ba0\n--- /dev/null\n+++ b/t/perf/p0005-status.sh\n@@ -0,0 +1,70 @@\n+#!/bin/sh\n+\n+test_description=\"Tests performance of read-tree\"\n+\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+test_checkout_worktree\n+\n+## usage: dir depth width files\n+make_paths () {\n+\tfor f in $(seq $4)\n+\tdo\n+\t\techo $1/file$f\n+\tdone;\n+\tif test $2 -gt 0;\n+\tthen\n+\t\tfor w in $(seq $3)\n+\t\tdo\n+\t\t\tmake_paths $1/dir$w $(($2 - 1)) $3 $4\n+\t\tdone\n+\tfi\n+\treturn 0\n+}\n+\n+fill_index () {\n+\tmake_paths $1 $2 $3 $4 |\n+\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n+\tgit update-index --index-info\n+\treturn 0\n+}\n+\n+br_work1=xxx_work1_xxx\n+\n+new_dir=xxx_dir_xxx\n+\n+## (5, 10, 9) will create 999,999 files.\n+## (4, 10, 9) will create  99,999 files.\n+depth=5\n+width=10\n+files=9\n+\n+export br_work1\n+\n+export new_dir\n+\n+export depth\n+export width\n+export files\n+\n+## Inflate the index with thousands of empty files and commit it.\n+test_expect_success 'inflate the index' '\n+\tgit reset --hard &&\n+\tgit branch $br_work1 &&\n+\tgit checkout $br_work1 &&\n+\tfill_index $new_dir $depth $width $files &&\n+\tgit commit -m $br_work1 &&\n+\tgit reset --hard\n+'\n+\n+## The number of files in the xxx_work1_xxx branch.\n+nr_work1=$(git ls-files | wc -l)\n+export nr_work1\n+\n+test_perf \"read-tree status work1 ($nr_work1)\" '\n+\tgit read-tree HEAD &&\n+\tgit status\n+'\n+\n+test_done\n-- \n2.9.3\n\n"},{"id":"316233","messageId":"CAGZ79kYFjuESBr72f5eyv7r4XohzY4KoQU36pqHLa3CsLuKi9w@mail.gmail.com","threadId":"45610","inReplyTo":"20170405195600.54801-2-git@jeffhostetler.com","subject":"Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-04-05T20:00:57Z","receivedAt":"2017-04-05T20:01:10Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Apr 5, 2017 at 12:55 PM,  <git@jeffhostetler.com> wrote:\n> +       if (list->nr + 1 >= list->alloc)\n> +               ALLOC_GROW(list->items, list->nr+1, list->alloc);\n\nNo need for the condition here as it is part of the macro as well.\n\nThanks for spotting this fix!\nStefan\n"},{"id":"316234","messageId":"20170405200954.jmjvuzwjploenbho@sigill.intra.peff.net","threadId":"45610","inReplyTo":"20170405195600.54801-2-git@jeffhostetler.com","subject":"Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-05T20:09:55Z","receivedAt":"2017-04-05T20:10:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 05, 2017 at 07:55:59PM +0000, git@jeffhostetler.com wrote:\n\n> From: Jeff Hostetler <jeffhost@microsoft.com>\n> \n> Use ALLOC_GROW() macro when reallocing a string_list array\n> rather than simply increasing it by 32.  This is a performance\n> optimization.\n> \n> During status on a very large repo and there are many changes,\n> a significant percentage of the total run time was spent\n> reallocing the wt_status.changes array.\n> \n> This change decreased the time in wt_status_collect_changes_worktree()\n> from 125 seconds to 45 seconds on my very large repository.\n\nOof. Looks like the original was quadratic. I'm surprised this didn't\nbite us more often. I guess we don't usually use string-lists for big\nlists.\n\nAside from the redundant size-check that Stefan pointed out, the patch\nlooks obviously correct. I grepped for \"alloc +=\" and \"alloc =.*+' to\nsee if there were any other cases, but didn't find any. Obviously that\nis dependent on calling the variable \"alloc\", but that is normal for us\n(and it does turn up a number of cases that do allocate correctly).\n\n-Peff\n"},{"id":"316238","messageId":"e805dfdd-12a4-cb70-d4e6-b5af915d29b5@jeffhostetler.com","threadId":"45610","inReplyTo":"20170405200954.jmjvuzwjploenbho@sigill.intra.peff.net","subject":"Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-05T21:12:37Z","receivedAt":"2017-04-05T21:12:54Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/5/2017 4:09 PM, Jeff King wrote:\n> On Wed, Apr 05, 2017 at 07:55:59PM +0000, git@jeffhostetler.com wrote:\n>\n>> From: Jeff Hostetler <jeffhost@microsoft.com>\n>>\n>> Use ALLOC_GROW() macro when reallocing a string_list array\n>> rather than simply increasing it by 32.  This is a performance\n>> optimization.\n>>\n>> During status on a very large repo and there are many changes,\n>> a significant percentage of the total run time was spent\n>> reallocing the wt_status.changes array.\n>>\n>> This change decreased the time in wt_status_collect_changes_worktree()\n>> from 125 seconds to 45 seconds on my very large repository.\n>\n> Oof. Looks like the original was quadratic. I'm surprised this didn't\n> bite us more often. I guess we don't usually use string-lists for big\n> lists.\n\nTo be fair, I was playing with a repo with 3M files\nand I think realloc() is more efficient on Linux, so\nI'm not surprised that we haven't seen it even with\nrepos the size of linux.git.\n\n>\n> Aside from the redundant size-check that Stefan pointed out, the patch\n> looks obviously correct. I grepped for \"alloc +=\" and \"alloc =.*+' to\n> see if there were any other cases, but didn't find any. Obviously that\n> is dependent on calling the variable \"alloc\", but that is normal for us\n> (and it does turn up a number of cases that do allocate correctly).\n>\n> -Peff\n>\n"},{"id":"316239","messageId":"20170405212620.GG8741@aiede.mtv.corp.google.com","threadId":"45610","inReplyTo":"20170405195600.54801-2-git@jeffhostetler.com","subject":"Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-04-05T21:26:20Z","receivedAt":"2017-04-05T21:26:29Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\ngit@jeffhostetler.com wrote:\n\n> During status on a very large repo and there are many changes,\n> a significant percentage of the total run time was spent\n> reallocing the wt_status.changes array.\n\nNit: commit messages tend to use the present tense instead of the past\nwhen describing Git's current behavior.  That makes it easier for\nreaders to tell whether you are describing the present or the distant\npast.\n\n> This change decreased the time in wt_status_collect_changes_worktree()\n> from 125 seconds to 45 seconds on my very large repository.\n\nNice.\n\nThis is also just the right thing to do.  The linear growth would\nproduce potentially (potentially because you can be lucky and allocate\nin the first place somewhere with a lot of room) quadratic behavior as\nrealloc copies the allocation to increasingly larger regions.\n\n> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n> ---\n>  string-list.c | 6 ++----\n>  1 file changed, 2 insertions(+), 4 deletions(-)\n>\n> diff --git a/string-list.c b/string-list.c\n> index 45016ad..cd4c4e0 100644\n> --- a/string-list.c\n> +++ b/string-list.c\n> @@ -41,10 +41,8 @@ static int add_entry(int insert_at, struct string_list *list, const char *string\n>  \tif (exact_match)\n>  \t\treturn -1 - index;\n>  \n> -\tif (list->nr + 1 >= list->alloc) {\n> -\t\tlist->alloc += 32;\n> -\t\tREALLOC_ARRAY(list->items, list->alloc);\n> -\t}\n> +\tif (list->nr + 1 >= list->alloc)\n> +\t\tALLOC_GROW(list->items, list->nr+1, list->alloc);\n\nThis checks for >= but ALLOC_GROW only grows when the new size is >.\nThe new code is less eager about growing than the old was, forcing me\nto look at the other code to find the correct invariant.\n\nFortunately (1) string_list_append_nodup already uses ALLOC_GROW the\nway this patch does and (2) REALLOC_ARRAY determines the meaning of\nlist->alloc.  The >= was just overeager and this is safe.\n\nAfter removing the unnecessary 'if' as described by Stefan,\nReviewed-by: Jonathan Nieder <jrnieder@gmail.com>\n\nThanks.\n"},{"id":"316240","messageId":"20170405213355.GH8741@aiede.mtv.corp.google.com","threadId":"45610","inReplyTo":"20170405195600.54801-3-git@jeffhostetler.com","subject":"Re: [PATCH v1 2/2] p0005-status: time status on very large repo","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-04-05T21:33:55Z","receivedAt":"2017-04-05T21:34:03Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\ngit@jeffhostetler.com wrote:\n\n> +++ b/t/perf/p0005-status.sh\n> @@ -0,0 +1,70 @@\n> +#!/bin/sh\n> +\n> +test_description=\"Tests performance of read-tree\"\n> +\n> +. ./perf-lib.sh\n> +\n> +test_perf_default_repo\n> +test_checkout_worktree\n> +\n> +## usage: dir depth width files\n> +make_paths () {\n> +\tfor f in $(seq $4)\n> +\tdo\n> +\t\techo $1/file$f\n> +\tdone;\n> +\tif test $2 -gt 0;\n> +\tthen\n> +\t\tfor w in $(seq $3)\n> +\t\tdo\n> +\t\t\tmake_paths $1/dir$w $(($2 - 1)) $3 $4\n> +\t\tdone\n> +\tfi\n> +\treturn 0\n> +}\n> +\n> +fill_index () {\n> +\tmake_paths $1 $2 $3 $4 |\n> +\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n> +\tgit update-index --index-info\n> +\treturn 0\n> +}\n\nMakes sense.\n\n> +\n> +br_work1=xxx_work1_xxx\n> +\n> +new_dir=xxx_dir_xxx\n> +\n> +## (5, 10, 9) will create 999,999 files.\n> +## (4, 10, 9) will create  99,999 files.\n> +depth=5\n> +width=10\n> +files=9\n> +\n> +export br_work1\n> +\n> +export new_dir\n> +\n> +export depth\n> +export width\n> +export files\n\nWhy are these exported?  test_expect_success code (unlike test_per\ncode) runs in the same shell as outside, so it doesn't seem necessary.\n\n> +\n> +## Inflate the index with thousands of empty files and commit it.\n> +test_expect_success 'inflate the index' '\n> +\tgit reset --hard &&\n\nWhat does this line do?\n\n> +\tgit branch $br_work1 &&\n> +\tgit checkout $br_work1 &&\n\nIs it useful for these parameters to exist in the test script?  I'd\nfind this easier to read if it named the branch explicitly.  For\nexample:\n\n\ttest_expect_success 'set up large index' '\n\t\tgit checkout -B million &&\n\t\t# (4, 10, 9) would create 99,999 files.\n\t\t# (5, 10, 9) creates 999,999 files.\n\t\tfill_index dir 5 10 9 &&\n\t\tgit commit -m \"large commit\"\n\t'\n\n> +\tfill_index $new_dir $depth $width $files &&\n> +\tgit commit -m $br_work1 &&\n> +\tgit reset --hard\n\nWhat does this line do?\n\n> +'\n> +\n> +## The number of files in the xxx_work1_xxx branch.\n> +nr_work1=$(git ls-files | wc -l)\n> +export nr_work1\n> +\n> +test_perf \"read-tree status work1 ($nr_work1)\" '\n> +\tgit read-tree HEAD &&\n> +\tgit status\n> +'\n\nLooks reasonable.\n\nThanks and hope that helps,\nJonathan\n"},{"id":"316272","messageId":"db545f25-b0a7-2359-e6f5-7a89860c4022@jeffhostetler.com","threadId":"45610","inReplyTo":"20170405213355.GH8741@aiede.mtv.corp.google.com","subject":"Re: [PATCH v1 2/2] p0005-status: time status on very large repo","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T13:26:15Z","receivedAt":"2017-04-06T13:26:23Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/5/2017 5:33 PM, Jonathan Nieder wrote:\n> Hi,\n>\n> git@jeffhostetler.com wrote:\n>\n>> +++ b/t/perf/p0005-status.sh\n>> @@ -0,0 +1,70 @@\n>> +#!/bin/sh\n>> +\n>> +test_description=\"Tests performance of read-tree\"\n>> +\n>> +. ./perf-lib.sh\n>> +\n>> +test_perf_default_repo\n>> +test_checkout_worktree\n>> +\n>> +## usage: dir depth width files\n>> +make_paths () {\n>> +\tfor f in $(seq $4)\n>> +\tdo\n>> +\t\techo $1/file$f\n>> +\tdone;\n>> +\tif test $2 -gt 0;\n>> +\tthen\n>> +\t\tfor w in $(seq $3)\n>> +\t\tdo\n>> +\t\t\tmake_paths $1/dir$w $(($2 - 1)) $3 $4\n>> +\t\tdone\n>> +\tfi\n>> +\treturn 0\n>> +}\n>> +\n>> +fill_index () {\n>> +\tmake_paths $1 $2 $3 $4 |\n>> +\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n>> +\tgit update-index --index-info\n>> +\treturn 0\n>> +}\n>\n> Makes sense.\n>\n>> +\n>> +br_work1=xxx_work1_xxx\n>> +\n>> +new_dir=xxx_dir_xxx\n>> +\n>> +## (5, 10, 9) will create 999,999 files.\n>> +## (4, 10, 9) will create  99,999 files.\n>> +depth=5\n>> +width=10\n>> +files=9\n>> +\n>> +export br_work1\n>> +\n>> +export new_dir\n>> +\n>> +export depth\n>> +export width\n>> +export files\n>\n> Why are these exported?  test_expect_success code (unlike test_per\n> code) runs in the same shell as outside, so it doesn't seem necessary.\n\nI'm still trying to grok all of the shell wizardry hidden\nin the test_* functions, so some may be novice mistakes here.\nHowever, I couldn't get some of the steps to run in an earlier\ndraft of it without them.  But I copied this from p0004-read-tree\nthat I posted in an earlier patch and this version is much simpler\nso they may not be necessary here.  I'll double check.\n\n>\n>> +\n>> +## Inflate the index with thousands of empty files and commit it.\n>> +test_expect_success 'inflate the index' '\n>> +\tgit reset --hard &&\n>\n> What does this line do?\n\nI used update-index to add 1M files and commit it instead of\ncreating the actual files.  This step causes git to do a full\ncheckout to populate those 1M files.  The reset --hard is\nfaster than doing \"git checkout HEAD\".\n\n>\n>> +\tgit branch $br_work1 &&\n>> +\tgit checkout $br_work1 &&\n>\n> Is it useful for these parameters to exist in the test script?  I'd\n> find this easier to read if it named the branch explicitly.  For\n> example:\n>\n> \ttest_expect_success 'set up large index' '\n> \t\tgit checkout -B million &&\n> \t\t# (4, 10, 9) would create 99,999 files.\n> \t\t# (5, 10, 9) creates 999,999 files.\n> \t\tfill_index dir 5 10 9 &&\n> \t\tgit commit -m \"large commit\"\n> \t'\n\nI got burned when playing with p3400-rebase.sh where\nit uses fixed name branches with somewhat common names\nsuch as \"upstream\".\n\nAnd since the test script copies $GIT_BUILD_DIR repo\ninto the trash-directory.* (which the user can override)\nwe run the risk of also colliding with \"dir\" or other\nsuch common-ish names.\n\nSo I created the variables and gave them unlikely values\nand used them as placeholders in the actual test.  If the\nuser has a collision, they can change the variable's\ninitialization in one place and not have to guess what\nthe usage is in the rest of the script.  (Especially\nsince the trend here is for the receiving function to\njust use $1 and $2 type arguments.)\n\n>\n>> +'\n>> +\n>> +## The number of files in the xxx_work1_xxx branch.\n>> +nr_work1=$(git ls-files | wc -l)\n>> +export nr_work1\n>> +\n>> +test_perf \"read-tree status work1 ($nr_work1)\" '\n>> +\tgit read-tree HEAD &&\n>> +\tgit status\n>> +'\n>\n> Looks reasonable.\n>\n> Thanks and hope that helps,\n> Jonathan\n>\n\nI'll send out a cleaned up version (and fix the grammar\nthing in the commit message).\nThanks\nJeff\n"},{"id":"316316","messageId":"20170407042955.i63i6prc3rwi4i6s@sigill.intra.peff.net","threadId":"45610","inReplyTo":"db545f25-b0a7-2359-e6f5-7a89860c4022@jeffhostetler.com","subject":"Re: [PATCH v1 2/2] p0005-status: time status on very large repo","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-07T04:29:56Z","receivedAt":"2017-04-07T04:30:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 06, 2017 at 09:26:15AM -0400, Jeff Hostetler wrote:\n\n> > > +export depth\n> > > +export width\n> > > +export files\n> > \n> > Why are these exported?  test_expect_success code (unlike test_per\n> > code) runs in the same shell as outside, so it doesn't seem necessary.\n> \n> I'm still trying to grok all of the shell wizardry hidden\n> in the test_* functions, so some may be novice mistakes here.\n> However, I couldn't get some of the steps to run in an earlier\n> draft of it without them.  But I copied this from p0004-read-tree\n> that I posted in an earlier patch and this version is much simpler\n> so they may not be necessary here.  I'll double check.\n\nIt's a subtle but annoying difference between the regular tests and the\nperf tests. test_perf() runs in a subshell because of the way the timing\nis implemented. There are a few pointers in t/perf/README regarding\nthis.\n\n-Peff\n"}]}