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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html