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

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

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to