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

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.

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