threads / patch / 45928

v3, 2 partsperf: add function to setup a fresh test repo

Subject: [PATCH v3 1/2] perf: add function to setup a fresh test repo

## tl;dr

7 messages between May 11, 2017 and May 11, 2017. Diffs are folded; open one to read it.

replies: 6people: 2as markdown or json

Ævar Arnfjörð Bjarmason· May 11, 2017, 07:43 UTC · lore

[PATCH v3 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0

Fixes the issues noted in v3, see <20170510225316.31680-1-avarab@gmail.com> (https://public-inbox.org/git/20170510225316.31680-1-avarab@gmail.com/).

In addition I was wrong about for-each-ref not being subjected to this slowdown, I was just screwing up the testcase. Fix that. Now:

    $ GIT_PERF_REPEAT_COUNT=1 GIT_PERF_MAKE_OPTS="-j6 NO_OPENSSL=Y NO_WILDMATCH=YesPlease" ./run v1.9.5 v2.12.0 p0100-globbing.sh
    Test                                                       v1.9.5            v2.12.0
    -------------------------------------------------------------------------------------------------
    0100.2: refglob((a*)^nb) against tag (a^100).t; n = 1      0.00(0.00+0.00)   0.00(0.00+0.00) =
    0100.3: refglob((a*)^nb) against tag (a^100).t; n = 2      0.00(0.00+0.00)   0.00(0.00+0.00) =
    0100.4: refglob((a*)^nb) against tag (a^100).t; n = 3      0.00(0.00+0.00)   0.00(0.00+0.00) =
    0100.5: refglob((a*)^nb) against tag (a^100).t; n = 4      0.00(0.00+0.00)   0.01(0.00+0.00) +inf
    0100.6: refglob((a*)^nb) against tag (a^100).t; n = 5      0.00(0.00+0.00)   0.16(0.15+0.00) +inf
    0100.7: refglob((a*)^nb) against tag (a^100).t; n = 6      0.00(0.00+0.00)   2.73(2.71+0.00) +inf
    0100.8: fileglob((a*)^nb) against file (a^100).t; n = 1    0.00(0.00+0.00)   0.00(0.00+0.00) =
    0100.9: fileglob((a*)^nb) against file (a^100).t; n = 2    0.00(0.00+0.00)   0.00(0.00+0.00) =
    0100.10: fileglob((a*)^nb) against file (a^100).t; n = 3   0.00(0.00+0.00)   0.00(0.00+0.00) =
    0100.11: fileglob((a*)^nb) against file (a^100).t; n = 4   0.00(0.00+0.00)   0.01(0.00+0.00) +inf
    0100.12: fileglob((a*)^nb) against file (a^100).t; n = 5   0.00(0.00+0.00)   0.16(0.15+0.00) +inf
    0100.13: fileglob((a*)^nb) against file (a^100).t; n = 6   0.00(0.00+0.00)   2.75(2.73+0.00) +inf

Ævar Arnfjörð Bjarmason (2):
  perf: add function to setup a fresh test repo
  perf: add test showing exponential growth in path globbing

 t/perf/README            |  1 +
 t/perf/p0100-globbing.sh | 43 +++++++++++++++++++++++++++++++++++++++++++
 t/perf/perf-lib.sh       | 17 +++++++++++++----
 3 files changed, 57 insertions(+), 4 deletions(-)
 create mode 100755 t/perf/p0100-globbing.sh

-- 
2.11.0

Ævar Arnfjörð Bjarmason· May 11, 2017, 07:43 UTC · re: Ævar Arnfjörð Bjarmason · lore

Add a function to setup a fresh test repo via 'git init' to compliment the existing functions to copy over a normal & large repo.

Some performance tests don't need any existing repository data at all to be significant, e.g. tests which stress glob matches against single pathological revisions or files, which I'm about to add in a subsequent commit.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 t/perf/README      |  1 +
 t/perf/perf-lib.sh | 17 +++++++++++++----
 2 files changed, 14 insertions(+), 4 deletions(-)

Show changes to 2 files +14 −4

t/perf/README, t/perf/perf-lib.sh

diff --git a/t/perf/README b/t/perf/README
index 49ea4349be..de2fe15696 100644
--- a/t/perf/README
+++ b/t/perf/README
@@ -106,6 +106,7 @@ sources perf-lib.sh:
 
 After that you will want to use some of the following:
 
+	test_perf_fresh_repo    # sets up an empty repository
 	test_perf_default_repo  # sets up a "normal" repository
 	test_perf_large_repo    # sets up a "large" repository
 
diff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh
index ab4b8b06ae..f51fc773e8 100644
--- a/t/perf/perf-lib.sh
+++ b/t/perf/perf-lib.sh
@@ -78,6 +78,10 @@ if test -z "$GIT_PERF_LARGE_REPO"; then
 	GIT_PERF_LARGE_REPO=$TEST_DIRECTORY/..
 fi
 
+test_perf_do_repo_symlink_config_ () {
+	test_have_prereq SYMLINKS || git config core.symlinks false
+}
+
 test_perf_create_repo_from () {
 	test "$#" = 2 ||
 	error "bug in the test script: not 2 parameters to test-create-repo"
@@ -102,15 +106,20 @@ test_perf_create_repo_from () {
 	) &&
 	(
 		cd "$repo" &&
-		"$MODERN_GIT" init -q && {
-			test_have_prereq SYMLINKS ||
-			git config core.symlinks false
-		} &&
+		"$MODERN_GIT" init -q &&
+		test_perf_do_repo_symlink_config_ &&
 		mv .git/hooks .git/hooks-disabled 2>/dev/null
 	) || error "failed to copy repository '$source' to '$repo'"
 }
 
 # call at least one of these to establish an appropriately-sized repository
+test_perf_fresh_repo () {
+	repo="${1:-$TRASH_DIRECTORY}"
+	"$MODERN_GIT" init -q "$repo" &&
+	cd "$repo" &&
+	test_perf_do_repo_symlink_config_
+}
+
 test_perf_default_repo () {
 	test_perf_create_repo_from "${1:-$TRASH_DIRECTORY}" "$GIT_PERF_REPO"
 }

-- 
2.11.0

Ævar Arnfjörð Bjarmason· May 11, 2017, 07:43 UTC · re: Ævar Arnfjörð Bjarmason · lore

[PATCH v3 2/2] perf: add test showing exponential growth in path globbing

Add a test showing that runtimes of the wildmatch() function used for globbing in git grow exponentially in the face of some pathological globs.

This issue affects both globs matching filenames via e.g. ls-files, and globs matching refnames via e.g. for-each-ref.

As noted in the test description this is a test to see whether Git suffers from the issue noted in an article Russ Cox posted today about common bugs in various glob implementations: https://research.swtch.com/glob

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 t/perf/p0100-globbing.sh | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)
 create mode 100755 t/perf/p0100-globbing.sh

Show changes to t/perf/p0100-globbing.sh +43 −0

diff --git a/t/perf/p0100-globbing.sh b/t/perf/p0100-globbing.sh
new file mode 100755
index 0000000000..dd18a9ce2b
--- /dev/null
+++ b/t/perf/p0100-globbing.sh
@@ -0,0 +1,43 @@
+#!/bin/sh
+
+test_description="Tests pathological globbing performance
+
+Shows how Git's globbing performance performs when given the sort of
+pathological patterns described in at https://research.swtch.com/glob
+"
+
+. ./perf-lib.sh
+
+test_globs_big='10 25 50 75 100'
+test_globs_small='1 2 3 4 5 6'
+
+test_perf_fresh_repo
+
+test_expect_success 'setup' '
+	for i in $(test_seq 1 100)
+	do
+		printf "a" >>refname &&
+		for j in $(test_seq 1 $i)
+		do
+			printf "a*" >>refglob.$i
+		done &&
+		echo b >>refglob.$i
+	done &&
+	test_commit test $(cat refname).t "" $(cat refname).t
+'
+
+for i in $test_globs_small
+do
+	test_perf "refglob((a*)^nb) against tag (a^100).t; n = $i" '
+		git for-each-ref "refs/tags/$(cat refglob.'$i')b"
+	'
+done
+
+for i in $test_globs_small
+do
+	test_perf "fileglob((a*)^nb) against file (a^100).t; n = $i" '
+		git ls-files "$(cat refglob.'$i')b"
+	'
+done
+
+test_done

-- 
2.11.0

Ævar Arnfjörð Bjarmason· May 11, 2017, 09:41 UTC · re: Ævar Arnfjörð Bjarmason · lore

[PATCH v4 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0

Fixes a brainfart in v3. I thought I'd fixed that subshell cd issue, but turns out I didn't, actually fix that.

Ævar Arnfjörð Bjarmason (2):
  perf: add function to setup a fresh test repo
  perf: add test showing exponential growth in path globbing

 t/perf/README            |  1 +
 t/perf/p0100-globbing.sh | 43 +++++++++++++++++++++++++++++++++++++++++++
 t/perf/perf-lib.sh       | 19 +++++++++++++++----
 3 files changed, 59 insertions(+), 4 deletions(-)
 create mode 100755 t/perf/p0100-globbing.sh

-- 
2.11.0

Ævar Arnfjörð Bjarmason· May 11, 2017, 09:41 UTC · re: Ævar Arnfjörð Bjarmason · lore

[PATCH v4 1/2] perf: add function to setup a fresh test repo

Add a function to setup a fresh test repo via 'git init' to compliment the existing functions to copy over a normal & large repo.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 t/perf/README      |  1 +
 t/perf/perf-lib.sh | 19 +++++++++++++++----
 2 files changed, 16 insertions(+), 4 deletions(-)

Show changes to 2 files +16 −4

t/perf/README, t/perf/perf-lib.sh

diff --git a/t/perf/README b/t/perf/README
index 49ea4349be..de2fe15696 100644
--- a/t/perf/README
+++ b/t/perf/README
@@ -106,6 +106,7 @@ sources perf-lib.sh:
 
 After that you will want to use some of the following:
 
+	test_perf_fresh_repo    # sets up an empty repository
 	test_perf_default_repo  # sets up a "normal" repository
 	test_perf_large_repo    # sets up a "large" repository
 
diff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh
index ab4b8b06ae..b6fc880395 100644
--- a/t/perf/perf-lib.sh
+++ b/t/perf/perf-lib.sh
@@ -78,6 +78,10 @@ if test -z "$GIT_PERF_LARGE_REPO"; then
 	GIT_PERF_LARGE_REPO=$TEST_DIRECTORY/..
 fi
 
+test_perf_do_repo_symlink_config_ () {
+	test_have_prereq SYMLINKS || git config core.symlinks false
+}
+
 test_perf_create_repo_from () {
 	test "$#" = 2 ||
 	error "bug in the test script: not 2 parameters to test-create-repo"
@@ -102,15 +106,22 @@ test_perf_create_repo_from () {
 	) &&
 	(
 		cd "$repo" &&
-		"$MODERN_GIT" init -q && {
-			test_have_prereq SYMLINKS ||
-			git config core.symlinks false
-		} &&
+		"$MODERN_GIT" init -q &&
+		test_perf_do_repo_symlink_config_ &&
 		mv .git/hooks .git/hooks-disabled 2>/dev/null
 	) || error "failed to copy repository '$source' to '$repo'"
 }
 
 # call at least one of these to establish an appropriately-sized repository
+test_perf_fresh_repo () {
+	repo="${1:-$TRASH_DIRECTORY}"
+	"$MODERN_GIT" init -q "$repo" &&
+	(
+		cd "$repo" &&
+		test_perf_do_repo_symlink_config_
+	)
+}
+
 test_perf_default_repo () {
 	test_perf_create_repo_from "${1:-$TRASH_DIRECTORY}" "$GIT_PERF_REPO"
 }

-- 
2.11.0

Ævar Arnfjörð Bjarmason· May 11, 2017, 09:41 UTC · re: Ævar Arnfjörð Bjarmason · lore

[PATCH v4 2/2] perf: add test showing exponential growth in path globbing

Add a test showing that runtimes of the wildmatch() function used for globbing in git grow exponentially in the face of some pathological globs.

This issue affects both globs matching filenames via e.g. ls-files, and globs matching refnames via e.g. for-each-ref.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 t/perf/p0100-globbing.sh | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)
 create mode 100755 t/perf/p0100-globbing.sh

Show changes to t/perf/p0100-globbing.sh +43 −0

diff --git a/t/perf/p0100-globbing.sh b/t/perf/p0100-globbing.sh
new file mode 100755
index 0000000000..dd18a9ce2b
--- /dev/null
+++ b/t/perf/p0100-globbing.sh
@@ -0,0 +1,43 @@
+#!/bin/sh
+
+test_description="Tests pathological globbing performance
+
+Shows how Git's globbing performance performs when given the sort of
+pathological patterns described in at https://research.swtch.com/glob
+"
+
+. ./perf-lib.sh
+
+test_globs_big='10 25 50 75 100'
+test_globs_small='1 2 3 4 5 6'
+
+test_perf_fresh_repo
+
+test_expect_success 'setup' '
+	for i in $(test_seq 1 100)
+	do
+		printf "a" >>refname &&
+		for j in $(test_seq 1 $i)
+		do
+			printf "a*" >>refglob.$i
+		done &&
+		echo b >>refglob.$i
+	done &&
+	test_commit test $(cat refname).t "" $(cat refname).t
+'
+
+for i in $test_globs_small
+do
+	test_perf "refglob((a*)^nb) against tag (a^100).t; n = $i" '
+		git for-each-ref "refs/tags/$(cat refglob.'$i')b"
+	'
+done
+
+for i in $test_globs_small
+do
+	test_perf "fileglob((a*)^nb) against file (a^100).t; n = $i" '
+		git ls-files "$(cat refglob.'$i')b"
+	'
+done
+
+test_done

-- 
2.11.0

Jonathan Nieder· May 11, 2017, 19:17 UTC · re: Ævar Arnfjörð Bjarmason · lore

Re: [PATCH v4 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0

Ævar Arnfjörð Bjarmason wrote:

Show 9 quoted lines

> Ævar Arnfjörð Bjarmason (2):
>   perf: add function to setup a fresh test repo
>   perf: add test showing exponential growth in path globbing
> 
>  t/perf/README            |  1 +
>  t/perf/p0100-globbing.sh | 43 +++++++++++++++++++++++++++++++++++++++++++
>  t/perf/perf-lib.sh       | 19 +++++++++++++++----
>  3 files changed, 59 insertions(+), 4 deletions(-)
>  create mode 100755 t/perf/p0100-globbing.sh

Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>

Thanks.