* [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 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 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 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).