Re: [PATCH v2 3/4] sort-in-topological-order: use commit-queue

[Jeff King <peff@peff.net>]

On Mon, Jun 10, 2013 at 12:27:31AM -0700, Junio C Hamano wrote:

> > Around the same time, though, René wrote the linked-list merge sort that
> > powers commit_list_sort_by_date. And topo-sort learned to do O(1)
> > insertions into the unsorted list, and then one O(n log n) sort.
> 
> Yes, but that only affects the "sort the work queue in date order"
> before entering the main loop, and maintenance of work queue as we
> dig along still is "find the place to put this in the date-order
> sorted linked list", no?

Ah, you're right. I was thinking that we saw all of the commits up
front and then sorted. And we do, but we still keep a separate list in
the work queue.

So I think it may just be the case that "N" does not get very big here
(the width of the graph), so log(N) versus (N) does not make a big
difference.

> I've been disturbed every time I saw the commit_list insertion
> function that does a small allocation which will be freed fairly
> often and have been wondering if we can rewrite it with custom slab
> allocator, but not using linked list where we do not have to feels
> like a better solution to that issue, and use of pqueue may be a
> right direction to go in.

Agreed. The only thing I'd worry about is that somebody cares about the
order stability of same-time commits in the output. But I cannot think
of a case where it is important (especially because the timestamps are
subject to minor skew anyway, so it is not like you could even count on
particular commits having equivalent timestamps).

-Peff