* [PATCH v3 0/2] string-list: use ALLOC_GROW macro when reallocing @ 2017-04-06 13:45 git 2017-04-06 13:45 ` [PATCH v3 1/2] string-list: use ALLOC_GROW macro when reallocing string_list git 2017-04-06 13:45 ` [PATCH v3 2/2] p0005-status: time status on very large repo git 0 siblings, 2 replies; 6+ messages in thread From: git @ 2017-04-06 13:45 UTC (permalink / raw) To: git; +Cc: gitster, peff, Jeff Hostetler From: Jeff Hostetler <jeffhost@microsoft.com> Version 3 eliminates unnecessary exports from p0005 perf test (and fixes the mode bits). ================ Use ALLOC_GROW() macro when reallocating a string_list array rather than simply increasing it by 32. This helps performance of status on very large repos on Windows. Jeff Hostetler (2): string-list: use ALLOC_GROW macro when reallocing string_list p0005-status: time status on very large repo string-list.c | 5 +---- t/perf/p0005-status.sh | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 62 insertions(+), 4 deletions(-) create mode 100755 t/perf/p0005-status.sh -- 2.9.3 ^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH v3 1/2] string-list: use ALLOC_GROW macro when reallocing string_list 2017-04-06 13:45 [PATCH v3 0/2] string-list: use ALLOC_GROW macro when reallocing git @ 2017-04-06 13:45 ` git 2017-04-06 13:45 ` [PATCH v3 2/2] p0005-status: time status on very large repo git 1 sibling, 0 replies; 6+ messages in thread From: git @ 2017-04-06 13:45 UTC (permalink / raw) To: git; +Cc: gitster, peff, Jeff Hostetler From: Jeff Hostetler <jeffhost@microsoft.com> Use ALLOC_GROW() macro when reallocing a string_list array rather than simply increasing it by 32. This is a performance optimization. During status on a very large repo and there are many changes, a significant percentage of the total run time is spent reallocing the wt_status.changes array. This change decreases the time in wt_status_collect_changes_worktree() from 125 seconds to 45 seconds on my very large repository. Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> --- string-list.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) diff --git a/string-list.c b/string-list.c index 45016ad..003ca18 100644 --- a/string-list.c +++ b/string-list.c @@ -41,10 +41,7 @@ static int add_entry(int insert_at, struct string_list *list, const char *string if (exact_match) return -1 - index; - if (list->nr + 1 >= list->alloc) { - list->alloc += 32; - REALLOC_ARRAY(list->items, list->alloc); - } + ALLOC_GROW(list->items, list->nr+1, list->alloc); if (index < list->nr) memmove(list->items + index + 1, list->items + index, (list->nr - index) -- 2.9.3 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH v3 2/2] p0005-status: time status on very large repo 2017-04-06 13:45 [PATCH v3 0/2] string-list: use ALLOC_GROW macro when reallocing git 2017-04-06 13:45 ` [PATCH v3 1/2] string-list: use ALLOC_GROW macro when reallocing string_list git @ 2017-04-06 13:45 ` git 2017-04-06 22:14 ` Thomas Gummerer 1 sibling, 1 reply; 6+ messages in thread From: git @ 2017-04-06 13:45 UTC (permalink / raw) To: git; +Cc: gitster, peff, Jeff Hostetler From: Jeff Hostetler <jeffhost@microsoft.com> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> --- t/perf/p0005-status.sh | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 61 insertions(+) create mode 100755 t/perf/p0005-status.sh diff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh new file mode 100755 index 0000000..704cebc --- /dev/null +++ b/t/perf/p0005-status.sh @@ -0,0 +1,61 @@ +#!/bin/sh + +test_description="Tests performance of read-tree" + +. ./perf-lib.sh + +test_perf_default_repo +test_checkout_worktree + +## usage: dir depth width files +make_paths () { + for f in $(seq $4) + do + echo $1/file$f + done; + if test $2 -gt 0; + then + for w in $(seq $3) + do + make_paths $1/dir$w $(($2 - 1)) $3 $4 + done + fi + return 0 +} + +fill_index () { + make_paths $1 $2 $3 $4 | + sed "s/^/100644 $EMPTY_BLOB /" | + git update-index --index-info + return 0 +} + +br_work1=xxx_work1_xxx +dir_new=xxx_dir_xxx + +## (5, 10, 9) will create 999,999 files. +## (4, 10, 9) will create 99,999 files. +depth=5 +width=10 +files=9 + +## Inflate the index with thousands of empty files and commit it. +## Use reset to actually populate the worktree. +test_expect_success 'inflate the index' ' + git reset --hard && + git branch $br_work1 && + git checkout $br_work1 && + fill_index $dir_new $depth $width $files && + git commit -m $br_work1 && + git reset --hard +' + +## The number of files in the branch. +nr_work1=$(git ls-files | wc -l) + +test_perf "read-tree status work1 ($nr_work1)" ' + git read-tree HEAD && + git status +' + +test_done -- 2.9.3 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH v3 2/2] p0005-status: time status on very large repo 2017-04-06 13:45 ` [PATCH v3 2/2] p0005-status: time status on very large repo git @ 2017-04-06 22:14 ` Thomas Gummerer 2017-04-06 20:58 ` Jeff Hostetler 0 siblings, 1 reply; 6+ messages in thread From: Thomas Gummerer @ 2017-04-06 22:14 UTC (permalink / raw) To: git; +Cc: git, gitster, peff, Jeff Hostetler On 04/06, git@jeffhostetler.com wrote: > From: Jeff Hostetler <jeffhost@microsoft.com> > > Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> > --- > t/perf/p0005-status.sh | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 61 insertions(+) > create mode 100755 t/perf/p0005-status.sh > > diff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh > new file mode 100755 > index 0000000..704cebc > --- /dev/null > +++ b/t/perf/p0005-status.sh > @@ -0,0 +1,61 @@ > +#!/bin/sh > + > +test_description="Tests performance of read-tree" > + > +. ./perf-lib.sh > + > +test_perf_default_repo > +test_checkout_worktree > + > +## usage: dir depth width files > +make_paths () { > + for f in $(seq $4) > + do > + echo $1/file$f > + done; > + if test $2 -gt 0; > + then > + for w in $(seq $3) > + do > + make_paths $1/dir$w $(($2 - 1)) $3 $4 > + done > + fi > + return 0 > +} > + > +fill_index () { > + make_paths $1 $2 $3 $4 | > + sed "s/^/100644 $EMPTY_BLOB /" | > + git update-index --index-info > + return 0 > +} > + > +br_work1=xxx_work1_xxx > +dir_new=xxx_dir_xxx > + > +## (5, 10, 9) will create 999,999 files. > +## (4, 10, 9) will create 99,999 files. > +depth=5 > +width=10 > +files=9 > + > +## Inflate the index with thousands of empty files and commit it. > +## Use reset to actually populate the worktree. > +test_expect_success 'inflate the index' ' > + git reset --hard && > + git branch $br_work1 && > + git checkout $br_work1 && > + fill_index $dir_new $depth $width $files && > + git commit -m $br_work1 && > + git reset --hard > +' > + > +## The number of files in the branch. > +nr_work1=$(git ls-files | wc -l) The above seems to be repeated (or at least very similar to what you have in your other series [1]. Especially in this perf test wouldn't it be better just use test_perf_large_repo, and let whoever runs the test decide what constitutes a large repository for them? The other advantage of that would be that it is more of a real-world scenario, instead of a synthetic distribution of the files, which would give us some better results I think. Is there anything I'm missing that would make using test_perf_large_repo not a good option here? [1]: http://public-inbox.org/git/20170406163442.36463-3-git@jeffhostetler.com/ > +test_perf "read-tree status work1 ($nr_work1)" ' > + git read-tree HEAD && > + git status > +' > + > +test_done > -- > 2.9.3 > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v3 2/2] p0005-status: time status on very large repo 2017-04-06 22:14 ` Thomas Gummerer @ 2017-04-06 20:58 ` Jeff Hostetler 2017-04-06 23:26 ` Thomas Gummerer 0 siblings, 1 reply; 6+ messages in thread From: Jeff Hostetler @ 2017-04-06 20:58 UTC (permalink / raw) To: Thomas Gummerer; +Cc: git, gitster, peff, Jeff Hostetler On 4/6/2017 6:14 PM, Thomas Gummerer wrote: > On 04/06, git@jeffhostetler.com wrote: >> From: Jeff Hostetler <jeffhost@microsoft.com> >> >> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> >> --- >> t/perf/p0005-status.sh | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++ >> 1 file changed, 61 insertions(+) >> create mode 100755 t/perf/p0005-status.sh >> >> diff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh >> new file mode 100755 >> index 0000000..704cebc >> --- /dev/null >> +++ b/t/perf/p0005-status.sh >> @@ -0,0 +1,61 @@ >> +#!/bin/sh >> + >> +test_description="Tests performance of read-tree" >> + >> +. ./perf-lib.sh >> + >> +test_perf_default_repo >> +test_checkout_worktree >> + >> +## usage: dir depth width files >> +make_paths () { >> + for f in $(seq $4) >> + do >> + echo $1/file$f >> + done; >> + if test $2 -gt 0; >> + then >> + for w in $(seq $3) >> + do >> + make_paths $1/dir$w $(($2 - 1)) $3 $4 >> + done >> + fi >> + return 0 >> +} >> + >> +fill_index () { >> + make_paths $1 $2 $3 $4 | >> + sed "s/^/100644 $EMPTY_BLOB /" | >> + git update-index --index-info >> + return 0 >> +} >> + >> +br_work1=xxx_work1_xxx >> +dir_new=xxx_dir_xxx >> + >> +## (5, 10, 9) will create 999,999 files. >> +## (4, 10, 9) will create 99,999 files. >> +depth=5 >> +width=10 >> +files=9 >> + >> +## Inflate the index with thousands of empty files and commit it. >> +## Use reset to actually populate the worktree. >> +test_expect_success 'inflate the index' ' >> + git reset --hard && >> + git branch $br_work1 && >> + git checkout $br_work1 && >> + fill_index $dir_new $depth $width $files && >> + git commit -m $br_work1 && >> + git reset --hard >> +' >> + >> +## The number of files in the branch. >> +nr_work1=$(git ls-files | wc -l) > > The above seems to be repeated (or at least very similar to what you > have in your other series [1]. Especially in this perf test wouldn't > it be better just use test_perf_large_repo, and let whoever runs the > test decide what constitutes a large repository for them? > > The other advantage of that would be that it is more of a real-world > scenario, instead of a synthetic distribution of the files, which > would give us some better results I think. > > Is there anything I'm missing that would make using > test_perf_large_repo not a good option here? Yes, it is copied from the other series. I make the same change that Rene just suggested on it to use awk to create the list. I did this because I need very large repos. From what I can tell the common usage is to set test_perf_large_repo to linux.git, but that only has 58K files. And it defaults to git.git which only has 3K files. Internally, I test against the Windows source tree with 3.1M files, but I can't share that :-) So I created this test to generate artificial, but large and reproducible repos for evaluation. I could change the default depth to 4 (giving a 100K tree), but I'm really interested in 1M+ repos. For small-ish values of n the difference between O(n) and O(n log n) operations can hide in system and I/O noise; not so for very large n.... > > [1]: http://public-inbox.org/git/20170406163442.36463-3-git@jeffhostetler.com/ > >> +test_perf "read-tree status work1 ($nr_work1)" ' >> + git read-tree HEAD && >> + git status >> +' >> + >> +test_done >> -- >> 2.9.3 >> ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v3 2/2] p0005-status: time status on very large repo 2017-04-06 20:58 ` Jeff Hostetler @ 2017-04-06 23:26 ` Thomas Gummerer 0 siblings, 0 replies; 6+ messages in thread From: Thomas Gummerer @ 2017-04-06 23:26 UTC (permalink / raw) To: Jeff Hostetler; +Cc: git, gitster, peff, Jeff Hostetler On 04/06, Jeff Hostetler wrote: > > > On 4/6/2017 6:14 PM, Thomas Gummerer wrote: > >On 04/06, git@jeffhostetler.com wrote: > >>From: Jeff Hostetler <jeffhost@microsoft.com> > >> > >>Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> > >>--- > >> t/perf/p0005-status.sh | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++ > >> 1 file changed, 61 insertions(+) > >> create mode 100755 t/perf/p0005-status.sh > >> > >>diff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh > >>new file mode 100755 > >>index 0000000..704cebc > >>--- /dev/null > >>+++ b/t/perf/p0005-status.sh > >>@@ -0,0 +1,61 @@ > >>+#!/bin/sh > >>+ > >>+test_description="Tests performance of read-tree" > >>+ > >>+. ./perf-lib.sh > >>+ > >>+test_perf_default_repo > >>+test_checkout_worktree > >>+ > >>+## usage: dir depth width files > >>+make_paths () { > >>+ for f in $(seq $4) > >>+ do > >>+ echo $1/file$f > >>+ done; > >>+ if test $2 -gt 0; > >>+ then > >>+ for w in $(seq $3) > >>+ do > >>+ make_paths $1/dir$w $(($2 - 1)) $3 $4 > >>+ done > >>+ fi > >>+ return 0 > >>+} > >>+ > >>+fill_index () { > >>+ make_paths $1 $2 $3 $4 | > >>+ sed "s/^/100644 $EMPTY_BLOB /" | > >>+ git update-index --index-info > >>+ return 0 > >>+} > >>+ > >>+br_work1=xxx_work1_xxx > >>+dir_new=xxx_dir_xxx > >>+ > >>+## (5, 10, 9) will create 999,999 files. > >>+## (4, 10, 9) will create 99,999 files. > >>+depth=5 > >>+width=10 > >>+files=9 > >>+ > >>+## Inflate the index with thousands of empty files and commit it. > >>+## Use reset to actually populate the worktree. > >>+test_expect_success 'inflate the index' ' > >>+ git reset --hard && > >>+ git branch $br_work1 && > >>+ git checkout $br_work1 && > >>+ fill_index $dir_new $depth $width $files && > >>+ git commit -m $br_work1 && > >>+ git reset --hard > >>+' > >>+ > >>+## The number of files in the branch. > >>+nr_work1=$(git ls-files | wc -l) > > > >The above seems to be repeated (or at least very similar to what you > >have in your other series [1]. Especially in this perf test wouldn't > >it be better just use test_perf_large_repo, and let whoever runs the > >test decide what constitutes a large repository for them? > > > >The other advantage of that would be that it is more of a real-world > >scenario, instead of a synthetic distribution of the files, which > >would give us some better results I think. > > > >Is there anything I'm missing that would make using > >test_perf_large_repo not a good option here? > > Yes, it is copied from the other series. I make the same change > that Rene just suggested on it to use awk to create the list. > > I did this because I need very large repos. From what I can tell > the common usage is to set test_perf_large_repo to linux.git, but > that only has 58K files. And it defaults to git.git which only > has 3K files. Yeah true. Back when I worked on "index v5" for my GSoC project, I used to use the webkit repository, which at the time had 300-something K files. Nowadays the better test might be the chromium repository, but I'm not sure (cloning that takes a while on my connection :) ). > Internally, I test against the Windows source tree with 3.1M files, > but I can't share that :-) Heh. I'd love to see the performance numbers for that though! > So I created this test to generate artificial, but large and > reproducible repos for evaluation. > > I could change the default depth to 4 (giving a 100K tree), but > I'm really interested in 1M+ repos. For small-ish values of n > the difference between O(n) and O(n log n) operations can hide > in system and I/O noise; not so for very large n.... Makes sense to me. Thanks for the explanation! > > > >[1]: http://public-inbox.org/git/20170406163442.36463-3-git@jeffhostetler.com/ > > > >>+test_perf "read-tree status work1 ($nr_work1)" ' > >>+ git read-tree HEAD && > >>+ git status > >>+' > >>+ > >>+test_done > >>-- > >>2.9.3 > >> ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2017-04-06 21:20 UTC | newest] Thread overview: 6+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2017-04-06 13:45 [PATCH v3 0/2] string-list: use ALLOC_GROW macro when reallocing git 2017-04-06 13:45 ` [PATCH v3 1/2] string-list: use ALLOC_GROW macro when reallocing string_list git 2017-04-06 13:45 ` [PATCH v3 2/2] p0005-status: time status on very large repo git 2017-04-06 22:14 ` Thomas Gummerer 2017-04-06 20:58 ` Jeff Hostetler 2017-04-06 23:26 ` Thomas Gummerer
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).