[PATCH v1 0/2] string-list: use ALLOC_GROW macro when reallocing

[PATCH v1 0/2] string-list: use ALLOC_GROW macro when reallocing

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

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          |  6 ++---
 t/perf/p0005-status.sh | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 72 insertions(+), 4 deletions(-)
 create mode 100644 t/perf/p0005-status.sh

-- 
2.9.3

[PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list

[git]

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 was spent
reallocing the wt_status.changes array.

This change decreased 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 | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/string-list.c b/string-list.c
index 45016ad..cd4c4e0 100644
--- a/string-list.c
+++ b/string-list.c
@@ -41,10 +41,8 @@ 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);
-	}
+	if (list->nr + 1 >= 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

Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list

[Stefan Beller]

On Wed, Apr 5, 2017 at 12:55 PM,  <git@jeffhostetler.com> wrote:
> +       if (list->nr + 1 >= list->alloc)
> +               ALLOC_GROW(list->items, list->nr+1, list->alloc);

No need for the condition here as it is part of the macro as well.

Thanks for spotting this fix!
Stefan

Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list

[Jeff King]

On Wed, Apr 05, 2017 at 07:55:59PM +0000, git@jeffhostetler.com wrote:

> 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 was spent
> reallocing the wt_status.changes array.
> 
> This change decreased the time in wt_status_collect_changes_worktree()
> from 125 seconds to 45 seconds on my very large repository.

Oof. Looks like the original was quadratic. I'm surprised this didn't
bite us more often. I guess we don't usually use string-lists for big
lists.

Aside from the redundant size-check that Stefan pointed out, the patch
looks obviously correct. I grepped for "alloc +=" and "alloc =.*+' to
see if there were any other cases, but didn't find any. Obviously that
is dependent on calling the variable "alloc", but that is normal for us
(and it does turn up a number of cases that do allocate correctly).

-Peff

Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list

[Jeff Hostetler]

On 4/5/2017 4:09 PM, Jeff King wrote:
> On Wed, Apr 05, 2017 at 07:55:59PM +0000, git@jeffhostetler.com wrote:
>
>> 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 was spent
>> reallocing the wt_status.changes array.
>>
>> This change decreased the time in wt_status_collect_changes_worktree()
>> from 125 seconds to 45 seconds on my very large repository.
>
> Oof. Looks like the original was quadratic. I'm surprised this didn't
> bite us more often. I guess we don't usually use string-lists for big
> lists.

To be fair, I was playing with a repo with 3M files
and I think realloc() is more efficient on Linux, so
I'm not surprised that we haven't seen it even with
repos the size of linux.git.

>
> Aside from the redundant size-check that Stefan pointed out, the patch
> looks obviously correct. I grepped for "alloc +=" and "alloc =.*+' to
> see if there were any other cases, but didn't find any. Obviously that
> is dependent on calling the variable "alloc", but that is normal for us
> (and it does turn up a number of cases that do allocate correctly).
>
> -Peff
>

Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list

[Jonathan Nieder]

Hi,

git@jeffhostetler.com wrote:

> During status on a very large repo and there are many changes,
> a significant percentage of the total run time was spent
> reallocing the wt_status.changes array.

Nit: commit messages tend to use the present tense instead of the past
when describing Git's current behavior.  That makes it easier for
readers to tell whether you are describing the present or the distant
past.

> This change decreased the time in wt_status_collect_changes_worktree()
> from 125 seconds to 45 seconds on my very large repository.

Nice.

This is also just the right thing to do.  The linear growth would
produce potentially (potentially because you can be lucky and allocate
in the first place somewhere with a lot of room) quadratic behavior as
realloc copies the allocation to increasingly larger regions.

> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
> ---
>  string-list.c | 6 ++----
>  1 file changed, 2 insertions(+), 4 deletions(-)
>
> diff --git a/string-list.c b/string-list.c
> index 45016ad..cd4c4e0 100644
> --- a/string-list.c
> +++ b/string-list.c
> @@ -41,10 +41,8 @@ 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);
> -	}
> +	if (list->nr + 1 >= list->alloc)
> +		ALLOC_GROW(list->items, list->nr+1, list->alloc);

This checks for >= but ALLOC_GROW only grows when the new size is >.
The new code is less eager about growing than the old was, forcing me
to look at the other code to find the correct invariant.

Fortunately (1) string_list_append_nodup already uses ALLOC_GROW the
way this patch does and (2) REALLOC_ARRAY determines the meaning of
list->alloc.  The >= was just overeager and this is safe.

After removing the unnecessary 'if' as described by Stefan,
Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>

Thanks.

[PATCH v1 2/2] p0005-status: time status on very large repo

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 t/perf/p0005-status.sh | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)
 create mode 100644 t/perf/p0005-status.sh

diff --git a/t/perf/p0005-status.sh b/t/perf/p0005-status.sh
new file mode 100644
index 0000000..4a25ba0
--- /dev/null
+++ b/t/perf/p0005-status.sh
@@ -0,0 +1,70 @@
+#!/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
+
+new_dir=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
+
+export br_work1
+
+export new_dir
+
+export depth
+export width
+export files
+
+## Inflate the index with thousands of empty files and commit it.
+test_expect_success 'inflate the index' '
+	git reset --hard &&
+	git branch $br_work1 &&
+	git checkout $br_work1 &&
+	fill_index $new_dir $depth $width $files &&
+	git commit -m $br_work1 &&
+	git reset --hard
+'
+
+## The number of files in the xxx_work1_xxx branch.
+nr_work1=$(git ls-files | wc -l)
+export nr_work1
+
+test_perf "read-tree status work1 ($nr_work1)" '
+	git read-tree HEAD &&
+	git status
+'
+
+test_done
-- 
2.9.3

Re: [PATCH v1 2/2] p0005-status: time status on very large repo

[Jonathan Nieder]

Hi,

git@jeffhostetler.com wrote:

> +++ b/t/perf/p0005-status.sh
> @@ -0,0 +1,70 @@
> +#!/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
> +}

Makes sense.

> +
> +br_work1=xxx_work1_xxx
> +
> +new_dir=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
> +
> +export br_work1
> +
> +export new_dir
> +
> +export depth
> +export width
> +export files

Why are these exported?  test_expect_success code (unlike test_per
code) runs in the same shell as outside, so it doesn't seem necessary.

> +
> +## Inflate the index with thousands of empty files and commit it.
> +test_expect_success 'inflate the index' '
> +	git reset --hard &&

What does this line do?

> +	git branch $br_work1 &&
> +	git checkout $br_work1 &&

Is it useful for these parameters to exist in the test script?  I'd
find this easier to read if it named the branch explicitly.  For
example:

	test_expect_success 'set up large index' '
		git checkout -B million &&
		# (4, 10, 9) would create 99,999 files.
		# (5, 10, 9) creates 999,999 files.
		fill_index dir 5 10 9 &&
		git commit -m "large commit"
	'

> +	fill_index $new_dir $depth $width $files &&
> +	git commit -m $br_work1 &&
> +	git reset --hard

What does this line do?

> +'
> +
> +## The number of files in the xxx_work1_xxx branch.
> +nr_work1=$(git ls-files | wc -l)
> +export nr_work1
> +
> +test_perf "read-tree status work1 ($nr_work1)" '
> +	git read-tree HEAD &&
> +	git status
> +'

Looks reasonable.

Thanks and hope that helps,
Jonathan

Re: [PATCH v1 2/2] p0005-status: time status on very large repo

[Jeff Hostetler]

On 4/5/2017 5:33 PM, Jonathan Nieder wrote:
> Hi,
>
> git@jeffhostetler.com wrote:
>
>> +++ b/t/perf/p0005-status.sh
>> @@ -0,0 +1,70 @@
>> +#!/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
>> +}
>
> Makes sense.
>
>> +
>> +br_work1=xxx_work1_xxx
>> +
>> +new_dir=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
>> +
>> +export br_work1
>> +
>> +export new_dir
>> +
>> +export depth
>> +export width
>> +export files
>
> Why are these exported?  test_expect_success code (unlike test_per
> code) runs in the same shell as outside, so it doesn't seem necessary.

I'm still trying to grok all of the shell wizardry hidden
in the test_* functions, so some may be novice mistakes here.
However, I couldn't get some of the steps to run in an earlier
draft of it without them.  But I copied this from p0004-read-tree
that I posted in an earlier patch and this version is much simpler
so they may not be necessary here.  I'll double check.

>
>> +
>> +## Inflate the index with thousands of empty files and commit it.
>> +test_expect_success 'inflate the index' '
>> +	git reset --hard &&
>
> What does this line do?

I used update-index to add 1M files and commit it instead of
creating the actual files.  This step causes git to do a full
checkout to populate those 1M files.  The reset --hard is
faster than doing "git checkout HEAD".

>
>> +	git branch $br_work1 &&
>> +	git checkout $br_work1 &&
>
> Is it useful for these parameters to exist in the test script?  I'd
> find this easier to read if it named the branch explicitly.  For
> example:
>
> 	test_expect_success 'set up large index' '
> 		git checkout -B million &&
> 		# (4, 10, 9) would create 99,999 files.
> 		# (5, 10, 9) creates 999,999 files.
> 		fill_index dir 5 10 9 &&
> 		git commit -m "large commit"
> 	'

I got burned when playing with p3400-rebase.sh where
it uses fixed name branches with somewhat common names
such as "upstream".

And since the test script copies $GIT_BUILD_DIR repo
into the trash-directory.* (which the user can override)
we run the risk of also colliding with "dir" or other
such common-ish names.

So I created the variables and gave them unlikely values
and used them as placeholders in the actual test.  If the
user has a collision, they can change the variable's
initialization in one place and not have to guess what
the usage is in the rest of the script.  (Especially
since the trend here is for the receiving function to
just use $1 and $2 type arguments.)

>
>> +'
>> +
>> +## The number of files in the xxx_work1_xxx branch.
>> +nr_work1=$(git ls-files | wc -l)
>> +export nr_work1
>> +
>> +test_perf "read-tree status work1 ($nr_work1)" '
>> +	git read-tree HEAD &&
>> +	git status
>> +'
>
> Looks reasonable.
>
> Thanks and hope that helps,
> Jonathan
>

I'll send out a cleaned up version (and fix the grammar
thing in the commit message).
Thanks
Jeff

Re: [PATCH v1 2/2] p0005-status: time status on very large repo

[Jeff King]

On Thu, Apr 06, 2017 at 09:26:15AM -0400, Jeff Hostetler wrote:

> > > +export depth
> > > +export width
> > > +export files
> > 
> > Why are these exported?  test_expect_success code (unlike test_per
> > code) runs in the same shell as outside, so it doesn't seem necessary.
> 
> I'm still trying to grok all of the shell wizardry hidden
> in the test_* functions, so some may be novice mistakes here.
> However, I couldn't get some of the steps to run in an earlier
> draft of it without them.  But I copied this from p0004-read-tree
> that I posted in an earlier patch and this version is much simpler
> so they may not be necessary here.  I'll double check.

It's a subtle but annoying difference between the regular tests and the
perf tests. test_perf() runs in a subshell because of the way the timing
is implemented. There are a few pointers in t/perf/README regarding
this.

-Peff