Re: Some git performance measurements..

["Mike Ralphson" <mike.ralphson@gmail.com>]

On Nov 30, 2007 6:11 AM, Steffen Prohaska <prohaska@zib.de> 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