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