[RFC PATCH 12/13] commit-reach: use is_descendant_of for ref_newer
- From
Derrick Stolee <dstolee@microsoft.com>
- Date
- Jun 29, 2018, 16:13 UTC
- Message-ID
- <20180629161223.229661-13-dstolee@microsoft.com>
- In-Reply-To
- <20180629161223.229661-1-dstolee@microsoft.com>
The ref_newer method is used by 'git push' to detect if a force-push is requried. 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.
Input ----- A:v4.9 B:v3.19
Before: 0.11 s After: 0.10 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.52 s After: 0.12 s
Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- commit-reach.c | 17 ++++------------- commit.c | 7 +++++-- commit.h | 6 +++++- fetch-pack.c | 3 ++- sha1-name.c | 3 ++- walker.c | 3 ++- 6 files changed, 20 insertions(+), 19 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c index 8e24455d9f..249e9a4fac 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -376,7 +376,7 @@ 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; + struct commit_list *list = NULL; int found = 0; /* @@ -396,18 +396,9 @@ 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); + commit_list_insert(old_commit, &list); + found = is_descendant_of(new_commit, list); + free_commit_list(list); return found; } diff --git a/commit.c b/commit.c index d4ddaf4879..9870682673 100644 --- a/commit.c +++ b/commit.c @@ -556,7 +556,8 @@ void commit_list_sort_by_date(struct commit_list **list) } struct commit *pop_most_recent_commit(struct commit_list **list, - unsigned int mark) + unsigned int mark, + uint32_t min_generation) { struct commit *ret = pop_commit(list); struct commit_list *parents = ret->parents; @@ -565,7 +566,9 @@ struct commit *pop_most_recent_commit(struct commit_list **list, struct commit *commit = parents->item; if (!parse_commit(commit) && !(commit->object.flags & mark)) { commit->object.flags |= mark; - commit_list_insert_by_date(commit, list); + + if (commit->generation >= min_generation) + commit_list_insert_by_date(commit, list); } parents = parents->next; } diff --git a/commit.h b/commit.h index 7e0f273720..5eaeded5e2 100644 --- a/commit.h +++ b/commit.h @@ -159,9 +159,13 @@ extern const char *skip_blank_lines(const char *msg); /** Removes the first commit from a list sorted by date, and adds all * of its parents. + * + * The parents are not added if their generation number is strictly + * lower than min_generation. **/ struct commit *pop_most_recent_commit(struct commit_list **list, - unsigned int mark); + unsigned int mark, + uint32_t min_generation); struct commit *pop_commit(struct commit_list **stack); diff --git a/fetch-pack.c b/fetch-pack.c index a320ce9872..351e3d4bcd 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -600,7 +600,8 @@ static void mark_recent_complete_commits(struct fetch_pack_args *args, while (complete && cutoff <= complete->item->date) { print_verbose(args, _("Marking %s as complete"), oid_to_hex(&complete->item->object.oid)); - pop_most_recent_commit(&complete, COMPLETE); + pop_most_recent_commit(&complete, COMPLETE, + GENERATION_NUMBER_ZERO); } } diff --git a/sha1-name.c b/sha1-name.c index 60d9ef3c7e..471a54464d 100644 --- a/sha1-name.c +++ b/sha1-name.c @@ -1141,7 +1141,8 @@ static int get_oid_oneline(const char *prefix, struct object_id *oid, struct commit *commit; int matches; - commit = pop_most_recent_commit(&list, ONELINE_SEEN); + commit = pop_most_recent_commit(&list, ONELINE_SEEN, + GENERATION_NUMBER_ZERO); if (!parse_object(&commit->object.oid)) continue; buf = get_commit_buffer(commit, NULL); diff --git a/walker.c b/walker.c index 0b162a09b9..e243fc8768 100644 --- a/walker.c +++ b/walker.c @@ -78,7 +78,8 @@ static int process_commit(struct walker *walker, struct commit *commit) return -1; while (complete && complete->item->date >= commit->date) { - pop_most_recent_commit(&complete, COMPLETE); + pop_most_recent_commit(&complete, COMPLETE, + GENERATION_NUMBER_ZERO); } if (commit->object.flags & COMPLETE)
-- 2.18.0.118.gd4f65b8d14