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

[Jeff King <peff@peff.net>]

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

> 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.

> +	/* 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