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

From: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Date: May 11, 2017, 07:43 UTC
Message-ID: <20170511074354.11336-3-avarab@gmail.com>
In-Reply-To: <20170511074354.11336-1-avarab@gmail.com>

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

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