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

From: Jeff King <peff@peff.net>
Date: Jun 10, 2013, 18:24 UTC
Message-ID: <20130610182441.GB2084@sigill.intra.peff.net>
In-Reply-To: <7vsj0ql924.fsf@alter.siamese.dyndns.org>

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

Show 8 quoted lines

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

Show 6 quoted lines

> 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