path: root/patch-ids.c
diff options
authorKevin Willford <>2016-07-29 16:19:20 (GMT)
committerJunio C Hamano <>2016-08-11 21:39:16 (GMT)
commitb3dfeebb92630c54db1e4f03dbcff0e05208c4c1 (patch)
treec994a03fe0911554245be1e40f4f68c2764ae922 /patch-ids.c
parent3e8e32c32ef8e49bcfd715837d51aca30925fdfe (diff)
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 <> Signed-off-by: Junio C Hamano <>
Diffstat (limited to 'patch-ids.c')
1 files changed, 26 insertions, 6 deletions
diff --git a/patch-ids.c b/patch-ids.c
index 69a14a3..082412a 100644
--- 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,
- unsigned char *sha1)
+ unsigned char *sha1, int diff_header_only)
if (commit->parents)
@@ -13,13 +13,31 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,
diff_root_tree_sha1(commit->object.oid.hash, "", 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,
- 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);
@@ -43,11 +61,13 @@ static int init_patch_id_entry(struct patch_id *patch,
struct commit *commit,
struct patch_ids *ids)
+ unsigned char header_only_patch_id[GIT_SHA1_RAWSZ];
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;
- hashmap_entry_init(patch, sha1hash(patch->patch_id));
+ hashmap_entry_init(patch, sha1hash(header_only_patch_id));
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;
- 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,