[PATCH 3/3] commit: use prio_queue_replace() in pop_most_recent_commit()

From: René Scharfe <l.s.r@web.de>
Date: Jul 15, 2025, 14:51 UTC
Message-ID: <aa89082f-34ab-4ec7-bdce-70f0a33815e6@web.de>
In-Reply-To: <bc079b3c-a472-4f5d-95ca-390f9de25196@web.de>

Optimize pop_most_recent_commit() by adding the first parent using the more efficient prio_queue_peek() and prio_queue_replace() instead of prio_queue_get() and prio_queue_put().

On my machine this neutralizes the performance hit it took in Git's own repository when we converted it to prio_queue two patches ago (git_pq):

   $ hyperfine -w3 -L git ./git_2.50.1,./git_pq,./git '{git} rev-parse :/^Initial.revision'
   Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision
     Time (mean ± σ):      1.073 s ±  0.003 s    [User: 1.053 s, System: 0.019 s]
     Range (min … max):    1.069 s …  1.078 s    10 runs

   Benchmark 2: ./git_pq rev-parse :/^Initial.revision
     Time (mean ± σ):      1.077 s ±  0.002 s    [User: 1.057 s, System: 0.018 s]
     Range (min … max):    1.072 s …  1.079 s    10 runs

   Benchmark 3: ./git rev-parse :/^Initial.revision
     Time (mean ± σ):      1.069 s ±  0.003 s    [User: 1.049 s, System: 0.018 s]
     Range (min … max):    1.065 s …  1.074 s    10 runs

   Summary
     ./git rev-parse :/^Initial.revision ran
       1.00 ± 0.00 times faster than ./git_2.50.1 rev-parse :/^Initial.revision
       1.01 ± 0.00 times faster than ./git_pq rev-parse :/^Initial.revision

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 commit.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/commit.c b/commit.c
index 0200759aaa..8244221b30 100644
--- a/commit.c
+++ b/commit.c
@@ -742,17 +742,24 @@ void commit_list_sort_by_date(struct commit_list **list)
 struct commit *pop_most_recent_commit(struct prio_queue *queue,
 				      unsigned int mark)
 {
-	struct commit *ret = prio_queue_get(queue);
+	struct commit *ret = prio_queue_peek(queue);
+	int delete_pending = 1;
 	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;
-			prio_queue_put(queue, commit);
+			if (delete_pending)
+				prio_queue_replace(queue, commit);
+			else
+				prio_queue_put(queue, commit);
+			delete_pending = 0;
 		}
 		parents = parents->next;
 	}
+	if (delete_pending)
+		prio_queue_get(queue);
 	return ret;
 }

-- 
2.50.1