Re: Some git performance measurements..

From: Jakub Narebski <jnareb@gmail.com>
Date: Nov 30, 2007, 00:54 UTC
Message-ID: <finmvm$da8$1@ger.gmane.org>
In-Reply-To: <alpine.LFD.0.99999.0711291208060.9605@xanadu.home>

<opublikowany i wysłany>

[Cc: git@vger.kernel.org, Nicolas Pitre <nico@cam.org>, 
 Linus Torvalds <torvalds@linux-foundation.org>]

Nicolas Pitre wrote:

> Well, see below for the patch that actually split the pack data into 
> objects of the same type.  Doing that "git checkout" on the kernel tree 
> did improve things for me although not spectacularly.

Show 14 quoted lines

> +static int sort_by_type(const void *_a, const void *_b)
> +{
> +     const struct object_entry *a = *(struct object_entry **)_a;
> +     const struct object_entry *b = *(struct object_entry **)_b;
> +
> +     /*
> +      * Preserve recency order for objects of the same type  and reused deltas.
> +      */
> +     if(a->type == OBJ_REF_DELTA || a->type == OBJ_OFS_DELTA ||
> +        b->type == OBJ_REF_DELTA || b->type == OBJ_OFS_DELTA ||
> +        a->type == b->type)
> +             return (a < b) ? -1 : 1;
> +     return a->type - b->type;
> +}

> +     qsort(sorted_by_type, nr_objects, sizeof(*sorted_by_type), sort_by_type);

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.

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git