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

Jeff King [off-list ref] writes:

The performance enhancement of the priority queue came from replacing
"commit_list_insert_by_date" calls with insertion into a queue. That
drops O(n^2) behavior on the linked-list down to O(n log n), as we have
"n" insertions, each causing an O(log n) heapify operation.

Yes.

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?

So your results are exactly what I would expect: the time should be
about the same (due to the same complexity), but the memory is used more
compactly (array of pointers instead of linked list of pointers).

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.

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

quoted

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