git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: Ramkumar Ramachandra <artagnon@gmail.com>
To: Jeff King <peff@peff.net>
Cc: git@vger.kernel.org, Duy Nguyen <pclouds@gmail.com>,
	Brandon Casey <drafnel@gmail.com>,
	Junio C Hamano <gitster@pobox.com>
Subject: Re: [PATCH 10/10] pack-revindex: radix-sort the revindex
Date: Wed, 10 Jul 2013 18:47:49 +0530	[thread overview]
Message-ID: <CALkWK0=_6-RN2dHrhMdKu8nTyj1iwVe388Y57pOac17xhbqn5Q@mail.gmail.com> (raw)
In-Reply-To: <20130710115557.GJ21963@sigill.intra.peff.net>

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?

  parent reply	other threads:[~2013-07-10 13:18 UTC|newest]

Thread overview: 52+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2013-07-07 10:01 [RFC/PATCH 0/4] cat-file --batch-disk-sizes Jeff King
2013-07-07 10:03 ` [PATCH 1/4] zero-initialize object_info structs Jeff King
2013-07-07 17:34   ` Junio C Hamano
2013-07-07 10:04 ` [PATCH 2/4] teach sha1_object_info_extended a "disk_size" query Jeff King
2013-07-07 10:09 ` [PATCH 3/4] cat-file: add --batch-disk-sizes option Jeff King
2013-07-07 17:49   ` Junio C Hamano
2013-07-07 18:19     ` Jeff King
2013-07-08 11:04     ` Duy Nguyen
2013-07-08 12:00       ` Ramkumar Ramachandra
2013-07-08 13:13         ` Duy Nguyen
2013-07-08 13:37           ` Ramkumar Ramachandra
2013-07-09  2:55             ` Duy Nguyen
2013-07-09 10:32               ` Ramkumar Ramachandra
2013-07-10 11:16             ` Jeff King
2013-07-08 16:40           ` Junio C Hamano
2013-07-10 11:04     ` Jeff King
2013-07-11 16:35       ` Junio C Hamano
2013-07-07 21:15   ` brian m. carlson
2013-07-10 10:57     ` Jeff King
2013-07-07 10:14 ` [PATCH 4/4] pack-revindex: radix-sort the revindex Jeff King
2013-07-07 23:52   ` Shawn Pearce
2013-07-08  7:57     ` Jeff King
2013-07-08 15:38       ` Shawn Pearce
2013-07-08 20:50   ` Brandon Casey
2013-07-08 21:35     ` Brandon Casey
2013-07-10 10:57       ` Jeff King
2013-07-10 10:52     ` Jeff King
2013-07-10 11:34 ` [PATCHv2 00/10] cat-file formats/on-disk sizes Jeff King
2013-07-10 11:35   ` [PATCH 01/10] zero-initialize object_info structs Jeff King
2013-07-10 11:35   ` [PATCH 02/10] teach sha1_object_info_extended a "disk_size" query Jeff King
2013-07-10 11:36   ` [PATCH 03/10] t1006: modernize output comparisons Jeff King
2013-07-10 11:38   ` [PATCH 04/10] cat-file: teach --batch to stream blob objects Jeff King
2013-07-10 11:38   ` [PATCH 05/10] cat-file: refactor --batch option parsing Jeff King
2013-07-10 11:45   ` [PATCH 06/10] cat-file: add --batch-check=<format> Jeff King
2013-07-10 11:57     ` Eric Sunshine
2013-07-10 14:51     ` Ramkumar Ramachandra
2013-07-11 11:24       ` Jeff King
2013-07-10 11:46   ` [PATCH 07/10] cat-file: add %(objectsize:disk) format atom Jeff King
2013-07-10 11:48   ` [PATCH 08/10] cat-file: split --batch input lines on whitespace Jeff King
2013-07-10 15:29     ` Ramkumar Ramachandra
2013-07-11 11:36       ` Jeff King
2013-07-11 17:42         ` Junio C Hamano
2013-07-11 20:45         ` [PATCHv3 " Jeff King
2013-07-10 11:50   ` [PATCH 09/10] pack-revindex: use unsigned to store number of objects Jeff King
2013-07-10 11:55   ` [PATCH 10/10] pack-revindex: radix-sort the revindex Jeff King
2013-07-10 12:00     ` Jeff King
2013-07-10 13:17     ` Ramkumar Ramachandra [this message]
2013-07-11 11:03       ` Jeff King
2013-07-10 17:10     ` Brandon Casey
2013-07-11 11:17       ` Jeff King
2013-07-11 12:16     ` [PATCHv3 " Jeff King
2013-07-11 21:12       ` Brandon Casey

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CALkWK0=_6-RN2dHrhMdKu8nTyj1iwVe388Y57pOac17xhbqn5Q@mail.gmail.com' \
    --to=artagnon@gmail.com \
    --cc=drafnel@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=pclouds@gmail.com \
    --cc=peff@peff.net \
    --subject='Re: [PATCH 10/10] pack-revindex: radix-sort the revindex' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).