On Nov 30, 2007, at 3:40 AM, Nicolas Pitre wrote:
On Thu, 29 Nov 2007, Linus Torvalds wrote:
On Fri, 30 Nov 2007, Jakub Narebski wrote:
Isn't there a better way to do this sorting? What is needed here is
(stable) _bucket_ sort / _pigeonhole_ sort (or counting sort), which
is O(n); quicksort is perhaps simpler to use, but I'm not sure if
faster in this situation.
That particular sort takes under a second here with the Linux repo.
Pretty insignificant compared to the time required to repack.
Brian Downing measured horrid performance of qsort on Windows
2000 [1]. qsort seems to show worst case behaviour.
This resulted in a patch replacing Window's qsort implementation
for the mingw port [2].
[1] http://thread.gmane.org/gmane.comp.version-control.msysgit/1084
[2] http://thread.gmane.org/gmane.comp.version-control.msysgit/1086
Avoiding qsort would even be better. I'm not sure, though,
if the particular qsort call that triggered the current
discussion, is the very same qsort call that Brian was hit by.
I'm only claiming that in general avoiding qsort on Windows
is a good idea.
Steffen
-
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
