Re: Some git performance measurements..

From: Mike Ralphson <mike.ralphson@gmail.com>
Date: Dec 7, 2007, 13:35 UTC
Message-ID: <e2b179460712070535x2eb10710s75a581664139e0cf@mail.gmail.com>
In-Reply-To: <B161871F-E812-44B4-A699-44341B5783D3@zib.de>

On Nov 30, 2007 6:11 AM, Steffen Prohaska <prohaska@zib.de> wrote:

Show 15 quoted lines

> 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