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 --- fetch-pack.c | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-) (limited to 'fetch-pack.c') diff --git a/fetch-pack.c b/fetch-pack.c index fa4231fee7..6afe2f964e 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -34,6 +34,7 @@ #include "commit-graph.h" #include "sigchain.h" #include "mergesort.h" +#include "prio-queue.h" static int transfer_unpack_limit = -1; static int fetch_unpack_limit = -1; @@ -600,7 +601,7 @@ done: return count ? retval : 0; } -static struct commit_list *complete; +static struct prio_queue complete = { compare_commits_by_commit_date }; static int mark_complete(const struct object_id *oid) { @@ -608,7 +609,7 @@ static int mark_complete(const struct object_id *oid) if (commit && !(commit->object.flags & COMPLETE)) { commit->object.flags |= COMPLETE; - commit_list_insert(commit, &complete); + prio_queue_put(&complete, commit); } return 0; } @@ -625,9 +626,12 @@ static int mark_complete_oid(const char *refname UNUSED, static void mark_recent_complete_commits(struct fetch_pack_args *args, timestamp_t cutoff) { - while (complete && cutoff <= complete->item->date) { + while (complete.nr) { + struct commit *item = prio_queue_peek(&complete); + if (item->date < cutoff) + break; print_verbose(args, _("Marking %s as complete"), - oid_to_hex(&complete->item->object.oid)); + oid_to_hex(&item->object.oid)); pop_most_recent_commit(&complete, COMPLETE); } } @@ -797,7 +801,6 @@ static void mark_complete_and_common_ref(struct fetch_negotiator *negotiator, refs_for_each_rawref(get_main_ref_store(the_repository), mark_complete_oid, NULL); for_each_cached_alternate(NULL, mark_alternate_complete); - commit_list_sort_by_date(&complete); if (cutoff) mark_recent_complete_commits(args, cutoff); } -- cgit v1.2.3