qsort on devel

[Steffen Prohaska]

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 <bdow...@lavos.net>
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 <bdow...@lavos.net>
Signed-off-by: Steffen Prohaska <proh...@zib.de>
Signed-off-by: Johannes Schindelin <johannes....@gmx.de>

[Johannes Schindelin]

Hi,

On Sun, 30 Dec 2007, Steffen Prohaska wrote:

> 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.

I had the impression that Brian found a faster implementation, which could
not be included for license reasons...

But for the time being, this is better than nothing, I guess.

Thanks,
Dscho

[Brian Downing]

On Sun, Dec 30, 2007 at 05:00:35PM +0100, Johannes Schindelin wrote:
> I had the impression that Brian found a faster implementation, which could
> not be included for license reasons...
>
> But for the time being, this is better than nothing, I guess.

It wasn't me. It was "Mike Ralphson" in the "Some git performance
measurements" thread on the vger list.

http://article.gmane.org/gmane.comp.version-control.git/67424

However, I came to the conclusion that he was actually comparing against
glibc's quicksort implementation; his comment about being tuned for
"Sun 4/260" matches a comment in glibc's quicksort implementation,
not the mergesort that I used as a base. Later, in:

http://article.gmane.org/gmane.comp.version-control.git/67443

He said the mergesort in mingw was faster.

-bcd

[Johannes Schindelin]

Hi,

Ah, thanks! So this is settled, then.

Ciao,
Dscho

[Steffen Prohaska]

But apparently the discussion didn't result in a patch then. I
can't find a patch sent to the git list that would add a qsort
replacement.

The qsort replacement seems to be of general interest and I
therefore prefer if it went to official git ASAP. My main goal
is still to reduce differences between 4msysgit, mingw, and
official git.

I'm not sure if this is the right time to send a patch upstream,
because we're in the middle of the 1.5.4 freeze. So, I'll keep
it in 4msysgit only. But maybe later someone (Brian?) could
send the patch upstream.

The latest version of the patch is here:

http://repo.or.cz/w/git/mingw/4msysgit.git?a=commitdiff;h=bc8e4538

Steffen