Jeff King wrote:
> That does O(n log n) offset comparisons, and profiling shows
> that we spend most of our time in cmp_offset. However, since
> we are sorting on a simple off_t, we can use numeric sorts
> that perform better. A radix sort can run in O(k*n), where k
> is the number of "digits" in our number. For a 64-bit off_t,
> using 16-bit "digits" gives us k=4.
Wait, isn't off_t a signed data type? Did you account for that in
your algorithm?
> On the linux.git repo, with about 3M objects to sort, this
> yields a 400% speedup. Here are the best-of-five numbers for
> running "echo HEAD | git cat-file --batch-disk-size", which
> is dominated by time spent building the pack revindex:
Okay.
> diff --git a/pack-revindex.c b/pack-revindex.c
> index 1aa9754..9365bc2 100644
> --- a/pack-revindex.c
> +++ b/pack-revindex.c
> @@ -59,11 +59,85 @@ static int cmp_offset(const void *a_, const void *b_)
> /* revindex elements are lazily initialized */
> }
>
> -static int cmp_offset(const void *a_, const void *b_)
> +/*
> + * This is a least-significant-digit radix sort.
> + */
Any particular reason for choosing LSD, and not MSD?
> +#define DIGIT_SIZE (16)
> +#define BUCKETS (1 << DIGIT_SIZE)
Okay, NUMBER_OF_BUCKETS = 2^RADIX, and you choose a hex radix. Is
off_t guaranteed to be fixed-length though? I thought only the ones
in stdint.h were guaranteed to be fixed-length?
> + /*
> + * We want to know the bucket that a[i] will go into when we are using
> + * the digit that is N bits from the (least significant) end.
> + */
> +#define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1))
Ouch! This is unreadable. Just write an inline function instead? A
% would've been easier on the eyes, but you chose base-16.
> + /*
> + * We need O(n) temporary storage, so we sort back and forth between
> + * the real array and our tmp storage. To keep them straight, we always
> + * sort from "a" into buckets in "b".
> + */
> + struct revindex_entry *tmp = xcalloc(n, sizeof(*tmp));
Shouldn't this be sizeof (struct revindex_entry), since tmp hasn't
been declared yet? Also, s/n/revindex_nr/, and something more
appropriate for tmp?
> + struct revindex_entry *a = entries, *b = tmp;
It's starting to look like you have something against descriptive names ;)
> + int bits = 0;
> + unsigned *pos = xmalloc(BUCKETS * sizeof(*pos));
sizeof(unsigned int), for clarity, if not anything else. You picked
malloc over calloc here, because you didn't want to incur the extra
cost of zero-initializing the memory? Also, pos is the actual buckets
array, I presume (hence unsigned, because there can't be a negative
number of keys in any bucket)?
> + while (max >> bits) {
No clue what max is. Looked at the caller and figured out that it's
the pack-size, although I'm still clueless about why it's appearing
here.
> + struct revindex_entry *swap;
> + int i;
> +
> + memset(pos, 0, BUCKETS * sizeof(*pos));
Ah, so that's why you used malloc there. Wait, shouldn't this be
memset(pos, 0, sizeof(*pos))?
> + for (i = 0; i < n; i++)
> + pos[BUCKET_FOR(a, i, bits)]++;
Okay, so you know how many numbers are in each bucket.
> + for (i = 1; i < BUCKETS; i++)
> + pos[i] += pos[i-1];
Cumulative sums; right.
> + for (i = n - 1; i >= 0; i--)
> + b[--pos[BUCKET_FOR(a, i, bits)]] = a[i];
Classical queue. You could've gone for something more complex, but I
don't think it would have been worth the extra complexity.
> + swap = a;
> + a = b;
> + b = swap;
Wait a minute: why don't you just throw away b? You're going to
rebuild the queue in the next iteration anyway, no? a is what is
being sorted.
> + /* And bump our bits for the next round. */
> + bits += DIGIT_SIZE;
I'd have gone for a nice for-loop.
> + /*
> + * If we ended with our data in the original array, great. If not,
> + * we have to move it back from the temporary storage.
> + */
> + if (a != entries)
> + memcpy(entries, tmp, n * sizeof(*entries));
How could a be different from entries? It has no memory allocated for
itself, no? Why did you even create a, and not directly operate on
entries?
> + free(tmp);
> + free(pos);
Overall, I found it quite confusing :(
> +#undef BUCKET_FOR
Why not DIGIT_SIZE and BUCKETS too, while at it?
--
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