threads / patch / 45610

patch, 2 partsstring-list: use ALLOC_GROW macro when reallocing string_list

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

## tl;dr

10 messages between Apr 5, 2017 and Apr 7, 2017. Diffs are folded; open one to read it.

replies: 9people: 4as markdown or json

git@jeffhostetler.com· Apr 5, 2017, 19:55 UTC · lore

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

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
git@jeffhostetler.com· Apr 5, 2017, 19:55 UTC · re: git@jeffhostetler.com · lore
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(-)
Show changes to string-list.c +2 −4
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
Stefan Beller· Apr 5, 2017, 20:00 UTC · re: git@jeffhostetler.com · lore

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

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

Jeff King· Apr 5, 2017, 20:09 UTC · re: git@jeffhostetler.com · lore

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

On Wed, Apr 05, 2017 at 07:55:59PM +0000, git@jeffhostetler.com wrote:
Show 12 quoted lines
> 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
Jeff Hostetler· Apr 5, 2017, 21:12 UTC · re: Jeff King · lore

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

On 4/5/2017 4:09 PM, Jeff King wrote:
Show 18 quoted lines
> 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.

Show 9 quoted lines
>
> 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
>
Jonathan Nieder· Apr 5, 2017, 21:26 UTC · re: git@jeffhostetler.com · lore

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

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.

Show 19 quoted lines
> 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.
git@jeffhostetler.com· Apr 5, 2017, 19:56 UTC · re: git@jeffhostetler.com · lore

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

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
Show changes to t/perf/p0005-status.sh +70 −0
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
Jonathan Nieder· Apr 5, 2017, 21:33 UTC · re: git@jeffhostetler.com · lore

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

Hi,
git@jeffhostetler.com wrote:
Show 33 quoted lines
> +++ 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.
Show 18 quoted lines
> +
> +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?
Show 10 quoted lines
> +'
> +
> +## 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

Jeff Hostetler· Apr 6, 2017, 13:26 UTC · re: Jonathan Nieder · lore

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

On 4/5/2017 5:33 PM, Jonathan Nieder wrote:
Show 61 quoted lines
> 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.

Show 7 quoted lines
>
>> +
>> +## 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".

Show 15 quoted lines
>
>> +	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.)

Show 17 quoted lines
>
>> +'
>> +
>> +## 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

Jeff King· Apr 7, 2017, 04:29 UTC · re: Jeff Hostetler · lore

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

On Thu, Apr 06, 2017 at 09:26:15AM -0400, Jeff Hostetler wrote:
Show 13 quoted lines
> > > +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

← back to recent threads