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

From: René Scharfe <rene.scharfe@lsrfire.ath.cx>
Date: Apr 2, 2012, 22:54 UTC
Message-ID: <4F7A2E0D.9030402@lsrfire.ath.cx>
In-Reply-To: <20120402201432.GA26503@sigill.intra.peff.net>

Am 02.04.2012 22:14, schrieb Jeff King:

Show 20 quoted lines

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

Show 5 quoted lines

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