Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

["René Scharfe" <rene.scharfe@lsrfire.ath.cx>]

Am 02.04.2012 22:14, schrieb Jeff King:
> On Sun, Apr 01, 2012 at 12:11:01AM +0200, René Scharfe wrote:
>
>> Speed up prepare_revision_walk() by adding commits without sorting
>> to the commit_list and at the end sort the list in one go.  Thanks
>> to mergesort() working behind the scenes, this is a lot faster for
>> large numbers of commits than the current insert sort.
>
> I think this is probably a sane thing to do, but I have two slight
> misgivings:
>
>    1. Is it worth the complexity of the linked-list mergesort? I was
>       planning to just build an array, qsort it, and then put the results
>       into a linked list. The patch for that is below for reference.
>
>       It's a lot less code and complexity for the same performance
>       (actually, I measured it at 1% faster, but that is probably
>       negligible). The downside is that it is not nicely encapsulated in
>       commit_list_sort_by_date(). We call the latter from two other
>       places; I don't know if they can be fed with enough commits to
>       actually benefit from the performance gain or not.

Using a temporary array here is just sad, because linked lists are 
already sortable, albeit not with qsort().  Your measurements seem to 
answer my question regarding the overhead of the callback functions of 
mergesort(), in any case. :)

Adding mergesort() only pays if we have other linked lists that we want 
to sort in-place.  I didn't search thoroughly for such a use case, but I 
think we tended to prefer arrays so far instead.

>       So I wonder if in the long term we would benefit from a better data
>       structure, which would make these problems just go away. That being
>       said, there is a lot of code to be updated with such a change, so
>       even if we do want to do that eventually, a quick fix like this is
>       probably still a good thing.

Using a more appropriate data structure sounds good in general. How 
about using a skip list?  (Or perhaps I need to lay the hammer of linked 
lists to rest for a while to stop seeing all data structures as the 
proverbial nails, or something. ;-)

> Here's the qsort-in-array patch, for reference.

It looks nice and to the point, but breaks several tests for me (t3508, 
t4013, t4041, t4202, t6003, t6009, t6016, t6018 and t7401).  Not sure why.

René