qsort in Windows 2000 (and possibly other older Windows' C libraries)

is a Quicksort with the usual O(n^2) worst case.  Unfortunately, sorting

Git trees seems to get very close to that worst case quite often:
    $ /git/gitbad runstatus

    # On branch master

    qsort, nmemb = 30842

    done, 237838087 comparisons.
This patch adds a simplified version of the merge sort that is glibc's

qsort(3).  As a merge sort, this needs a temporary array equal in size

to the array that is to be sorted.
The complexity that was removed is:
* Doing direct stores for word-size and -aligned data.

* Falling back to quicksort if the allocation required to perform the

  merge sort would likely push the machine into swap.
Even with these simplifications, this seems to outperform the Windows

qsort(3) implementation, even in Windows XP (where it is "fixed" and

doesn't trigger O(n^2) complexity on trees).
[jes: moved into compat/qsort.c, as per Johannes Sixt's suggestion]
Signed-off-by: Brian Downing <bdowning@lavos.net>

Signed-off-by: Steffen Prohaska <prohaska@zib.de>

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>

---

   Junio,
   This is for consideration for mainline Git now that 1.5.4 is out.  It

   is used to avoid an awful qsort implementation on Windows 2000, and I

   believe there was some discussion about other Unixes (AIX, etc) that

   have a similar problem.
   -bcd
 Makefile          |    7 ++++++

 compat/qsort.c    |   60 +++++++++++++++++++++++++++++++++++++++++++++++++++++

 git-compat-util.h |    6 +++++

 3 files changed, 73 insertions(+), 0 deletions(-)

 create mode 100644 compat/qsort.c
diff --git a/Makefile b/Makefile

index 92341c4..1698bc4 100644

--- a/Makefile

+++ b/Makefile

@@ -137,6 +137,9 @@ all::

 # Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit

 # parallel delta searching when packing objects.

 #

+# Define NEEDS_QUICK_QSORT if your qsort() implementation has O(n^2)

+# worst case complexity.

...
[ message continues ]

if (size < 1024) {

-		char buf[size]; /* gcc-ism */

+		char buf[1024];

-

Good point; when it was a mingw-only hack the gcc-ism didn't matter.
I'll see if I can push an updated patch in a day or so...
-bcd

-

Hi,
I should add that this is a stripped-down version of glibc's sort() (yes,

the GPL of glibc allows that we rip it, for all you license wieners out

there).
AFAIR the discussion about the different implementations of a sort

algorithm boiled down to one particular implementation being quicker than

what this patch has, but with dubious licensing, and the glibc

implementation without the modifications present in this patch being

slower.
So I would like this to go in, evidently, if only as a starting point for

people to play with sorting algorithms, to find the one which is optimal

for our general use (we have quite some uses where we put in _almost_

sorted data, which seems to be the worst-case for many sorting

algorithms).
Ciao,

Dscho
-

I do not think we want to spend arguing over the last few

percent to get anything ultra-fast.  The aim for compat/ is to

have a replacement for unusable platform-supplied stuff.
The patch looked fine, thanks.
If I may add a bikeshed comment, I probably would have modelled

the make variable, not after ssl-with-crypto and libiconv, but

after {arm,mozilla,ppc}-sha1, if I were naming it.  This is not

like an absolute must-to-have: "on this platform, libc is not

enough and we NEED to explicitly ask for -liconv".  It is more

like a choose-to-use: "we could use openssl sha1 implementation,

but I choose to use Mozilla one".

-

If this is what I am thinking of, the sort of dubious licensing was

faster than glibc's quicksort.  This patch, however, is simplified from

glibc's mergesort (which is what glibc uses for the qsort() call except

for very large arrays), and was determined to be faster than both.
See:
http://groups.google.com/group/msysgit/browse_frm/thread/3c2eb564b9d0a994
and the links from that thread for more information.
-bcd

-

Tested-by: Mike Ralphson <mike.ralphson@gmail.com>
Many thanks Brian, I held off from submitting your patch to git.git

because of the 1.5.4 freeze. I'll retest my other candidate qsort

implementations and report back. For now this makes git look good on

AIX. It would be good to have feedback from users of older versions of

Solaris too.
Once the final patch is in, I'll drop some queued AIX Makefile patches on top.
Cheers, Mike

-

Hi,
Yeah, sorry, I forgot that important fact.
Thanks,

Dscho
-