On Nov 30, 2007 6:11 AM, Steffen Prohaska <prohaska@xxxxxx> wrote: > 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. This is a vote for pulling this into mainline git. AIX (at least 5.3) also has the horrible worst-case performance of the libc qsort on sorted or near-sorted lists (such as those provided by some filesystems, or a directory which has been rsynced). Some versions of Solaris have the same problem [1] I benchmarked 3 alternative qsorts, qsortG [2] was the fastest on my system but has funky licensing, the NetBSD qsort was middle-range and the glibc one the slowest of the three (but that could be due to it being tuned for a "Sun 4/260"). All of them show over 100x speed improvements on a git-status of my main repo (104s -> ~0.7s) I like the idea of a BROKEN_QSORT make variable. I was trying to come up with a patch which would discover the problem in a performance/regression test and suggest the setting, but have had insufficient free time so far. Cheers, Mike [1] http://bugs.opensolaris.org/view_bug.do?bug_id=1258570 [2] http://www.mccaughan.org.uk/g/software.html#qsort - 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
