From d6ec08788e667d4f556e9c2d97bbd7adb7e582be Mon Sep 17 00:00:00 2001 From: René Scharfe Date: Fri, 18 Jul 2025 11:39:06 +0200 Subject: commit: convert pop_most_recent_commit() to prio_queue MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit pop_most_recent_commit() calls commit_list_insert_by_date() for parent commits, which is itself called in a loop. This can lead to quadratic complexity if there are many merges. Replace the commit_list with a prio_queue to ensure logarithmic worst case complexity and convert all three users. Add a performance test that exercises one of them using a pathological history that consists of 50% merges and 50% root commits to demonstrate the speedup: Test v2.50.1 HEAD ---------------------------------------------------------------------- 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9% Alas, sane histories don't benefit from the conversion much, and traversing Git's own history takes a 1% performance hit on my machine: $ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision' Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s] Range (min … max): 1.067 s … 1.078 s 10 runs Benchmark 2: ./git rev-parse :/^Initial.revision Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s] Range (min … max): 1.074 s … 1.083 s 10 runs Summary ./git_2.50.1 rev-parse :/^Initial.revision ran 1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision Signed-off-by: René Scharfe Signed-off-by: Junio C Hamano --- object-name.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'object-name.c') diff --git a/object-name.c b/object-name.c index 9288b2dd24..8a787b3ff3 100644 --- a/object-name.c +++ b/object-name.c @@ -28,6 +28,7 @@ #include "commit-reach.h" #include "date.h" #include "object-file-convert.h" +#include "prio-queue.h" static int get_oid_oneline(struct repository *r, const char *, struct object_id *, const struct commit_list *); @@ -1457,7 +1458,7 @@ static int get_oid_oneline(struct repository *r, const char *prefix, struct object_id *oid, const struct commit_list *list) { - struct commit_list *copy = NULL, **copy_tail = © + struct prio_queue copy = { compare_commits_by_commit_date }; const struct commit_list *l; int found = 0; int negative = 0; @@ -1479,9 +1480,9 @@ static int get_oid_oneline(struct repository *r, for (l = list; l; l = l->next) { l->item->object.flags |= ONELINE_SEEN; - copy_tail = &commit_list_insert(l->item, copy_tail)->next; + prio_queue_put(©, l->item); } - while (copy) { + while (copy.nr) { const char *p, *buf; struct commit *commit; int matches; @@ -1503,7 +1504,7 @@ static int get_oid_oneline(struct repository *r, regfree(®ex); for (l = list; l; l = l->next) clear_commit_marks(l->item, ONELINE_SEEN); - free_commit_list(copy); + clear_prio_queue(©); return found ? 0 : -1; } @@ -2057,7 +2058,6 @@ static enum get_oid_result get_oid_with_context_1(struct repository *repo, cb.list = &list; refs_for_each_ref(get_main_ref_store(repo), handle_one_ref, &cb); refs_head_ref(get_main_ref_store(repo), handle_one_ref, &cb); - commit_list_sort_by_date(&list); ret = get_oid_oneline(repo, name + 2, oid, list); free_commit_list(list); -- cgit v1.2.3