Re: Some git performance measurements..

From: Brian Downing <bdowning@lavos.net>
Date: Dec 8, 2007, 23:04 UTC
Message-ID: <20071208230402.GK6212@lavos.net>
In-Reply-To: <Pine.LNX.4.64.0712081103430.27959@racer.site>

On Sat, Dec 08, 2007 at 11:05:35AM +0000, Johannes Schindelin wrote:

Show 10 quoted lines

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

Show 5 quoted lines

> 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