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.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index e915b2b9a1..0200759aaa 100644 --- a/commit.c +++ b/commit.c @@ -31,6 +31,7 @@ #include "parse.h" #include "object-file.h" #include "object-file-convert.h" +#include "prio-queue.h" static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **); @@ -738,17 +739,17 @@ void commit_list_sort_by_date(struct commit_list **list) commit_list_sort(list, commit_list_compare_by_date); } -struct commit *pop_most_recent_commit(struct commit_list **list, +struct commit *pop_most_recent_commit(struct prio_queue *queue, unsigned int mark) { - struct commit *ret = pop_commit(list); + struct commit *ret = prio_queue_get(queue); struct commit_list *parents = ret->parents; while (parents) { struct commit *commit = parents->item; if (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) { commit->object.flags |= mark; - commit_list_insert_by_date(commit, list); + prio_queue_put(queue, commit); } parents = parents->next; } -- cgit v1.2.3