{"thread":{"id":"45619","subject":"[PATCH v3 0/2] string-list: use ALLOC_GROW macro when reallocing","startedAt":"2017-04-06T13:45:22Z","lastAt":"2017-04-06T21:20:21Z","messageCount":6,"participants":["git@jeffhostetler.com","Thomas Gummerer","Jeff Hostetler"],"isPatch":true,"patchVersion":3,"patchTotal":2},"messages":[{"id":"316273","messageId":"20170406134508.31711-1-git@jeffhostetler.com","threadId":"45619","inReplyTo":null,"subject":"[PATCH v3 0/2] string-list: use ALLOC_GROW macro when reallocing","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T13:45:06Z","receivedAt":"2017-04-06T13:45:22Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nVersion 3 eliminates unnecessary exports from p0005 perf test\n(and fixes the mode bits).\n\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          |  5 +----\n t/perf/p0005-status.sh | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 62 insertions(+), 4 deletions(-)\n create mode 100755 t/perf/p0005-status.sh\n\n-- \n2.9.3\n\n"},{"id":"316274","messageId":"20170406134508.31711-3-git@jeffhostetler.com","threadId":"45619","inReplyTo":"20170406134508.31711-1-git@jeffhostetler.com","subject":"[PATCH v3 2/2] p0005-status: time status on very large repo","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T13:45:08Z","receivedAt":"2017-04-06T13:45:25Z","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 | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 61 insertions(+)\n create mode 100755 t/perf/p0005-status.sh\n\ndiff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh\nnew file mode 100755\nindex 0000000..704cebc\n--- /dev/null\n+++ b/t/perf/p0005-status.sh\n@@ -0,0 +1,61 @@\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+dir_new=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+## Inflate the index with thousands of empty files and commit it.\n+## Use reset to actually populate the worktree.\n+test_expect_success 'inflate the index' '\n+\tgit reset --hard &&\n+\tgit branch $br_work1 &&\n+\tgit checkout $br_work1 &&\n+\tfill_index $dir_new $depth $width $files &&\n+\tgit commit -m $br_work1 &&\n+\tgit reset --hard\n+'\n+\n+## The number of files in the branch.\n+nr_work1=$(git ls-files | wc -l)\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":"316275","messageId":"20170406134508.31711-2-git@jeffhostetler.com","threadId":"45619","inReplyTo":"20170406134508.31711-1-git@jeffhostetler.com","subject":"[PATCH v3 1/2] string-list: use ALLOC_GROW macro when reallocing string_list","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T13:45:07Z","receivedAt":"2017-04-06T13:45:26Z","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 is spent\nreallocing the wt_status.changes array.\n\nThis change decreases 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 | 5 +----\n 1 file changed, 1 insertion(+), 4 deletions(-)\n\ndiff --git a/string-list.c b/string-list.c\nindex 45016ad..003ca18 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -41,10 +41,7 @@ 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+\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":"316298","messageId":"20170406221453.GA32223@hank","threadId":"45619","inReplyTo":"20170406134508.31711-3-git@jeffhostetler.com","subject":"Re: [PATCH v3 2/2] p0005-status: time status on very large repo","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2017-04-06T22:14:53Z","receivedAt":"2017-04-06T20:08:38Z","isPatch":true,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 04/06, git@jeffhostetler.com wrote:\n> From: Jeff Hostetler <jeffhost@microsoft.com>\n> \n> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n> ---\n>  t/perf/p0005-status.sh | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++\n>  1 file changed, 61 insertions(+)\n>  create mode 100755 t/perf/p0005-status.sh\n> \n> diff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh\n> new file mode 100755\n> index 0000000..704cebc\n> --- /dev/null\n> +++ b/t/perf/p0005-status.sh\n> @@ -0,0 +1,61 @@\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> +dir_new=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> +## Inflate the index with thousands of empty files and commit it.\n> +## Use reset to actually populate the worktree.\n> +test_expect_success 'inflate the index' '\n> +\tgit reset --hard &&\n> +\tgit branch $br_work1 &&\n> +\tgit checkout $br_work1 &&\n> +\tfill_index $dir_new $depth $width $files &&\n> +\tgit commit -m $br_work1 &&\n> +\tgit reset --hard\n> +'\n> +\n> +## The number of files in the branch.\n> +nr_work1=$(git ls-files | wc -l)\n\nThe above seems to be repeated (or at least very similar to what you\nhave in your other series [1].  Especially in this perf test wouldn't\nit be better just use test_perf_large_repo, and let whoever runs the\ntest decide what constitutes a large repository for them?\n\nThe other advantage of that would be that it is more of a real-world\nscenario, instead of a synthetic distribution of the files, which\nwould give us some better results I think.\n\nIs there anything I'm missing that would make using\ntest_perf_large_repo not a good option here?\n\n[1]: http://public-inbox.org/git/20170406163442.36463-3-git@jeffhostetler.com/\n\n> +test_perf \"read-tree status work1 ($nr_work1)\" '\n> +\tgit read-tree HEAD &&\n> +\tgit status\n> +'\n> +\n> +test_done\n> -- \n> 2.9.3\n> \n"},{"id":"316310","messageId":"590f6863-801b-58e9-3700-962168f8315e@jeffhostetler.com","threadId":"45619","inReplyTo":"20170406221453.GA32223@hank","subject":"Re: [PATCH v3 2/2] p0005-status: time status on very large repo","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T20:58:21Z","receivedAt":"2017-04-06T20:58:35Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/6/2017 6:14 PM, Thomas Gummerer wrote:\n> On 04/06, git@jeffhostetler.com wrote:\n>> From: Jeff Hostetler <jeffhost@microsoft.com>\n>>\n>> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n>> ---\n>>  t/perf/p0005-status.sh | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++\n>>  1 file changed, 61 insertions(+)\n>>  create mode 100755 t/perf/p0005-status.sh\n>>\n>> diff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh\n>> new file mode 100755\n>> index 0000000..704cebc\n>> --- /dev/null\n>> +++ b/t/perf/p0005-status.sh\n>> @@ -0,0 +1,61 @@\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>> +dir_new=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>> +## Inflate the index with thousands of empty files and commit it.\n>> +## Use reset to actually populate the worktree.\n>> +test_expect_success 'inflate the index' '\n>> +\tgit reset --hard &&\n>> +\tgit branch $br_work1 &&\n>> +\tgit checkout $br_work1 &&\n>> +\tfill_index $dir_new $depth $width $files &&\n>> +\tgit commit -m $br_work1 &&\n>> +\tgit reset --hard\n>> +'\n>> +\n>> +## The number of files in the branch.\n>> +nr_work1=$(git ls-files | wc -l)\n>\n> The above seems to be repeated (or at least very similar to what you\n> have in your other series [1].  Especially in this perf test wouldn't\n> it be better just use test_perf_large_repo, and let whoever runs the\n> test decide what constitutes a large repository for them?\n>\n> The other advantage of that would be that it is more of a real-world\n> scenario, instead of a synthetic distribution of the files, which\n> would give us some better results I think.\n>\n> Is there anything I'm missing that would make using\n> test_perf_large_repo not a good option here?\n\nYes, it is copied from the other series.  I make the same change\nthat Rene just suggested on it to use awk to create the list.\n\nI did this because I need very large repos.  From what I can tell\nthe common usage is to set test_perf_large_repo to linux.git, but\nthat only has 58K files.  And it defaults to git.git which only\nhas 3K files.\n\nInternally, I test against the Windows source tree with 3.1M files,\nbut I can't share that :-)\n\nSo I created this test to generate artificial, but large and\nreproducible repos for evaluation.\n\nI could change the default depth to 4 (giving a 100K tree), but\nI'm really interested in 1M+ repos.  For small-ish values of n\nthe difference between O(n) and O(n log n) operations can hide\nin system and I/O noise; not so for very large n....\n\n>\n> [1]: http://public-inbox.org/git/20170406163442.36463-3-git@jeffhostetler.com/\n>\n>> +test_perf \"read-tree status work1 ($nr_work1)\" '\n>> +\tgit read-tree HEAD &&\n>> +\tgit status\n>> +'\n>> +\n>> +test_done\n>> --\n>> 2.9.3\n>>\n"},{"id":"316311","messageId":"20170406232634.GB32223@hank","threadId":"45619","inReplyTo":"590f6863-801b-58e9-3700-962168f8315e@jeffhostetler.com","subject":"Re: [PATCH v3 2/2] p0005-status: time status on very large repo","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2017-04-06T23:26:39Z","receivedAt":"2017-04-06T21:20:21Z","isPatch":true,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 04/06, Jeff Hostetler wrote:\n> \n> \n> On 4/6/2017 6:14 PM, Thomas Gummerer wrote:\n> >On 04/06, git@jeffhostetler.com wrote:\n> >>From: Jeff Hostetler <jeffhost@microsoft.com>\n> >>\n> >>Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n> >>---\n> >> t/perf/p0005-status.sh | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++\n> >> 1 file changed, 61 insertions(+)\n> >> create mode 100755 t/perf/p0005-status.sh\n> >>\n> >>diff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh\n> >>new file mode 100755\n> >>index 0000000..704cebc\n> >>--- /dev/null\n> >>+++ b/t/perf/p0005-status.sh\n> >>@@ -0,0 +1,61 @@\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> >>+dir_new=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> >>+## Inflate the index with thousands of empty files and commit it.\n> >>+## Use reset to actually populate the worktree.\n> >>+test_expect_success 'inflate the index' '\n> >>+\tgit reset --hard &&\n> >>+\tgit branch $br_work1 &&\n> >>+\tgit checkout $br_work1 &&\n> >>+\tfill_index $dir_new $depth $width $files &&\n> >>+\tgit commit -m $br_work1 &&\n> >>+\tgit reset --hard\n> >>+'\n> >>+\n> >>+## The number of files in the branch.\n> >>+nr_work1=$(git ls-files | wc -l)\n> >\n> >The above seems to be repeated (or at least very similar to what you\n> >have in your other series [1].  Especially in this perf test wouldn't\n> >it be better just use test_perf_large_repo, and let whoever runs the\n> >test decide what constitutes a large repository for them?\n> >\n> >The other advantage of that would be that it is more of a real-world\n> >scenario, instead of a synthetic distribution of the files, which\n> >would give us some better results I think.\n> >\n> >Is there anything I'm missing that would make using\n> >test_perf_large_repo not a good option here?\n> \n> Yes, it is copied from the other series.  I make the same change\n> that Rene just suggested on it to use awk to create the list.\n> \n> I did this because I need very large repos.  From what I can tell\n> the common usage is to set test_perf_large_repo to linux.git, but\n> that only has 58K files.  And it defaults to git.git which only\n> has 3K files.\n\nYeah true.  Back when I worked on \"index v5\" for my GSoC project, I\nused to use the webkit repository, which at the time had\n300-something K files.  Nowadays the better test might be the chromium\nrepository, but I'm not sure (cloning that takes a while on my\nconnection :) ).  \n\n> Internally, I test against the Windows source tree with 3.1M files,\n> but I can't share that :-)\n\nHeh.  I'd love to see the performance numbers for that though!\n\n> So I created this test to generate artificial, but large and\n> reproducible repos for evaluation.\n> \n> I could change the default depth to 4 (giving a 100K tree), but\n> I'm really interested in 1M+ repos.  For small-ish values of n\n> the difference between O(n) and O(n log n) operations can hide\n> in system and I/O noise; not so for very large n....\n\nMakes sense to me.  Thanks for the explanation!\n\n> >\n> >[1]: http://public-inbox.org/git/20170406163442.36463-3-git@jeffhostetler.com/\n> >\n> >>+test_perf \"read-tree status work1 ($nr_work1)\" '\n> >>+\tgit read-tree HEAD &&\n> >>+\tgit status\n> >>+'\n> >>+\n> >>+test_done\n> >>--\n> >>2.9.3\n> >>\n"}]}