[PATCH v7 0/3] read-cache: speed up add_index_entry

[PATCH v7 0/3] read-cache: speed up add_index_entry

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Version 7 addresses size_t and casting issues in strcmp_offset()
and replaces shell test function with an awk expression to make
the perf test run faster.

================
Teach add_index_entry_with_check() and has_dir_name()
to avoid index lookups if the given path sorts after
the last entry in the index.

This saves at least 2 binary searches per entry.

This improves performance during checkout and read-tree because
merge_working_tree() and unpack_trees() processes a list of already
sorted entries.

Jeff Hostetler (3):
  read-cache: add strcmp_offset function
  p0004-read-tree: perf test to time read-tree
  read-cache: speed up add_index_entry during checkout

 Makefile                      |   1 +
 cache.h                       |   1 +
 read-cache.c                  |  66 +++++++++++++++++++++++-
 t/helper/.gitignore           |   1 +
 t/helper/test-strcmp-offset.c |  64 +++++++++++++++++++++++
 t/perf/p0004-read-tree.sh     | 117 ++++++++++++++++++++++++++++++++++++++++++
 t/t0065-strcmp-offset.sh      |  11 ++++
 7 files changed, 259 insertions(+), 2 deletions(-)
 create mode 100644 t/helper/test-strcmp-offset.c
 create mode 100755 t/perf/p0004-read-tree.sh
 create mode 100755 t/t0065-strcmp-offset.sh

-- 
2.9.3

[PATCH v7 1/3] read-cache: add strcmp_offset function

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Add strcmp_offset() function to also return the offset of the
first change.

Add unit test and helper to verify.

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 Makefile                      |  1 +
 cache.h                       |  1 +
 read-cache.c                  | 20 ++++++++++++++
 t/helper/.gitignore           |  1 +
 t/helper/test-strcmp-offset.c | 64 +++++++++++++++++++++++++++++++++++++++++++
 t/t0065-strcmp-offset.sh      | 11 ++++++++
 6 files changed, 98 insertions(+)
 create mode 100644 t/helper/test-strcmp-offset.c
 create mode 100755 t/t0065-strcmp-offset.sh

diff --git a/Makefile b/Makefile
index 9ec6065..4c4c246 100644
--- a/Makefile
+++ b/Makefile
@@ -631,6 +631,7 @@ TEST_PROGRAMS_NEED_X += test-scrap-cache-tree
 TEST_PROGRAMS_NEED_X += test-sha1
 TEST_PROGRAMS_NEED_X += test-sha1-array
 TEST_PROGRAMS_NEED_X += test-sigchain
+TEST_PROGRAMS_NEED_X += test-strcmp-offset
 TEST_PROGRAMS_NEED_X += test-string-list
 TEST_PROGRAMS_NEED_X += test-submodule-config
 TEST_PROGRAMS_NEED_X += test-subprocess
diff --git a/cache.h b/cache.h
index 80b6372..3c55047 100644
--- a/cache.h
+++ b/cache.h
@@ -574,6 +574,7 @@ extern int write_locked_index(struct index_state *, struct lock_file *lock, unsi
 extern int discard_index(struct index_state *);
 extern int unmerged_index(const struct index_state *);
 extern int verify_path(const char *path);
+extern int strcmp_offset(const char *s1, const char *s2, size_t *first_change);
 extern int index_dir_exists(struct index_state *istate, const char *name, int namelen);
 extern void adjust_dirname_case(struct index_state *istate, char *name);
 extern struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int igncase);
diff --git a/read-cache.c b/read-cache.c
index 9054369..97f13a1 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -887,6 +887,26 @@ static int has_file_name(struct index_state *istate,
 	return retval;
 }
 
+
+/*
+ * Like strcmp(), but also return the offset of the first change.
+ * If strings are equal, return the length.
+ */
+int strcmp_offset(const char *s1, const char *s2, size_t *first_change)
+{
+	size_t k;
+
+	if (!first_change)
+		return strcmp(s1, s2);
+
+	for (k = 0; s1[k] == s2[k]; k++)
+		if (s1[k] == '\0')
+			break;
+
+	*first_change = k;
+	return (unsigned char)s1[k] - (unsigned char)s2[k];
+}
+
 /*
  * Do we have another file with a pathname that is a proper
  * subset of the name we're trying to add?
diff --git a/t/helper/.gitignore b/t/helper/.gitignore
index d6e8b36..0a89531 100644
--- a/t/helper/.gitignore
+++ b/t/helper/.gitignore
@@ -25,6 +25,7 @@
 /test-sha1
 /test-sha1-array
 /test-sigchain
+/test-strcmp-offset
 /test-string-list
 /test-submodule-config
 /test-subprocess
diff --git a/t/helper/test-strcmp-offset.c b/t/helper/test-strcmp-offset.c
new file mode 100644
index 0000000..03e1eef
--- /dev/null
+++ b/t/helper/test-strcmp-offset.c
@@ -0,0 +1,64 @@
+#include "cache.h"
+
+struct test_data {
+	const char *s1;
+	const char *s2;
+	size_t expected_first_change; /* or strlen() when equal */
+};
+
+static struct test_data data[] = {
+	{ "abc", "abc", 3 },
+	{ "abc", "def", 0 },
+
+	{ "abc", "abz", 2 },
+
+	{ "abc", "abcdef", 3 },
+
+	{ "abc\xF0zzz", "abc\xFFzzz", 3 },
+
+	{ NULL, NULL, 0 }
+};
+
+int try_pair(const char *sa, const char *sb, size_t expected_first_change)
+{
+	int failed = 0;
+	int r_exp, r_tst, r_exp_sign, r_tst_sign;
+	size_t offset;
+
+	/*
+	 * Because differnt CRTs behave differently, only rely on signs
+	 * of the result values.
+	 */
+	r_exp = strcmp(sa, sb);
+	r_exp_sign = ((r_exp < 0) ? -1 : ((r_exp == 0) ? 0 : 1));
+
+	r_tst = strcmp_offset(sa, sb, &offset);
+	r_tst_sign = ((r_tst < 0) ? -1 : ((r_tst == 0) ? 0 : 1));
+
+	if (r_tst_sign != r_exp_sign) {
+		error("FAIL: '%s' vs '%s', result expect %d, observed %d\n",
+			  sa, sb, r_exp_sign, r_tst_sign);
+		failed = 1;
+	}
+
+	if (offset != expected_first_change) {
+		error("FAIL: '%s' vs '%s', offset expect %lu, observed %lu\n",
+			  sa, sb, expected_first_change, offset);
+		failed = 1;
+	}
+
+	return failed;
+}
+
+int cmd_main(int argc, const char **argv)
+{
+	int failed = 0;
+	int k;
+
+	for (k=0; data[k].s1; k++) {
+		failed += try_pair(data[k].s1, data[k].s2, data[k].expected_first_change);
+		failed += try_pair(data[k].s2, data[k].s1, data[k].expected_first_change);
+	}
+
+	return failed;
+}
diff --git a/t/t0065-strcmp-offset.sh b/t/t0065-strcmp-offset.sh
new file mode 100755
index 0000000..0176c8c
--- /dev/null
+++ b/t/t0065-strcmp-offset.sh
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+test_description='Test strcmp_offset functionality'
+
+. ./test-lib.sh
+
+test_expect_success run_helper '
+	test-strcmp-offset
+'
+
+test_done
-- 
2.9.3

[PATCH v7 2/3] p0004-read-tree: perf test to time read-tree

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 t/perf/p0004-read-tree.sh | 117 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 117 insertions(+)
 create mode 100755 t/perf/p0004-read-tree.sh

diff --git a/t/perf/p0004-read-tree.sh b/t/perf/p0004-read-tree.sh
new file mode 100755
index 0000000..a70e969
--- /dev/null
+++ b/t/perf/p0004-read-tree.sh
@@ -0,0 +1,117 @@
+#!/bin/sh
+
+test_description="Tests performance of read-tree"
+
+. ./perf-lib.sh
+
+test_perf_default_repo
+test_checkout_worktree
+
+## usage: dir depth width files
+fill_index() {
+	awk -v arg_dir=$1 -v arg_depth=$2 -v arg_width=$3 -v arg_files=$4 '
+		function make_paths(dir, depth, width, files, f, w) {
+			for (f = 1; f <= files; f++) {
+				print dir "/file" f
+			}
+			if (depth > 0) {
+				for (w = 1; w <= width; w++) {
+					make_paths(dir "/dir" w, depth - 1, width, files)
+				}
+			}
+		}
+		END { make_paths(arg_dir, arg_depth, arg_width, arg_files) }
+' </dev/null |
+	sed "s/^/100644 $EMPTY_BLOB	/" |
+	git update-index --index-info
+	return 0
+}
+
+
+
+
+br_base=xxx_base_xxx
+br_work1=xxx_work1_xxx
+br_work2=xxx_work2_xxx
+br_work3=xxx_work3_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_base
+export br_work1
+export br_work2
+export br_work3
+
+export new_dir
+
+export depth
+export width
+export files
+
+## The number of files in the xxx_base_xxx branch.
+nr_base=$(git ls-files | wc -l)
+export nr_base
+
+## Inflate the index with thousands of empty files and commit it.
+## Turn on sparse-checkout so that we don't have to populate them
+## later when we start switching branches.  Use reset --hard to
+## quickly checkout the new HEAD with minimum actual files.
+test_expect_success 'inflate the index' '
+	git reset --hard &&
+	git branch $br_base &&
+	git branch $br_work1 &&
+	git checkout $br_work1 &&
+	fill_index $new_dir $depth $width $files &&
+	git commit -m $br_work1 &&
+	echo $new_dir/file1 >.git/info/sparse-checkout &&
+	git config --local core.sparsecheckout 1 &&
+	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 work1 ($nr_work1)" '
+	git read-tree -m $br_base $br_work1 -n
+'
+
+## Alternate between base and work branches several
+## times to measure a large change.
+test_perf "switch base work1 ($nr_base $nr_work1)" '
+	git checkout $br_base &&
+	git checkout $br_work1
+'
+
+## Create work2 by modifying 1 file in work1.
+## Create work3 as an alias of work2.
+test_expect_success 'setup work2' '
+	git branch $br_work2 &&
+	git checkout $br_work2 &&
+	echo x >$new_dir/file1 &&
+	git add $new_dir/file1 &&
+	git commit -m $br_work2 &&
+	git branch $br_work3
+'
+
+## Alternate between work1 and work2 several times
+## to measure a very small change.
+test_perf "switch work1 work2 ($nr_work1)" '
+	git checkout $br_work1 &&
+	git checkout $br_work2
+'
+
+## Alternate between branches work2 and work3 which
+## are aliases of the same commit.
+test_perf "switch commit aliases ($nr_work1)" '
+	git checkout $br_work3 &&
+	git checkout $br_work2
+'
+
+test_done
-- 
2.9.3

[PATCH v7 3/3] read-cache: speed up add_index_entry during checkout

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Teach add_index_entry_with_check() and has_dir_name()
to see if the path of the new item is greater than the
last path in the index array before attempting to search
for it.

During checkout, merge_working_tree() populates the new
index in sorted order, so this change will save at least 2
binary lookups per file.  This preserves the original
behavior but simply checks the last element before starting
the search.

This helps performance on very large repositories.

================
Before and after numbers on index with 1M files
./p0004-read-tree.sh
0004.2: read-tree work1 (1003037)          3.21(2.54+0.62)
0004.3: switch base work1 (3038 1003037)   7.49(5.39+1.84)
0004.5: switch work1 work2 (1003037)       11.91(8.38+3.00)
0004.6: switch commit aliases (1003037)    12.22(8.30+3.06)

./p0004-read-tree.sh
0004.2: read-tree work1 (1003040)          2.40(1.65+0.73)
0004.3: switch base work1 (3041 1003040)   6.07(4.12+1.66)
0004.5: switch work1 work2 (1003040)       10.23(6.76+2.92)
0004.6: switch commit aliases (1003040)    10.53(6.97+2.83)
================

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 read-cache.c | 46 ++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 44 insertions(+), 2 deletions(-)

diff --git a/read-cache.c b/read-cache.c
index 97f13a1..a8ef823 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -918,9 +918,24 @@ static int has_dir_name(struct index_state *istate,
 	int stage = ce_stage(ce);
 	const char *name = ce->name;
 	const char *slash = name + ce_namelen(ce);
+	size_t len_eq_last;
+	int cmp_last = 0;
+
+	if (istate->cache_nr > 0) {
+		/*
+		 * Compare the entry's full path with the last path in the index.
+		 * If it sorts AFTER the last entry in the index and they have no
+		 * common prefix, then there cannot be any F/D name conflicts.
+		 */
+		cmp_last = strcmp_offset(name,
+			istate->cache[istate->cache_nr-1]->name,
+			&len_eq_last);
+		if (cmp_last > 0 && len_eq_last == 0)
+			return retval;
+	}
 
 	for (;;) {
-		int len;
+		size_t len;
 
 		for (;;) {
 			if (*--slash == '/')
@@ -930,6 +945,24 @@ static int has_dir_name(struct index_state *istate,
 		}
 		len = slash - name;
 
+		if (cmp_last > 0) {
+			/*
+			 * If this part of the directory prefix (including the trailing
+			 * slash) already appears in the path of the last entry in the
+			 * index, then we cannot also have a file with this prefix (or
+			 * any parent directory prefix).
+			 */
+			if (len+1 <= len_eq_last)
+				return retval;
+			/*
+			 * If this part of the directory prefix (excluding the trailing
+			 * slash) is longer than the known equal portions, then this part
+			 * of the prefix cannot collide with a file.  Go on to the parent.
+			 */
+			if (len > len_eq_last)
+				continue;
+		}
+
 		pos = index_name_stage_pos(istate, name, len, stage);
 		if (pos >= 0) {
 			/*
@@ -1021,7 +1054,16 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e
 
 	if (!(option & ADD_CACHE_KEEP_CACHE_TREE))
 		cache_tree_invalidate_path(istate, ce->name);
-	pos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce));
+
+	/*
+	 * If this entry's path sorts after the last entry in the index,
+	 * we can avoid searching for it.
+	 */
+	if (istate->cache_nr > 0 &&
+		strcmp(ce->name, istate->cache[istate->cache_nr - 1]->name) > 0)
+		pos = -istate->cache_nr - 1;
+	else
+		pos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce));
 
 	/* existing match? Just replace it. */
 	if (pos >= 0) {
-- 
2.9.3

Re: [PATCH v7 3/3] read-cache: speed up add_index_entry during checkout

[Jeff King]

On Fri, Apr 07, 2017 at 09:20:47PM +0000, git@jeffhostetler.com wrote:

> This helps performance on very large repositories.
> 
> ================
> Before and after numbers on index with 1M files
> ./p0004-read-tree.sh
> 0004.2: read-tree work1 (1003037)          3.21(2.54+0.62)
> 0004.3: switch base work1 (3038 1003037)   7.49(5.39+1.84)
> 0004.5: switch work1 work2 (1003037)       11.91(8.38+3.00)
> 0004.6: switch commit aliases (1003037)    12.22(8.30+3.06)
> 
> ./p0004-read-tree.sh
> 0004.2: read-tree work1 (1003040)          2.40(1.65+0.73)
> 0004.3: switch base work1 (3041 1003040)   6.07(4.12+1.66)
> 0004.5: switch work1 work2 (1003040)       10.23(6.76+2.92)
> 0004.6: switch commit aliases (1003040)    10.53(6.97+2.83)
> ================

By the way, you may want to try:

  $ cd t/perf
  $ ./run HEAD^ HEAD p0004-read-tree.sh

which gives you the before/after in a nice table, with percentage
changes:

  Test                                       HEAD^             HEAD                  
  -----------------------------------------------------------------------------------
  0004.2: read-tree work1 (1003065)          2.34(1.90+0.42)   1.91(1.51+0.38) -18.4%
  0004.3: switch base work1 (3066 1003065)   5.12(4.14+0.96)   4.45(3.55+0.88) -13.1%
  0004.5: switch work1 work2 (1003065)       8.55(6.63+1.87)   7.78(5.76+2.00) -9.0% 
  0004.6: switch commit aliases (1003065)    8.59(6.75+1.80)   7.64(5.92+1.70) -11.1%

The results are stored for each tested version, so you can re-run just a
single test and then re-output the results with "./aggregate.perl HEAD^
HEAD p0004-read-tree.sh".

The "run" script obviously builds each version behind the scenes, so you
probably also want to set GIT_PERF_MAKE_OPTS as appropriate (at the very
least "-j16" makes it more pleasant).

-Peff

Re: [PATCH v7 1/3] read-cache: add strcmp_offset function

[Jeff King]

On Fri, Apr 07, 2017 at 09:20:45PM +0000, git@jeffhostetler.com wrote:

> diff --git a/t/helper/test-strcmp-offset.c b/t/helper/test-strcmp-offset.c
> new file mode 100644
> index 0000000..03e1eef
> --- /dev/null
> +++ b/t/helper/test-strcmp-offset.c
> @@ -0,0 +1,64 @@
> +#include "cache.h"
> +
> +struct test_data {
> +	const char *s1;
> +	const char *s2;
> +	size_t expected_first_change; /* or strlen() when equal */
> +};
> +
> +static struct test_data data[] = {
> +	{ "abc", "abc", 3 },
> +	{ "abc", "def", 0 },
> +
> +	{ "abc", "abz", 2 },
> +
> +	{ "abc", "abcdef", 3 },
> +
> +	{ "abc\xF0zzz", "abc\xFFzzz", 3 },
> +
> +	{ NULL, NULL, 0 }
> +};

I've been thinking a bit on the comments on earlier rounds regarding C
tests. I think in the early days, we generally had plumbing that exposed
the C interfaces in a pretty transparent way. I.e., it was reasonable to
unit-test update-index, because you pretty much know how input to it
will map to the code and data structures used.

These days we have more C infrastructure, and it's sometimes hard to
tickle the exact inputs to those modules through plumbing commands. So I
don't really object to adding module-specific helpers that make it easy
to unit test these underlying modules.

I'm not sure how I feel about sticking test data in the helpers, though.
A higher level language like shell is actually pretty good for passing
data around. Passing in the input makes it much easier to prod a helper
with new test cases, see its output, run it in a debugger for a specific
case, etc.

It also integrates better with our test suite. For instance, here:

> +	if (r_tst_sign != r_exp_sign) {
> +		error("FAIL: '%s' vs '%s', result expect %d, observed %d\n",
> +			  sa, sb, r_exp_sign, r_tst_sign);
> +		failed = 1;
> +	}
> +
> +	if (offset != expected_first_change) {
> +		error("FAIL: '%s' vs '%s', offset expect %lu, observed %lu\n",
> +			  sa, sb, expected_first_change, offset);
> +		failed = 1;
> +	}
> +
> +	return failed;
> +}

You're essentially rebuilding a test harness just for this one function,
and the regular test harness only knows "did anything fail", and nothing
about specific tests.

Perhaps something like:

 t/helper/test-strcmp-offset.c | 66 +++++++----------------------------
 t/t0065-strcmp-offset.sh      | 17 +++++++--
 2 files changed, 26 insertions(+), 57 deletions(-)

diff --git a/t/helper/test-strcmp-offset.c b/t/helper/test-strcmp-offset.c
index 03e1eef8a..1fdf4d137 100644
--- a/t/helper/test-strcmp-offset.c
+++ b/t/helper/test-strcmp-offset.c
@@ -1,64 +1,22 @@
 #include "cache.h"
 
-struct test_data {
-	const char *s1;
-	const char *s2;
-	size_t expected_first_change; /* or strlen() when equal */
-};
-
-static struct test_data data[] = {
-	{ "abc", "abc", 3 },
-	{ "abc", "def", 0 },
-
-	{ "abc", "abz", 2 },
-
-	{ "abc", "abcdef", 3 },
-
-	{ "abc\xF0zzz", "abc\xFFzzz", 3 },
-
-	{ NULL, NULL, 0 }
-};
-
-int try_pair(const char *sa, const char *sb, size_t expected_first_change)
+int cmd_main(int argc, const char **argv)
 {
-	int failed = 0;
-	int r_exp, r_tst, r_exp_sign, r_tst_sign;
+	int result;
 	size_t offset;
 
+	if (!argv[1] || !argv[2])
+		die("usage: %s <string1> <string2>", argv[0]);
+
+	result = strcmp_offset(argv[1], argv[2], &offset);
+
 	/*
 	 * Because differnt CRTs behave differently, only rely on signs
 	 * of the result values.
 	 */
-	r_exp = strcmp(sa, sb);
-	r_exp_sign = ((r_exp < 0) ? -1 : ((r_exp == 0) ? 0 : 1));
-
-	r_tst = strcmp_offset(sa, sb, &offset);
-	r_tst_sign = ((r_tst < 0) ? -1 : ((r_tst == 0) ? 0 : 1));
-
-	if (r_tst_sign != r_exp_sign) {
-		error("FAIL: '%s' vs '%s', result expect %d, observed %d\n",
-			  sa, sb, r_exp_sign, r_tst_sign);
-		failed = 1;
-	}
-
-	if (offset != expected_first_change) {
-		error("FAIL: '%s' vs '%s', offset expect %lu, observed %lu\n",
-			  sa, sb, expected_first_change, offset);
-		failed = 1;
-	}
-
-	return failed;
-}
-
-int cmd_main(int argc, const char **argv)
-{
-	int failed = 0;
-	int k;
-
-	for (k=0; data[k].s1; k++) {
-		failed += try_pair(data[k].s1, data[k].s2, data[k].expected_first_change);
-		failed += try_pair(data[k].s2, data[k].s1, data[k].expected_first_change);
-	}
-
-	return failed;
+	result = result < 0 ? -1 :
+		 result > 0 ? 1 :
+		 0;
+	printf("%d %"PRIuMAX"\n", result, (uintmax_t)offset);
+	return 0;
 }
diff --git a/t/t0065-strcmp-offset.sh b/t/t0065-strcmp-offset.sh
index 0176c8c92..8c167d24b 100755
--- a/t/t0065-strcmp-offset.sh
+++ b/t/t0065-strcmp-offset.sh
@@ -4,8 +4,19 @@ test_description='Test strcmp_offset functionality'
 
 . ./test-lib.sh
 
-test_expect_success run_helper '
-	test-strcmp-offset
-'
+while read s1 s2 expect
+do
+	test_expect_success "strcmp_offset($s1, $s2)" '
+		echo "$expect" >expect &&
+		test-strcmp-offset "$s1" "$s2" >actual &&
+		test_cmp expect actual
+	'
+done <<-EOF
+abc abc 0 3
+abc def -1 0
+abc abz -1 2
+abc abcdef -1 3
+$(printf "abc\360zzz") $(printf "abc\377zzz") -1 3
+EOF
 
 test_done

Re: [PATCH v7 2/3] p0004-read-tree: perf test to time read-tree

[Jeff King]

On Fri, Apr 07, 2017 at 09:20:46PM +0000, git@jeffhostetler.com wrote:

> diff --git a/t/perf/p0004-read-tree.sh b/t/perf/p0004-read-tree.sh
> new file mode 100755
> index 0000000..a70e969

I think p0004 is taken by your lazy-init-name-hash script already
(which, btw, I think is missing its executable bit).

> +## usage: dir depth width files
> +fill_index() {
> +	awk -v arg_dir=$1 -v arg_depth=$2 -v arg_width=$3 -v arg_files=$4 '
> +		function make_paths(dir, depth, width, files, f, w) {
> +			for (f = 1; f <= files; f++) {
> +				print dir "/file" f
> +			}
> +			if (depth > 0) {
> +				for (w = 1; w <= width; w++) {
> +					make_paths(dir "/dir" w, depth - 1, width, files)
> +				}
> +			}
> +		}
> +		END { make_paths(arg_dir, arg_depth, arg_width, arg_files) }
> +' </dev/null |
> +	sed "s/^/100644 $EMPTY_BLOB	/" |
> +	git update-index --index-info
> +	return 0
> +}

I saw some discussion earlier on testing synthetic versus real
repositories. The original point of the perf test suite was to find
performance regressions between versions. So periodically you'd run:

  cd t/perf
  ./run v2.10.0 HEAD

and make sure that nothing got inexplicably slower. And for that, using
real repositories is nice, because it's showing real user-impacting
performance changes, not synthetic benchmarks.

In an ideal world, people run it against their own real repositories and
can report back to the list when they see a problem. So running the
whole suite against your monstrous Windows repo would be a nice
benchmark to do periodically (I shudder to think how long it might take
to run, though).

Of course, perf scripts are also a nice way to show off your
improvements. And synthetic repos can often exaggerate the improvement
(which is sometimes good to see changes, but also sometimes bad if
real-world repos don't show the improvement). And they also serve as a
reproduction case for people who don't necessarily have access to the
extreme repo that motivated the test in the first place.

But one side effect of writing the perf test the way you have it here is
that you _can't_ easily run it against a real repo. I think the perf
suite could provide better tools for this. You can already say "run this
test against repo X" with GIT_PERF_REPO. But there's no way to say
"create a synthetic repo with parameters X,Y,Z, and run against that".

IOW, I think rather than having the perf-scripts themselves create the
synthetic repo, we should have a _library_ of synthetic repos that the
test-runners can choose from. I'm imagining a world where your repo
setup goes into t/perf/repos/many-files.sh (which could even take your
depth, width, and files parameters to allow experimenting), and then you
could run "GIT_PERF_REPO=many-files ./p0004-read-tree.sh".

> +br_base=xxx_base_xxx
> +br_work1=xxx_work1_xxx
> +br_work2=xxx_work2_xxx
> +br_work3=xxx_work3_xxx

FWIW, I really dislike the extra level of indirection here. You still
have to consistently say $br_base everywhere. Why not just call the
branch "br_base" in the first place?

My experience has been that debugging tests is much easier when as
little state is carried in the environment as possible. Because it's
quite often reasonable to do:

  ./t1234-whatever.sh -v -i
  cd trash*
  git cmd-that-failed

where you can pick the final line out from the failed test output. When
the command involves $br_base, I have to dig into the script to find out
what's in that variable.

I know that perf tests need less debugging than the regular regression
tests, but I'd hate to see this pattern get applied liberally.

-Peff

Re: [PATCH v7 2/3] p0004-read-tree: perf test to time read-tree

[Jeff Hostetler]

On 4/8/2017 6:36 AM, Jeff King wrote:
> On Fri, Apr 07, 2017 at 09:20:46PM +0000, git@jeffhostetler.com wrote:
>
>> diff --git a/t/perf/p0004-read-tree.sh b/t/perf/p0004-read-tree.sh
>> new file mode 100755
>> index 0000000..a70e969
>
> I think p0004 is taken by your lazy-init-name-hash script already
> (which, btw, I think is missing its executable bit).
>
>> +## usage: dir depth width files
>> +fill_index() {
>> +	awk -v arg_dir=$1 -v arg_depth=$2 -v arg_width=$3 -v arg_files=$4 '
>> +		function make_paths(dir, depth, width, files, f, w) {
>> +			for (f = 1; f <= files; f++) {
>> +				print dir "/file" f
>> +			}
>> +			if (depth > 0) {
>> +				for (w = 1; w <= width; w++) {
>> +					make_paths(dir "/dir" w, depth - 1, width, files)
>> +				}
>> +			}
>> +		}
>> +		END { make_paths(arg_dir, arg_depth, arg_width, arg_files) }
>> +' </dev/null |
>> +	sed "s/^/100644 $EMPTY_BLOB	/" |
>> +	git update-index --index-info
>> +	return 0
>> +}
>
> I saw some discussion earlier on testing synthetic versus real
> repositories. The original point of the perf test suite was to find
> performance regressions between versions. So periodically you'd run:
>
>   cd t/perf
>   ./run v2.10.0 HEAD
>
> and make sure that nothing got inexplicably slower. And for that, using
> real repositories is nice, because it's showing real user-impacting
> performance changes, not synthetic benchmarks.
>
> In an ideal world, people run it against their own real repositories and
> can report back to the list when they see a problem. So running the
> whole suite against your monstrous Windows repo would be a nice
> benchmark to do periodically (I shudder to think how long it might take
> to run, though).
>
> Of course, perf scripts are also a nice way to show off your
> improvements. And synthetic repos can often exaggerate the improvement
> (which is sometimes good to see changes, but also sometimes bad if
> real-world repos don't show the improvement). And they also serve as a
> reproduction case for people who don't necessarily have access to the
> extreme repo that motivated the test in the first place.
>
> But one side effect of writing the perf test the way you have it here is
> that you _can't_ easily run it against a real repo. I think the perf
> suite could provide better tools for this. You can already say "run this
> test against repo X" with GIT_PERF_REPO. But there's no way to say
> "create a synthetic repo with parameters X,Y,Z, and run against that".
>
> IOW, I think rather than having the perf-scripts themselves create the
> synthetic repo, we should have a _library_ of synthetic repos that the
> test-runners can choose from. I'm imagining a world where your repo
> setup goes into t/perf/repos/many-files.sh (which could even take your
> depth, width, and files parameters to allow experimenting), and then you
> could run "GIT_PERF_REPO=many-files ./p0004-read-tree.sh".

Agreed, both types of repos have value.  We've also been discussing
internally the need for more test repos with specific data shapes.
Whether that is a collection of pre-built repos (like what libgit2
does) or scripts to build and persist them I don't know.

Let me take a stab at that separation.

>
>> +br_base=xxx_base_xxx
>> +br_work1=xxx_work1_xxx
>> +br_work2=xxx_work2_xxx
>> +br_work3=xxx_work3_xxx
>
> FWIW, I really dislike the extra level of indirection here. You still
> have to consistently say $br_base everywhere. Why not just call the
> branch "br_base" in the first place?
>
> My experience has been that debugging tests is much easier when as
> little state is carried in the environment as possible. Because it's
> quite often reasonable to do:
>
>   ./t1234-whatever.sh -v -i
>   cd trash*
>   git cmd-that-failed
>
> where you can pick the final line out from the failed test output. When
> the command involves $br_base, I have to dig into the script to find out
> what's in that variable.
>
> I know that perf tests need less debugging than the regular regression
> tests, but I'd hate to see this pattern get applied liberally.

That makes sense.

Thanks
Jeff