summaryrefslogtreecommitdiff
path: root/commit.c
diff options
context:
space:
mode:
authorRené Scharfe <l.s.r@web.de>2025-07-18 11:39:06 +0200
committerJunio C Hamano <gitster@pobox.com>2025-07-22 07:28:23 -0700
commitd6ec08788e667d4f556e9c2d97bbd7adb7e582be (patch)
tree833bcbff1f6ebaf69daac4faabd4e23969f7b064 /commit.c
parent16bd9f20a403117f2e0d9bcda6c6e621d3763e77 (diff)
commit: convert pop_most_recent_commit() to prio_queue
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 <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'commit.c')
-rw-r--r--commit.c7
1 files changed, 4 insertions, 3 deletions
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;
}