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
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
