Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits

From: Jeff King <peff@peff.net>
Date: Jun 10, 2013, 05:25 UTC
Message-ID: <20130610052500.GD3621@sigill.intra.peff.net>
In-Reply-To: <1370820277-30158-3-git-send-email-gitster@pobox.com>

On Sun, Jun 09, 2013 at 04:24:35PM -0700, Junio C Hamano wrote:

Show 11 quoted lines

> Traditionally we used a singly linked list of commits to hold a set
> of in-flight commits while traversing history.  The most typical use
> of the list is to add commits that are newly discovered to it, keep
> the list sorted by commit timestamp, pick up the newest one from the
> list, and keep digging.  The cost of keeping the singly linked list
> sorted is nontrivial, and this typical use pattern better matches a
> priority queue.
> 
> Introduce a commit-queue structure, that can be used either as a
> LIFO stack, or a priority queue.  This will be used in the next
> patch to hold in-flight commits during sort-in-topological-order.

Great. You may recall I had a similar patch or year or two back, in an attempt to fix some of the O(n^2) places (e.g., in fetch-pack's mark_complete). We ended up dropping it because duplicate removal kept "n" small enough for common cases, and most of the commit_list users depend on doing cheap splicing and other linked-list operations.

It may be worth looking again for other places to use this over commit_list, but even the caller you are introducing here justifies its presence.

Also, I wrote some basic tests to cover the priority queue as a unit. I can rebase them on your commit if you are interested.

A few comments on the code itself:

> +void commit_queue_put(struct commit_queue *queue, struct commit *commit)

Is it worth making this "struct commit *" a void pointer, and handling arbitrary items in our priority queue? The compare function should be the only thing that dereferences them.

I do not have any non-commit priority queue use in mind, but I do not think it adds any complexity in this case.

Show 6 quoted lines

> +	/* Bubble up the new one */
> +	for (ix = queue->nr - 1; ix; ix = parent) {
> +		parent = (ix - 1) / 2;
> +		if (compare(queue->array[parent], queue->array[ix],
> +			    queue->cb_data) < 0)
> +			break;

In my implementation, I stopped on "compare() <= 0". It is late and my mind is fuzzy, but I recall that heaps are never stable with respect to insertion order, so I don't think it would matter.

-Peff