threads / patch / 45611

v2, 2 partsstring-list: use ALLOC_GROW macro when reallocing

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

## tl;dr

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

replies: 3people: 2as markdown or json

git@jeffhostetler.com· Apr 5, 2017, 21:09 UTC · lore

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

-- 
2.9.3

git@jeffhostetler.com· Apr 5, 2017, 21:09 UTC · re: git@jeffhostetler.com · lore

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

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 | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

Show changes to string-list.c +1 −4

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

Jonathan Nieder· Apr 5, 2017, 21:35 UTC · re: git@jeffhostetler.com · lore

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

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

nit: s/was/is/ (see comments on v1)

> reallocing the wt_status.changes array.

[...]

> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
> ---
>  string-list.c | 5 +----
>  1 file changed, 1 insertion(+), 4 deletions(-)

With or without that wording tweak,
Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>

git@jeffhostetler.com· Apr 5, 2017, 21:09 UTC · re: git@jeffhostetler.com · lore

[PATCH v2 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