Subject: [PATCH v2 16/18] commit-reach: replace ref_newer logic

From: Derrick Stolee <[email-masked]>
Date: Fri, 20 Jul 2018 16:33:27 +0000

The ref_newer method is used by 'git push' to check if a force-push is
required. This method does not use any kind of cutoff when walking, so
in the case of a force-push will walk all reachable commits.

The is_descendant_of method already uses paint_down_to_common along with
cutoffs. By translating the ref_newer arguments into the commit and
commit_list required by is_descendant_of, we can have one fewer commit
walk and also improve our performance!

For a copy of the Linux repository, 'test-tool reach ref_newer' presents
the following improvements with the specified input. In the case that
ref_newer returns 1, there is no improvement. The improvement is in the
second case where ref_newer returns 0.

Input:
A:v4.9
B:v3.19

Before: 0.09 s
 After: 0.09 s

To test the negative case, add a new commit with parent v3.19,
regenerate the commit-graph, and then run with B pointing at that
commit.

Before: 0.43 s
 After: 0.09 s

Signed-off-by: Derrick Stolee <[email-masked]>
---
 commit-reach.c | 26 +++-----------------------
 1 file changed, 3 insertions(+), 23 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 940fbf2e17..f5858944fd 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -366,20 +366,11 @@ void reduce_heads_replace(struct commit_list **heads)
 	*heads = result;
 }
 
-static void unmark_and_free(struct commit_list *list, unsigned int mark)
-{
-	while (list) {
-		struct commit *commit = pop_commit(&list);
-		commit->object.flags &= ~mark;
-	}
-}
-
 int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
 {
 	struct object *o;
 	struct commit *old_commit, *new_commit;
-	struct commit_list *list, *used;
-	int found = 0;
+	struct commit_list *old_commit_list = NULL;
 
 	/*
 	 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
@@ -400,19 +391,8 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
 	if (parse_commit(new_commit) < 0)
 		return 0;
 
-	used = list = NULL;
-	commit_list_insert(new_commit, &list);
-	while (list) {
-		new_commit = pop_most_recent_commit(&list, TMP_MARK);
-		commit_list_insert(new_commit, &used);
-		if (new_commit == old_commit) {
-			found = 1;
-			break;
-		}
-	}
-	unmark_and_free(list, TMP_MARK);
-	unmark_and_free(used, TMP_MARK);
-	return found;
+	commit_list_insert(old_commit, &old_commit_list);
+	return is_descendant_of(new_commit, old_commit_list);
 }
 
 /*
-- 
2.18.0.118.gd4f65b8d14