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

[Junio C Hamano <gitster@pobox.com>]

René Scharfe <l.s.r@web.de> 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;
>  }