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

From: Jeff King <peff@peff.net>
Date: Apr 3, 2012, 08:40 UTC
Message-ID: <20120403084035.GA14483@sigill.intra.peff.net>
In-Reply-To: <4F7A2E0D.9030402@lsrfire.ath.cx>

On Tue, Apr 03, 2012 at 12:54:05AM +0200, René Scharfe wrote:

Show 8 quoted lines

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

I agree it is a little gross. The main impetus was shortened code, since we get qsort for free. However, after reading Simon's page that you referenced and reading your code carefully, I'm beginning to think that the linked-list mergesort is pretty damn cool (I hadn't seen it before). After all, mergesort without the auxiliary space should be better than qsort.

So let's go with your patches.

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

I probably screwed up the reversal or something. My patch was a quick "I was thinking of this direction" and I didn't actually test it well.

Show 10 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. ;-)

Actually, I think a skip list would make a lot of sense, as it mostly retains the linked-list properties. When I tried converting it to a heap-based priority queue, I seem to recall that there were some spots that wanted to splice the commit list (among other things). Although I'm not sure how splicing works in a skip list; I guess you'd have to do a list merge.

-Peff