Merge branch 'kw/patch-ids-optim'

When "git rebase" tries to compare set of changes on the updated
upstream and our own branch, it computes patch-id for all of these
changes and attempts to find matches. This has been optimized by
lazily computing the full patch-id (which is expensive) to be
compared only for changes that touch the same set of paths.

* kw/patch-ids-optim:
  rebase: avoid computing unnecessary patch IDs
  patch-ids: add flag to create the diff patch id using header only data
  patch-ids: replace the seen indicator with a commit pointer
  patch-ids: stop using a hand-rolled hashmap implementation

2 files changed, 57 insertions, 0 deletions

diff --git a/t/perf/p3400-rebase.sh b/t/perf/p3400-rebase.sh
new file mode 100644
index 0000000000..b3e7d525d2
--- /dev/null
+++ b/t/perf/p3400-rebase.sh
@@ -0,0 +1,36 @@
+#!/bin/sh
+
+test_description='Tests rebase performance'
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+test_expect_success 'setup' '
+	git checkout -f -b base &&
+	git checkout -b to-rebase &&
+	git checkout -b upstream &&
+	for i in $(seq 100)
+	do
+		# simulate huge diffs
+		echo change$i >unrelated-file$i &&
+		seq 1000 >>unrelated-file$i &&
+		git add unrelated-file$i &&
+		test_tick &&
+		git commit -m commit$i unrelated-file$i &&
+		echo change$i >unrelated-file$i &&
+		seq 1000 | tac >>unrelated-file$i &&
+		git add unrelated-file$i &&
+		test_tick &&
+		git commit -m commit$i-reverse unrelated-file$i ||
+		break
+	done &&
+	git checkout to-rebase &&
+	test_commit our-patch interesting-file
+'
+
+test_perf 'rebase on top of a lot of unrelated changes' '
+	git rebase --onto upstream HEAD^ &&
+	git rebase --onto base HEAD^
+'
+
+test_done
diff --git a/t/t6007-rev-list-cherry-pick-file.sh b/t/t6007-rev-list-cherry-pick-file.sh
index 28d4f6b259..1408b608eb 100755
--- a/t/t6007-rev-list-cherry-pick-file.sh
+++ b/t/t6007-rev-list-cherry-pick-file.sh
@@ -207,4 +207,25 @@ test_expect_success '--count --left-right' '
 	test_cmp expect actual
 '
 
+# Corrupt the object store deliberately to make sure
+# the object is not even checked for its existence.
+remove_loose_object () {
+	sha1="$(git rev-parse "$1")" &&
+	remainder=${sha1#??} &&
+	firsttwo=${sha1%$remainder} &&
+	rm .git/objects/$firsttwo/$remainder
+}
+
+test_expect_success '--cherry-pick avoids looking at full diffs' '
+	git checkout -b shy-diff &&
+	test_commit dont-look-at-me &&
+	echo Hello >dont-look-at-me.t &&
+	test_tick &&
+	git commit -m tip dont-look-at-me.t &&
+	git checkout -b mainline HEAD^ &&
+	test_commit to-cherry-pick &&
+	remove_loose_object shy-diff^:dont-look-at-me.t &&
+	git rev-list --cherry-pick ...shy-diff
+'
+
 test_done