I recognized today that the qsort replacement never made it to
msysgit's master. I remember we discussed wether the patch
should be sent upstream or included in mingw or in msysgit. I
don't remember if we came to a conclusion.
Anyway, I now merged the patch to msysgit's devel and it will be
included in the next release. The commit log is attached below.
Steffen
commit bc8e453867b6ae950ae4333647f7f5e368ba7b15
Author: Brian Downing <[EMAIL PROTECTED]>
Date: Fri Nov 16 22:28:13 2007 -0600
mingw-compat: Add simplified merge sort implementation from glibc
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 <[EMAIL PROTECTED]>
Signed-off-by: Steffen Prohaska <[EMAIL PROTECTED]>
Signed-off-by: Johannes Schindelin <[EMAIL PROTECTED]>
