René Scharfe <l.s.r@xxxxxx> writes:
> 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.
> 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.
> 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;
> }
