19 files changed, 1046 insertions, 0 deletions

diff --git a/t/perf/.gitignore b/t/perf/.gitignore
new file mode 100644
index 0000000000..982eb8e3a9
--- /dev/null
+++ b/t/perf/.gitignore
@@ -0,0 +1,3 @@
+/build/
+/test-results/
+/trash directory*/
diff --git a/t/perf/Makefile b/t/perf/Makefile
new file mode 100644
index 0000000000..8c47155a7c
--- /dev/null
+++ b/t/perf/Makefile
@@ -0,0 +1,15 @@
+-include ../../config.mak
+export GIT_TEST_OPTIONS
+
+all: perf
+
+perf: pre-clean
+	./run
+
+pre-clean:
+	rm -rf test-results
+
+clean:
+	rm -rf build "trash directory".* test-results
+
+.PHONY: all perf pre-clean clean
diff --git a/t/perf/README b/t/perf/README
new file mode 100644
index 0000000000..8848c14619
--- /dev/null
+++ b/t/perf/README
@@ -0,0 +1,146 @@
+Git performance tests
+=====================
+
+This directory holds performance testing scripts for git tools.  The
+first part of this document describes the various ways in which you
+can run them.
+
+When fixing the tools or adding enhancements, you are strongly
+encouraged to add tests in this directory to cover what you are
+trying to fix or enhance.  The later part of this short document
+describes how your test scripts should be organized.
+
+
+Running Tests
+-------------
+
+The easiest way to run tests is to say "make".  This runs all
+the tests on the current git repository.
+
+    === Running 2 tests in this tree ===
+    [...]
+    Test                                     this tree
+    ---------------------------------------------------------
+    0001.1: rev-list --all                   0.54(0.51+0.02)
+    0001.2: rev-list --all --objects         6.14(5.99+0.11)
+    7810.1: grep worktree, cheap regex       0.16(0.16+0.35)
+    7810.2: grep worktree, expensive regex   7.90(29.75+0.37)
+    7810.3: grep --cached, cheap regex       3.07(3.02+0.25)
+    7810.4: grep --cached, expensive regex   9.39(30.57+0.24)
+
+You can compare multiple repositories and even git revisions with the
+'run' script:
+
+    $ ./run . origin/next /path/to/git-tree p0001-rev-list.sh
+
+where . stands for the current git tree.  The full invocation is
+
+    ./run [<revision|directory>...] [--] [<test-script>...]
+
+A '.' argument is implied if you do not pass any other
+revisions/directories.
+
+You can also manually test this or another git build tree, and then
+call the aggregation script to summarize the results:
+
+    $ ./p0001-rev-list.sh
+    [...]
+    $ GIT_BUILD_DIR=/path/to/other/git ./p0001-rev-list.sh
+    [...]
+    $ ./aggregate.perl . /path/to/other/git ./p0001-rev-list.sh
+
+aggregate.perl has the same invocation as 'run', it just does not run
+anything beforehand.
+
+You can set the following variables (also in your config.mak):
+
+    GIT_PERF_REPEAT_COUNT
+	Number of times a test should be repeated for best-of-N
+	measurements.  Defaults to 3.
+
+    GIT_PERF_MAKE_OPTS
+	Options to use when automatically building a git tree for
+	performance testing.  E.g., -j6 would be useful.
+
+    GIT_PERF_REPO
+    GIT_PERF_LARGE_REPO
+	Repositories to copy for the performance tests.  The normal
+	repo should be at least git.git size.  The large repo should
+	probably be about linux.git size for optimal results.
+	Both default to the git.git you are running from.
+
+You can also pass the options taken by ordinary git tests; the most
+useful one is:
+
+--root=<directory>::
+	Create "trash" directories used to store all temporary data during
+	testing under <directory>, instead of the t/ directory.
+	Using this option with a RAM-based filesystem (such as tmpfs)
+	can massively speed up the test suite.
+
+
+Naming Tests
+------------
+
+The performance test files are named as:
+
+	pNNNN-commandname-details.sh
+
+where N is a decimal digit.  The same conventions for choosing NNNN as
+for normal tests apply.
+
+
+Writing Tests
+-------------
+
+The perf script starts much like a normal test script, except it
+sources perf-lib.sh:
+
+	#!/bin/sh
+	#
+	# Copyright (c) 2005 Junio C Hamano
+	#
+
+	test_description='xxx performance test'
+	. ./perf-lib.sh
+
+After that you will want to use some of the following:
+
+	test_perf_default_repo  # sets up a "normal" repository
+	test_perf_large_repo    # sets up a "large" repository
+
+	test_perf_default_repo sub  # ditto, in a subdir "sub"
+
+        test_checkout_worktree  # if you need the worktree too
+
+At least one of the first two is required!
+
+You can use test_expect_success as usual.  For actual performance
+tests, use
+
+	test_perf 'descriptive string' '
+		command1 &&
+		command2
+	'
+
+test_perf spawns a subshell, for lack of better options.  This means
+that
+
+* you _must_ export all variables that you need in the subshell
+
+* you _must_ flag all variables that you want to persist from the
+  subshell with 'test_export':
+
+	test_perf 'descriptive string' '
+		foo=$(git rev-parse HEAD) &&
+		test_export foo
+	'
+
+  The so-exported variables are automatically marked for export in the
+  shell executing the perf test.  For your convenience, test_export is
+  the same as export in the main shell.
+
+  This feature relies on a bit of magic using 'set' and 'source'.
+  While we have tried to make sure that it can cope with embedded
+  whitespace and other special characters, it will not work with
+  multi-line data.
diff --git a/t/perf/aggregate.perl b/t/perf/aggregate.perl
new file mode 100755
index 0000000000..924b19dab4
--- /dev/null
+++ b/t/perf/aggregate.perl
@@ -0,0 +1,167 @@
+#!/usr/bin/perl
+
+use lib '../../perl/blib/lib';
+use strict;
+use warnings;
+use Git;
+
+sub get_times {
+	my $name = shift;
+	open my $fh, "<", $name or return undef;
+	my $line = <$fh>;
+	return undef if not defined $line;
+	close $fh or die "cannot close $name: $!";
+	$line =~ /^(?:(\d+):)?(\d+):(\d+(?:\.\d+)?) (\d+(?:\.\d+)?) (\d+(?:\.\d+)?)$/
+		or die "bad input line: $line";
+	my $rt = ((defined $1 ? $1 : 0.0)*60+$2)*60+$3;
+	return ($rt, $4, $5);
+}
+
+sub format_times {
+	my ($r, $u, $s, $firstr) = @_;
+	if (!defined $r) {
+		return "<missing>";
+	}
+	my $out = sprintf "%.2f(%.2f+%.2f)", $r, $u, $s;
+	if (defined $firstr) {
+		if ($firstr > 0) {
+			$out .= sprintf " %+.1f%%", 100.0*($r-$firstr)/$firstr;
+		} elsif ($r == 0) {
+			$out .= " =";
+		} else {
+			$out .= " +inf";
+		}
+	}
+	return $out;
+}
+
+my (@dirs, %dirnames, %dirabbrevs, %prefixes, @tests);
+while (scalar @ARGV) {
+	my $arg = $ARGV[0];
+	my $dir;
+	last if -f $arg or $arg eq "--";
+	if (! -d $arg) {
+		my $rev = Git::command_oneline(qw(rev-parse --verify), $arg);
+		$dir = "build/".$rev;
+	} else {
+		$arg =~ s{/*$}{};
+		$dir = $arg;
+		$dirabbrevs{$dir} = $dir;
+	}
+	push @dirs, $dir;
+	$dirnames{$dir} = $arg;
+	my $prefix = $dir;
+	$prefix =~ tr/^a-zA-Z0-9/_/c;
+	$prefixes{$dir} = $prefix . '.';
+	shift @ARGV;
+}
+
+if (not @dirs) {
+	@dirs = ('.');
+}
+$dirnames{'.'} = $dirabbrevs{'.'} = "this tree";
+$prefixes{'.'} = '';
+
+shift @ARGV if scalar @ARGV and $ARGV[0] eq "--";
+
+@tests = @ARGV;
+if (not @tests) {
+	@tests = glob "p????-*.sh";
+}
+
+my @subtests;
+my %shorttests;
+for my $t (@tests) {
+	$t =~ s{(?:.*/)?(p(\d+)-[^/]+)\.sh$}{$1} or die "bad test name: $t";
+	my $n = $2;
+	my $fname = "test-results/$t.subtests";
+	open my $fp, "<", $fname or die "cannot open $fname: $!";
+	for (<$fp>) {
+		chomp;
+		/^(\d+)$/ or die "malformed subtest line: $_";
+		push @subtests, "$t.$1";
+		$shorttests{"$t.$1"} = "$n.$1";
+	}
+	close $fp or die "cannot close $fname: $!";
+}
+
+sub read_descr {
+	my $name = shift;
+	open my $fh, "<", $name or return "<error reading description>";
+	my $line = <$fh>;
+	close $fh or die "cannot close $name";
+	chomp $line;
+	return $line;
+}
+
+my %descrs;
+my $descrlen = 4; # "Test"
+for my $t (@subtests) {
+	$descrs{$t} = $shorttests{$t}.": ".read_descr("test-results/$t.descr");
+	$descrlen = length $descrs{$t} if length $descrs{$t}>$descrlen;
+}
+
+sub have_duplicate {
+	my %seen;
+	for (@_) {
+		return 1 if exists $seen{$_};
+		$seen{$_} = 1;
+	}
+	return 0;
+}
+sub have_slash {
+	for (@_) {
+		return 1 if m{/};
+	}
+	return 0;
+}
+
+my %newdirabbrevs = %dirabbrevs;
+while (!have_duplicate(values %newdirabbrevs)) {
+	%dirabbrevs = %newdirabbrevs;
+	last if !have_slash(values %dirabbrevs);
+	%newdirabbrevs = %dirabbrevs;
+	for (values %newdirabbrevs) {
+		s{^[^/]*/}{};
+	}
+}
+
+my %times;
+my @colwidth = ((0)x@dirs);
+for my $i (0..$#dirs) {
+	my $d = $dirs[$i];
+	my $w = length (exists $dirabbrevs{$d} ? $dirabbrevs{$d} : $dirnames{$d});
+	$colwidth[$i] = $w if $w > $colwidth[$i];
+}
+for my $t (@subtests) {
+	my $firstr;
+	for my $i (0..$#dirs) {
+		my $d = $dirs[$i];
+		$times{$prefixes{$d}.$t} = [get_times("test-results/$prefixes{$d}$t.times")];
+		my ($r,$u,$s) = @{$times{$prefixes{$d}.$t}};
+		my $w = length format_times($r,$u,$s,$firstr);
+		$colwidth[$i] = $w if $w > $colwidth[$i];
+		$firstr = $r unless defined $firstr;
+	}
+}
+my $totalwidth = 3*@dirs+$descrlen;
+$totalwidth += $_ for (@colwidth);
+
+printf "%-${descrlen}s", "Test";
+for my $i (0..$#dirs) {
+	my $d = $dirs[$i];
+	printf "   %-$colwidth[$i]s", (exists $dirabbrevs{$d} ? $dirabbrevs{$d} : $dirnames{$d});
+}
+print "\n";
+print "-"x$totalwidth, "\n";
+for my $t (@subtests) {
+	printf "%-${descrlen}s", $descrs{$t};
+	my $firstr;
+	for my $i (0..$#dirs) {
+		my $d = $dirs[$i];
+		my ($r,$u,$s) = @{$times{$prefixes{$d}.$t}};
+		printf "   %-$colwidth[$i]s", format_times($r,$u,$s,$firstr);
+		$firstr = $r unless defined $firstr;
+	}
+	print "\n";
+}
diff --git a/t/perf/min_time.perl b/t/perf/min_time.perl
new file mode 100755
index 0000000000..c1a2717e07
--- /dev/null
+++ b/t/perf/min_time.perl
@@ -0,0 +1,21 @@
+#!/usr/bin/perl
+
+my $minrt = 1e100;
+my $min;
+
+while (<>) {
+	# [h:]m:s.xx U.xx S.xx
+	/^(?:(\d+):)?(\d+):(\d+(?:\.\d+)?) (\d+(?:\.\d+)?) (\d+(?:\.\d+)?)$/
+		or die "bad input line: $_";
+	my $rt = ((defined $1 ? $1 : 0.0)*60+$2)*60+$3;
+	if ($rt < $minrt) {
+		$min = $_;
+		$minrt = $rt;
+	}
+}
+
+if (!defined $min) {
+	die "no input found";
+}
+
+print $min;
diff --git a/t/perf/p0000-perf-lib-sanity.sh b/t/perf/p0000-perf-lib-sanity.sh
new file mode 100755
index 0000000000..cf8e1efce7
--- /dev/null
+++ b/t/perf/p0000-perf-lib-sanity.sh
@@ -0,0 +1,55 @@
+#!/bin/sh
+
+test_description='Tests whether perf-lib facilities work'
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+test_perf 'test_perf_default_repo works' '
+	foo=$(git rev-parse HEAD) &&
+	test_export foo
+'
+
+test_checkout_worktree
+
+test_perf 'test_checkout_worktree works' '
+	wt=$(find . | wc -l) &&
+	idx=$(git ls-files | wc -l) &&
+	test $wt -gt $idx
+'
+
+baz=baz
+test_export baz
+
+test_expect_success 'test_export works' '
+	echo "$foo" &&
+	test "$foo" = "$(git rev-parse HEAD)" &&
+	echo "$baz" &&
+	test "$baz" = baz
+'
+
+test_perf 'export a weird var' '
+	bar="weird # variable" &&
+	test_export bar
+'
+
+test_expect_success 'test_export works with weird vars' '
+	echo "$bar" &&
+	test "$bar" = "weird # variable"
+'
+
+test_perf 'important variables available in subshells' '
+	test -n "$HOME" &&
+	test -n "$TEST_DIRECTORY" &&
+	test -n "$TRASH_DIRECTORY" &&
+	test -n "$GIT_BUILD_DIR"
+'
+
+test_perf 'test-lib-functions correctly loaded in subshells' '
+	: >a &&
+	test_path_is_file a &&
+	: >b &&
+	test_cmp a b
+'
+
+test_done
diff --git a/t/perf/p0001-rev-list.sh b/t/perf/p0001-rev-list.sh
new file mode 100755
index 0000000000..16359d51ae
--- /dev/null
+++ b/t/perf/p0001-rev-list.sh
@@ -0,0 +1,29 @@
+#!/bin/sh
+
+test_description="Tests history walking performance"
+
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+test_perf 'rev-list --all' '
+	git rev-list --all >/dev/null
+'
+
+test_perf 'rev-list --all --objects' '
+	git rev-list --all --objects >/dev/null
+'
+
+test_expect_success 'create new unreferenced commit' '
+	commit=$(git commit-tree HEAD^{tree} -p HEAD)
+'
+
+test_perf 'rev-list $commit --not --all' '
+	git rev-list $commit --not --all >/dev/null
+'
+
+test_perf 'rev-list --objects $commit --not --all' '
+	git rev-list --objects $commit --not --all >/dev/null
+'
+
+test_done
diff --git a/t/perf/p0002-read-cache.sh b/t/perf/p0002-read-cache.sh
new file mode 100755
index 0000000000..9180ae9343
--- /dev/null
+++ b/t/perf/p0002-read-cache.sh
@@ -0,0 +1,14 @@
+#!/bin/sh
+
+test_description="Tests performance of reading the index"
+
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+count=1000
+test_perf "read_cache/discard_cache $count times" "
+	test-read-cache $count
+"
+
+test_done
diff --git a/t/perf/p3404-rebase-interactive.sh b/t/perf/p3404-rebase-interactive.sh
new file mode 100755
index 0000000000..88f47de282
--- /dev/null
+++ b/t/perf/p3404-rebase-interactive.sh
@@ -0,0 +1,36 @@
+#!/bin/sh
+
+test_description='Tests rebase -i performance'
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+# This commit merges a sufficiently long topic branch for reasonable
+# performance testing
+branch_merge=ba5312da19c6fdb6c6747d479f58932aae6e900c^{commit}
+export branch_merge
+
+git rev-parse --verify $branch_merge >/dev/null 2>&1 || {
+	skip_all='skipping because $branch_merge was not found'
+	test_done
+}
+
+write_script swap-first-two.sh <<\EOF
+case "$1" in
+*/COMMIT_EDITMSG)
+	mv "$1" "$1".bak &&
+	sed -e '1{h;d}' -e 2G <"$1".bak >"$1"
+	;;
+esac
+EOF
+
+test_expect_success 'setup' '
+	git config core.editor "\"$PWD"/swap-first-two.sh\" &&
+	git checkout -f $branch_merge^2
+'
+
+test_perf 'rebase -i' '
+	git rebase -i $branch_merge^
+'
+
+test_done
diff --git a/t/perf/p4000-diff-algorithms.sh b/t/perf/p4000-diff-algorithms.sh
new file mode 100755
index 0000000000..7e00c9da47
--- /dev/null
+++ b/t/perf/p4000-diff-algorithms.sh
@@ -0,0 +1,29 @@
+#!/bin/sh
+
+test_description="Tests diff generation performance"
+
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+test_perf 'log -3000 (baseline)' '
+	git log -3000 >/dev/null
+'
+
+test_perf 'log --raw -3000 (tree-only)' '
+	git log --raw -3000 >/dev/null
+'
+
+test_perf 'log -p -3000 (Myers)' '
+	git log -p -3000 >/dev/null
+'
+
+test_perf 'log -p -3000 --histogram' '
+	git log -p -3000 --histogram >/dev/null
+'
+
+test_perf 'log -p -3000 --patience' '
+	git log -p -3000 --patience >/dev/null
+'
+
+test_done
diff --git a/t/perf/p4001-diff-no-index.sh b/t/perf/p4001-diff-no-index.sh
new file mode 100755
index 0000000000..683be6984f
--- /dev/null
+++ b/t/perf/p4001-diff-no-index.sh
@@ -0,0 +1,22 @@
+#!/bin/sh
+
+test_description="Test diff --no-index performance"
+
+. ./perf-lib.sh
+
+test_perf_large_repo
+test_checkout_worktree
+
+file1=$(git ls-files | tail -n 2 | head -1)
+file2=$(git ls-files | tail -n 1 | head -1)
+
+test_expect_success "empty files, so they take no time to diff" "
+	echo >$file1 &&
+	echo >$file2
+"
+
+test_perf "diff --no-index" "
+	git diff --no-index $file1 $file2 >/dev/null
+"
+
+test_done
diff --git a/t/perf/p4211-line-log.sh b/t/perf/p4211-line-log.sh
new file mode 100755
index 0000000000..3d074b0e41
--- /dev/null
+++ b/t/perf/p4211-line-log.sh
@@ -0,0 +1,34 @@
+#!/bin/sh
+
+test_description='Tests log -L performance'
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+# Pick a file to log pseudo-randomly.  The sort key is the blob hash,
+# so it is stable.
+test_expect_success 'select a file' '
+	git ls-tree HEAD | grep ^100644 |
+	sort -k 3 | head -1 | cut -f 2 >filelist
+'
+
+file=$(cat filelist)
+export file
+
+test_perf 'git rev-list --topo-order (baseline)' '
+	git rev-list --topo-order HEAD >/dev/null
+'
+
+test_perf 'git log --follow (baseline for -M)' '
+	git log --oneline --follow -- "$file" >/dev/null
+'
+
+test_perf 'git log -L' '
+	git log -L 1:"$file" >/dev/null
+'
+
+test_perf 'git log -M -L' '
+	git log -M -L 1:"$file" >/dev/null
+'
+
+test_done
diff --git a/t/perf/p5302-pack-index.sh b/t/perf/p5302-pack-index.sh
new file mode 100755
index 0000000000..5ee9211f98
--- /dev/null
+++ b/t/perf/p5302-pack-index.sh
@@ -0,0 +1,40 @@
+#!/bin/sh
+
+test_description="Tests index-pack performance"
+
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+test_expect_success 'repack' '
+	git repack -ad &&
+	PACK=$(ls .git/objects/pack/*.pack | head -n1) &&
+	test -f "$PACK" &&
+	export PACK
+'
+
+test_perf 'index-pack 0 threads' '
+	GIT_DIR=t1 git index-pack --threads=1 --stdin < $PACK
+'
+
+test_perf 'index-pack 1 thread ' '
+	GIT_DIR=t2 GIT_FORCE_THREADS=1 git index-pack --threads=1 --stdin < $PACK
+'
+
+test_perf 'index-pack 2 threads' '
+	GIT_DIR=t3 git index-pack --threads=2 --stdin < $PACK
+'
+
+test_perf 'index-pack 4 threads' '
+	GIT_DIR=t4 git index-pack --threads=4 --stdin < $PACK
+'
+
+test_perf 'index-pack 8 threads' '
+	GIT_DIR=t5 git index-pack --threads=8 --stdin < $PACK
+'
+
+test_perf 'index-pack default number of threads' '
+	GIT_DIR=t6 git index-pack --stdin < $PACK
+'
+
+test_done
diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh
new file mode 100755
index 0000000000..de2a224a36
--- /dev/null
+++ b/t/perf/p5310-pack-bitmaps.sh
@@ -0,0 +1,60 @@
+#!/bin/sh
+
+test_description='Tests pack performance using bitmaps'
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+# note that we do everything through config,
+# since we want to be able to compare bitmap-aware
+# git versus non-bitmap git
+#
+# We intentionally use the deprecated pack.writebitmaps
+# config so that we can test against older versions of git.
+test_expect_success 'setup bitmap config' '
+	git config pack.writebitmaps true &&
+	git config pack.writebitmaphashcache true
+'
+
+test_perf 'repack to disk' '
+	git repack -ad
+'
+
+test_perf 'simulated clone' '
+	git pack-objects --stdout --all </dev/null >/dev/null
+'
+
+test_perf 'simulated fetch' '
+	have=$(git rev-list HEAD~100 -1) &&
+	{
+		echo HEAD &&
+		echo ^$have
+	} | git pack-objects --revs --stdout >/dev/null
+'
+
+test_expect_success 'create partial bitmap state' '
+	# pick a commit to represent the repo tip in the past
+	cutoff=$(git rev-list HEAD~100 -1) &&
+	orig_tip=$(git rev-parse HEAD) &&
+
+	# now kill off all of the refs and pretend we had
+	# just the one tip
+	rm -rf .git/logs .git/refs/* .git/packed-refs &&
+	git update-ref HEAD $cutoff &&
+
+	# and then repack, which will leave us with a nice
+	# big bitmap pack of the "old" history, and all of
+	# the new history will be loose, as if it had been pushed
+	# up incrementally and exploded via unpack-objects
+	git repack -Ad &&
+
+	# and now restore our original tip, as if the pushes
+	# had happened
+	git update-ref HEAD $orig_tip
+'
+
+test_perf 'partial bitmap' '
+	git pack-objects --stdout --all </dev/null >/dev/null
+'
+
+test_done
diff --git a/t/perf/p7000-filter-branch.sh b/t/perf/p7000-filter-branch.sh
new file mode 100755
index 0000000000..15ee5d1d53
--- /dev/null
+++ b/t/perf/p7000-filter-branch.sh
@@ -0,0 +1,19 @@
+#!/bin/sh
+
+test_description='performance of filter-branch'
+. ./perf-lib.sh
+
+test_perf_default_repo
+test_checkout_worktree
+
+test_expect_success 'mark bases for tests' '
+	git tag -f tip &&
+	git tag -f base HEAD~100
+'
+
+test_perf 'noop filter' '
+	git checkout --detach tip &&
+	git filter-branch -f base..HEAD
+'
+
+test_done
diff --git a/t/perf/p7300-clean.sh b/t/perf/p7300-clean.sh
new file mode 100755
index 0000000000..7c1888a27e
--- /dev/null
+++ b/t/perf/p7300-clean.sh
@@ -0,0 +1,35 @@
+#!/bin/sh
+
+test_description="Test git-clean performance"
+
+. ./perf-lib.sh
+
+test_perf_default_repo
+test_checkout_worktree
+
+test_expect_success 'setup untracked directory with many sub dirs' '
+	rm -rf 500_sub_dirs 100000_sub_dirs clean_test_dir &&
+	mkdir 500_sub_dirs 100000_sub_dirs clean_test_dir &&
+	for i in $(test_seq 1 500)
+	do
+		mkdir 500_sub_dirs/dir$i || return $?
+	done &&
+	for i in $(test_seq 1 200)
+	do
+		cp -r 500_sub_dirs 100000_sub_dirs/dir$i || return $?
+	done
+'
+
+test_perf 'clean many untracked sub dirs, check for nested git' '
+	git clean -n -q -f -d 100000_sub_dirs/
+'
+
+test_perf 'clean many untracked sub dirs, ignore nested git' '
+	git clean -n -q -f -f -d 100000_sub_dirs/
+'
+
+test_perf 'ls-files -o' '
+	git ls-files -o
+'
+
+test_done
diff --git a/t/perf/p7810-grep.sh b/t/perf/p7810-grep.sh
new file mode 100755
index 0000000000..9f4ade639f
--- /dev/null
+++ b/t/perf/p7810-grep.sh
@@ -0,0 +1,23 @@
+#!/bin/sh
+
+test_description="git-grep performance in various modes"
+
+. ./perf-lib.sh
+
+test_perf_large_repo
+test_checkout_worktree
+
+test_perf 'grep worktree, cheap regex' '
+	git grep some_nonexistent_string || :
+'
+test_perf 'grep worktree, expensive regex' '
+	git grep "^.* *some_nonexistent_string$" || :
+'
+test_perf 'grep --cached, cheap regex' '
+	git grep --cached some_nonexistent_string || :
+'
+test_perf 'grep --cached, expensive regex' '
+	git grep --cached "^.* *some_nonexistent_string$" || :
+'
+
+test_done
diff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh
new file mode 100644
index 0000000000..773f955d4a
--- /dev/null
+++ b/t/perf/perf-lib.sh
@@ -0,0 +1,216 @@
+# Performance testing framework.  Each perf script starts much like
+# a normal test script, except it sources this library instead of
+# test-lib.sh.  See t/perf/README for documentation.
+#
+# Copyright (c) 2011 Thomas Rast
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see http://www.gnu.org/licenses/ .
+
+# do the --tee work early; it otherwise confuses our careful
+# GIT_BUILD_DIR mangling
+case "$GIT_TEST_TEE_STARTED, $* " in
+done,*)
+	# do not redirect again
+	;;
+*' --tee '*|*' --va'*)
+	mkdir -p test-results
+	BASE=test-results/$(basename "$0" .sh)
+	(GIT_TEST_TEE_STARTED=done ${SHELL-sh} "$0" "$@" 2>&1;
+	 echo $? > $BASE.exit) | tee $BASE.out
+	test "$(cat $BASE.exit)" = 0
+	exit
+	;;
+esac
+
+TEST_DIRECTORY=$(pwd)/..
+TEST_OUTPUT_DIRECTORY=$(pwd)
+if test -z "$GIT_TEST_INSTALLED"; then
+	perf_results_prefix=
+else
+	perf_results_prefix=$(printf "%s" "${GIT_TEST_INSTALLED%/bin-wrappers}" | tr -c "[a-zA-Z0-9]" "[_*]")"."
+	# make the tested dir absolute
+	GIT_TEST_INSTALLED=$(cd "$GIT_TEST_INSTALLED" && pwd)
+fi
+
+TEST_NO_CREATE_REPO=t
+TEST_NO_MALLOC_CHECK=t
+
+. ../test-lib.sh
+
+# Variables from test-lib that are normally internal to the tests; we
+# need to export them for test_perf subshells
+export TEST_DIRECTORY TRASH_DIRECTORY GIT_BUILD_DIR GIT_TEST_CMP
+
+perf_results_dir=$TEST_OUTPUT_DIRECTORY/test-results
+mkdir -p "$perf_results_dir"
+rm -f "$perf_results_dir"/$(basename "$0" .sh).subtests
+
+if test -z "$GIT_PERF_REPEAT_COUNT"; then
+	GIT_PERF_REPEAT_COUNT=3
+fi
+die_if_build_dir_not_repo () {
+	if ! ( cd "$TEST_DIRECTORY/.." &&
+		    git rev-parse --build-dir >/dev/null 2>&1 ); then
+		error "No $1 defined, and your build directory is not a repo"
+	fi
+}
+
+if test -z "$GIT_PERF_REPO"; then
+	die_if_build_dir_not_repo '$GIT_PERF_REPO'
+	GIT_PERF_REPO=$TEST_DIRECTORY/..
+fi
+if test -z "$GIT_PERF_LARGE_REPO"; then
+	die_if_build_dir_not_repo '$GIT_PERF_LARGE_REPO'
+	GIT_PERF_LARGE_REPO=$TEST_DIRECTORY/..
+fi
+
+test_perf_create_repo_from () {
+	test "$#" = 2 ||
+	error "bug in the test script: not 2 parameters to test-create-repo"
+	repo="$1"
+	source="$2"
+	source_git="$(git -C "$source" rev-parse --git-dir)"
+	objects_dir="$(git -C "$source" rev-parse --git-path objects)"
+	mkdir -p "$repo/.git"
+	(
+		cd "$source" &&
+		{ cp -Rl "$objects_dir" "$repo/.git/" 2>/dev/null ||
+			cp -R "$objects_dir" "$repo/.git/"; } &&
+		for stuff in "$source_git"/*; do
+			case "$stuff" in
+				*/objects|*/hooks|*/config|*/commondir)
+					;;
+				*)
+					cp -R "$stuff" "$repo/.git/" || exit 1
+					;;
+			esac
+		done
+	) &&
+	(
+		cd "$repo" &&
+		git init -q && {
+			test_have_prereq SYMLINKS ||
+			git config core.symlinks false
+		} &&
+		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_default_repo () {
+	test_perf_create_repo_from "${1:-$TRASH_DIRECTORY}" "$GIT_PERF_REPO"
+}
+test_perf_large_repo () {
+	if test "$GIT_PERF_LARGE_REPO" = "$GIT_BUILD_DIR"; then
+		echo "warning: \$GIT_PERF_LARGE_REPO is \$GIT_BUILD_DIR." >&2
+		echo "warning: This will work, but may not be a sufficiently large repo" >&2
+		echo "warning: for representative measurements." >&2
+	fi
+	test_perf_create_repo_from "${1:-$TRASH_DIRECTORY}" "$GIT_PERF_LARGE_REPO"
+}
+test_checkout_worktree () {
+	git checkout-index -u -a ||
+	error "git checkout-index failed"
+}
+
+# Performance tests should never fail.  If they do, stop immediately
+immediate=t
+
+# Perf tests require GNU time
+case "$(uname -s)" in Darwin) GTIME="${GTIME:-gtime}";; esac
+GTIME="${GTIME:-/usr/bin/time}"
+
+test_run_perf_ () {
+	test_cleanup=:
+	test_export_="test_cleanup"
+	export test_cleanup test_export_
+	"$GTIME" -f "%E %U %S" -o test_time.$i "$SHELL" -c '
+. '"$TEST_DIRECTORY"/test-lib-functions.sh'
+test_export () {
+	[ $# != 0 ] || return 0
+	test_export_="$test_export_\\|$1"
+	shift
+	test_export "$@"
+}
+'"$1"'
+ret=$?
+set | sed -n "s'"/'/'\\\\''/g"';s/^\\($test_export_\\)/export '"'&'"'/p" >test_vars
+exit $ret' >&3 2>&4
+	eval_ret=$?
+
+	if test $eval_ret = 0 || test -n "$expecting_failure"
+	then
+		test_eval_ "$test_cleanup"
+		. ./test_vars || error "failed to load updated environment"
+	fi
+	if test "$verbose" = "t" && test -n "$HARNESS_ACTIVE"; then
+		echo ""
+	fi
+	return "$eval_ret"
+}
+
+
+test_perf () {
+	test_start_
+	test "$#" = 3 && { test_prereq=$1; shift; } || test_prereq=
+	test "$#" = 2 ||
+	error "bug in the test script: not 2 or 3 parameters to test-expect-success"
+	export test_prereq
+	if ! test_skip "$@"
+	then
+		base=$(basename "$0" .sh)
+		echo "$test_count" >>"$perf_results_dir"/$base.subtests
+		echo "$1" >"$perf_results_dir"/$base.$test_count.descr
+		if test -z "$verbose"; then
+			printf "%s" "perf $test_count - $1:"
+		else
+			echo "perf $test_count - $1:"
+		fi
+		for i in $(test_seq 1 $GIT_PERF_REPEAT_COUNT); do
+			say >&3 "running: $2"
+			if test_run_perf_ "$2"
+			then
+				if test -z "$verbose"; then
+					printf " %s" "$i"
+				else
+					echo "* timing run $i/$GIT_PERF_REPEAT_COUNT:"
+				fi
+			else
+				test -z "$verbose" && echo
+				test_failure_ "$@"
+				break
+			fi
+		done
+		if test -z "$verbose"; then
+			echo " ok"
+		else
+			test_ok_ "$1"
+		fi
+		base="$perf_results_dir"/"$perf_results_prefix$(basename "$0" .sh)"."$test_count"
+		"$TEST_DIRECTORY"/perf/min_time.perl test_time.* >"$base".times
+	fi
+	test_finish_
+}
+
+# We extend test_done to print timings at the end (./run disables this
+# and does it after running everything)
+test_at_end_hook_ () {
+	if test -z "$GIT_PERF_AGGREGATING_LATER"; then
+		( cd "$TEST_DIRECTORY"/perf && ./aggregate.perl $(basename "$0") )
+	fi
+}
+
+test_export () {
+	export "$@"
+}
diff --git a/t/perf/run b/t/perf/run
new file mode 100755
index 0000000000..cfd70129bb
--- /dev/null
+++ b/t/perf/run
@@ -0,0 +1,82 @@
+#!/bin/sh
+
+case "$1" in
+	--help)
+		echo "usage: $0 [other_git_tree...] [--] [test_scripts]"
+		exit 0
+		;;
+esac
+
+die () {
+	echo >&2 "error: $*"
+	exit 1
+}
+
+run_one_dir () {
+	if test $# -eq 0; then
+		set -- p????-*.sh
+	fi
+	echo "=== Running $# tests in ${GIT_TEST_INSTALLED:-this tree} ==="
+	for t in "$@"; do
+		./$t $GIT_TEST_OPTS
+	done
+}
+
+unpack_git_rev () {
+	rev=$1
+	mkdir -p build/$rev
+	(cd "$(git rev-parse --show-cdup)" && git archive --format=tar $rev) |
+	(cd build/$rev && tar x)
+}
+build_git_rev () {
+	rev=$1
+	cp ../../config.mak build/$rev/config.mak
+	(cd build/$rev && make $GIT_PERF_MAKE_OPTS) ||
+	die "failed to build revision '$mydir'"
+}
+
+run_dirs_helper () {
+	mydir=${1%/}
+	shift
+	while test $# -gt 0 -a "$1" != -- -a ! -f "$1"; do
+		shift
+	done
+	if test $# -gt 0 -a "$1" = --; then
+		shift
+	fi
+	if [ ! -d "$mydir" ]; then
+		rev=$(git rev-parse --verify "$mydir" 2>/dev/null) ||
+		die "'$mydir' is neither a directory nor a valid revision"
+		if [ ! -d build/$rev ]; then
+			unpack_git_rev $rev
+		fi
+		build_git_rev $rev
+		mydir=build/$rev
+	fi
+	if test "$mydir" = .; then
+		unset GIT_TEST_INSTALLED
+	else
+		GIT_TEST_INSTALLED="$mydir/bin-wrappers"
+		export GIT_TEST_INSTALLED
+	fi
+	run_one_dir "$@"
+}
+
+run_dirs () {
+	while test $# -gt 0 -a "$1" != -- -a ! -f "$1"; do
+		run_dirs_helper "$@"
+		shift
+	done
+}
+
+GIT_PERF_AGGREGATING_LATER=t
+export GIT_PERF_AGGREGATING_LATER
+
+cd "$(dirname $0)"
+. ../../GIT-BUILD-OPTIONS
+
+if test $# = 0 -o "$1" = -- -o -f "$1"; then
+	set -- . "$@"
+fi
+run_dirs "$@"
+./aggregate.perl "$@"