Subject: Re: Some git performance measurements..

From: Jakub Narebski <[email-masked]>
Date: Fri, 30 Nov 2007 01:54:13 +0100

<opublikowany i wysłany>

[Cc: [email-masked], Nicolas Pitre <[email-masked]>, 
 Linus Torvalds <[email-masked]>]

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.

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