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 --- commit.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'commit.h') diff --git a/commit.h b/commit.h index 70c870dae4..9630c076d6 100644 --- a/commit.h +++ b/commit.h @@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r, const char *skip_blank_lines(const char *msg); -/** Removes the first commit from a list sorted by date, and adds all - * of its parents. - **/ -struct commit *pop_most_recent_commit(struct commit_list **list, +struct prio_queue; + +/* Removes the first commit from a prio_queue and adds its parents. */ +struct commit *pop_most_recent_commit(struct prio_queue *queue, unsigned int mark); struct commit *pop_commit(struct commit_list **stack); -- cgit v1.2.3