rebase: avoid computing unnecessary patch IDs

The `rebase` family of Git commands avoid applying patches that were
already integrated upstream. They do that by using the revision walking
option that computes the patch IDs of the two sides of the rebase
(local-only patches vs upstream-only ones) and skipping those local
patches whose patch ID matches one of the upstream ones.

In many cases, this causes unnecessary churn, as already the set of
paths touched by a given commit would suffice to determine that an
upstream patch has no local equivalent.

This hurts performance in particular when there are a lot of upstream
patches, and/or large ones.

Therefore, let's introduce the concept of a "diff-header-only" patch ID,
compare those first, and only evaluate the "full" patch ID lazily.

Please note that in contrast to the "full" patch IDs, those
"diff-header-only" patch IDs are prone to collide with one another, as
adjacent commits frequently touch the very same files. Hence we now
have to be careful to allow multiple hash entries with the same hash.
We accomplish that by using the hashmap_add() function that does not even
test for hash collisions.  This also allows us to evaluate the full patch ID
lazily, i.e. only when we found commits with matching diff-header-only
patch IDs.

We add a performance test that demonstrates ~1-6% improvement.  In
practice this will depend on various factors such as how many upstream
changes and how big those changes are along with whether file system
caches are cold or warm.  As Git's test suite has no way of catching
performance regressions, we also add a regression test that verifies
that the full patch ID computation is skipped when the diff-header-only
computation suffices.

Signed-off-by: Kevin Willford <kcwillford@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/builtin/log.c b/builtin/log.c
index 099f4f7be92c6d4371dcc8cba1322351c6840439..e36457288a71035cbcdd8b57f5ef0145204be512 100644 (file)
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -1315,7 +1315,7 @@ static void prepare_bases(struct base_tree_info *bases,
                struct object_id *patch_id;
                if (commit->util)
                        continue;
                struct object_id *patch_id;
                if (commit->util)
                        continue;

-               if (commit_patch_id(commit, &diffopt, sha1))
+               if (commit_patch_id(commit, &diffopt, sha1, 0))

                        die(_("cannot get patch id"));
                ALLOC_GROW(bases->patch_id, bases->nr_patch_id + 1, bases->alloc_patch_id);
                patch_id = bases->patch_id + bases->nr_patch_id;
                        die(_("cannot get patch id"));
                ALLOC_GROW(bases->patch_id, bases->nr_patch_id + 1, bases->alloc_patch_id);
                patch_id = bases->patch_id + bases->nr_patch_id;

diff --git a/patch-ids.c b/patch-ids.c
index 69a14a3b50eeb62d4ec4561fe5395db12b06b366..082412aca66be6ce826034c5177e2f7f4b3bda58 100644 (file)
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -5,7 +5,7 @@
 #include "patch-ids.h"
 
 int commit_patch_id(struct commit *commit, struct diff_options *options,
 #include "patch-ids.h"
 
 int commit_patch_id(struct commit *commit, struct diff_options *options,

-                   unsigned char *sha1)
+                   unsigned char *sha1, int diff_header_only)

 {
        if (commit->parents)
                diff_tree_sha1(commit->parents->item->object.oid.hash,
 {
        if (commit->parents)
                diff_tree_sha1(commit->parents->item->object.oid.hash,


@@ -13,13 +13,31 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,
        else
                diff_root_tree_sha1(commit->object.oid.hash, "", options);
        diffcore_std(options);
        else
                diff_root_tree_sha1(commit->object.oid.hash, "", options);
        diffcore_std(options);

-       return diff_flush_patch_id(options, sha1, 0);
+       return diff_flush_patch_id(options, sha1, diff_header_only);

 }
 
 }
 

+/*
+ * When we cannot load the full patch-id for both commits for whatever
+ * reason, the function returns -1 (i.e. return error(...)). Despite
+ * the "cmp" in the name of this function, the caller only cares about
+ * the return value being zero (a and b are equivalent) or non-zero (a
+ * and b are different), and returning non-zero would keep both in the
+ * result, even if they actually were equivalent, in order to err on
+ * the side of safety.  The actual value being negative does not have
+ * any significance; only that it is non-zero matters.
+ */

 static int patch_id_cmp(struct patch_id *a,
                        struct patch_id *b,
 static int patch_id_cmp(struct patch_id *a,
                        struct patch_id *b,

-                       void *keydata)
+                       struct diff_options *opt)

 {
 {

+       if (is_null_sha1(a->patch_id) &&
+           commit_patch_id(a->commit, opt, a->patch_id, 0))
+               return error("Could not get patch ID for %s",
+                       oid_to_hex(&a->commit->object.oid));
+       if (is_null_sha1(b->patch_id) &&
+           commit_patch_id(b->commit, opt, b->patch_id, 0))
+               return error("Could not get patch ID for %s",
+                       oid_to_hex(&b->commit->object.oid));

        return hashcmp(a->patch_id, b->patch_id);
 }
 
        return hashcmp(a->patch_id, b->patch_id);
 }
 


@@ -43,11 +61,13 @@ static int init_patch_id_entry(struct patch_id *patch,
                               struct commit *commit,
                               struct patch_ids *ids)
 {
                               struct commit *commit,
                               struct patch_ids *ids)
 {

+       unsigned char header_only_patch_id[GIT_SHA1_RAWSZ];
+

        patch->commit = commit;
        patch->commit = commit;

-       if (commit_patch_id(commit, &ids->diffopts, patch->patch_id))
+       if (commit_patch_id(commit, &ids->diffopts, header_only_patch_id, 1))

                return -1;
 
                return -1;
 

-       hashmap_entry_init(patch, sha1hash(patch->patch_id));
+       hashmap_entry_init(patch, sha1hash(header_only_patch_id));

        return 0;
 }
 
        return 0;
 }
 


@@ -60,7 +80,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,
        if (init_patch_id_entry(&patch, commit, ids))
                return NULL;
 
        if (init_patch_id_entry(&patch, commit, ids))
                return NULL;
 

-       return hashmap_get(&ids->patches, &patch, NULL);
+       return hashmap_get(&ids->patches, &patch, &ids->diffopts);

 }
 
 struct patch_id *add_commit_patch_id(struct commit *commit,
 }
 
 struct patch_id *add_commit_patch_id(struct commit *commit,

diff --git a/patch-ids.h b/patch-ids.h
index dea1ecda48ba7a43cc56e103eec61d8e12bedd10..0f34ea11eadffea14620ea2ad45d69894469aef7 100644 (file)
--- a/patch-ids.h
+++ b/patch-ids.h
@@ -13,7 +13,7 @@ struct patch_ids {
 };
 
 int commit_patch_id(struct commit *commit, struct diff_options *options,
 };
 
 int commit_patch_id(struct commit *commit, struct diff_options *options,

-                   unsigned char *sha1);
+                   unsigned char *sha1, int);

 int init_patch_ids(struct patch_ids *);
 int free_patch_ids(struct patch_ids *);
 struct patch_id *add_commit_patch_id(struct commit *, struct patch_ids *);
 int init_patch_ids(struct patch_ids *);
 int free_patch_ids(struct patch_ids *);
 struct patch_id *add_commit_patch_id(struct commit *, struct patch_ids *);

diff --git a/t/perf/p3400-rebase.sh b/t/perf/p3400-rebase.sh
new file mode 100644 (file)
index 0000000..b3e7d52
--- /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 28d4f6b259c1696435698cb3826c837c8eaf90e3..1408b608eb030f0e6bcc3d531aad426da5f06b12 100755 (executable)
--- 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
 '
 
        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
 test_done