Re: Some git performance measurements..

[bdowning@lavos.net (Brian Downing)]

On Sat, Dec 08, 2007 at 11:05:35AM +0000, Johannes Schindelin wrote:
> On Fri, 7 Dec 2007, Mike Ralphson wrote:
> > I've just tried the mergesort implementation as used in msysgit and that 
> > performs faster for me. It's simpler, and compatibly licensed. It looks 
> > good.
> 
> Now I'm confused.  You said you tested qsortG, NetBSD qsort and qlibc, 
> with glibc performing the slowest.  Now, 4msysgit's implementation is 
> based on glibc (Thanks Brian!), so I wonder if you could redo the 
> performance tests and say if qsortG still is substantially faster than 
> 4msysgit's qsort?

This is just me guessing, but when he said:

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

It's possible he tried glibc's actual quicksort implementation, rather
than their "qsort."  Their qsort basically has the following behavior:

if size < 1024
    mergesort with temporary array on stack
if allocating size bytes would likely cause swapping
    quicksort in place
else
    mergesort with temporary array in heap

I removed the "quicksort in place" possibility, as it would have added
another sort algorithm and I had no way to easily determine whether
"allocating size bytes would likely cause swapping."

-bcd