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

From: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Date: May 10, 2017, 22:53 UTC
Message-ID: <20170510225316.31680-3-avarab@gmail.com>
In-Reply-To: <20170510225316.31680-1-avarab@gmail.com>

Add a test showing that ls-files times grow exponentially in the face of some pathological globs, whereas refglobs via for-each-ref don't in practice suffer from the same issue.

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

The pathological git-ls-files globbing is done by wildmatch() in wildmatch.c. The for-each-ref codepath also uses wildmatch(), but will always match against e.g. "refs/tags/aaa...", not "aaa.." as git-ls-files will.

I'm unsure why the pathological case isn't triggered by for-each-ref, but in any case, now we have a performance test for it.

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

diff --git a/t/perf/p0100-globbing.sh b/t/perf/p0100-globbing.sh
new file mode 100755
index 0000000000..e98fd7ce4b
--- /dev/null
+++ b/t/perf/p0100-globbing.sh
@@ -0,0 +1,48 @@
+#!/bin/sh
+
+test_description="Tests pathalogical globbing performance
+
+Shows how Git's globbing performance performs when given the sort of
+pathalogical 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 $(cat refname) &&
+	for i in $(test_seq 1 100)
+	do
+	echo	git tag $(cat refname)-$i
+	done &&
+	test_commit hello
+'
+
+for i in $test_globs_big
+do
+	test_perf "refglob((a*)^nb) against tag a^100; 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