Re: [PATCH 3/3] commit: use prio_queue_replace() in pop_most_recent_commit()
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Jul 15, 2025, 20:43 UTC
- Message-ID
- <xmqqh5zdgp6r.fsf@gitster.g>
- In-Reply-To
- <aa89082f-34ab-4ec7-bdce-70f0a33815e6@web.de>
René Scharfe <l.s.r@web.de> writes:
Show 6 quoted lines
> 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):
Given that our history has more merges than other projects, and the _replace() optimization would help primarily single-strand-of-pearls (and the first parent of a merge), that result is very good.
Show 11 quoted lines
> 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;Briefly I was puzzled by the name (I would have called first-parent since the logic was "we treat first parent specially by using replace instead of get/put"), but the variable signals "instead of get to remove the item from the queue, we just peeked, so we need to remove it later" with its name, which is understandable.
Show 19 quoted lines
> 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;
> }