Re: Some git performance measurements..

From: Nicolas Pitre <nico@cam.org>
Date: Nov 30, 2007, 02:40 UTC
Message-ID: <alpine.LFD.0.99999.0711292131350.9605@xanadu.home>
In-Reply-To: <alpine.LFD.0.9999.0711291812530.8458@woody.linux-foundation.org>

On Thu, 29 Nov 2007, Linus Torvalds wrote:

Show 6 quoted lines

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

> Actually, I doubt you need to do any sorting at all: what would be easiest 
> would be to simply change "traverse_commit_list()" to use different lists 
> for different object types, and just output them in type order (semi-sane 
> order choice: commits first, then tags, then trees, and finally blobs).

Yes! That's what I thought initially, but since list-objects.c is completely unknown territory to me, I sorted them in pack-object.c instead, out of pure laziness.

Nicolas