Re: Some git performance measurements..

From: Steffen Prohaska <prohaska@zib.de>
Date: Nov 30, 2007, 06:11 UTC
Message-ID: <B161871F-E812-44B4-A699-44341B5783D3@zib.de>
In-Reply-To: <alpine.LFD.0.99999.0711292131350.9605@xanadu.home>

On Nov 30, 2007, at 3:40 AM, Nicolas Pitre wrote:

Show 11 quoted lines

> On Thu, 29 Nov 2007, Linus Torvalds wrote:
>
>> On Fri, 30 Nov 2007, Jakub Narebski wrote:
>>>
>>> Isn't there a better way to do this sorting? What is needed here is
>>> (stable) _bucket_ sort / _pigeonhole_ sort (or counting sort), which
>>> is O(n); quicksort is perhaps simpler to use, but I'm not sure if
>>> faster in this situation.
>
> That particular sort takes under a second here with the Linux repo.
> Pretty insignificant compared to the time required to repack.

Brian Downing measured horrid performance of qsort on Windows 2000 [1]. qsort seems to show worst case behaviour.

This resulted in a patch replacing Window's qsort implementation for the mingw port [2].

[1] http://thread.gmane.org/gmane.comp.version-control.msysgit/1084 [2] http://thread.gmane.org/gmane.comp.version-control.msysgit/1086

Avoiding qsort would even be better. I'm not sure, though, if the particular qsort call that triggered the current discussion, is the very same qsort call that Brian was hit by. I'm only claiming that in general avoiding qsort on Windows is a good idea.

	Steffen