Re: [PATCH 10/10] pack-revindex: radix-sort the revindex

On Wed, Jul 10, 2013 at 06:47:49PM +0530, Ramkumar Ramachandra wrote:

It is signed, but the values we are storing in the revindex are all positive file offsets. Right-shifting a positive signed type is explicitly allowed in C.

Simplicity. An MSD implementation should have the same algorithmic complexity and in theory, one can do MSD in-place. I'm happy enough with the speedup here, but if you want to take a stab at beating my times with MSD, please feel free.

The other "usual" downside of MSD is that it is typically not stable, but we don't care about that here. We know that our sort keys are unique.

I'm not sure what you mean by fixed-length. If you mean does it have the same size on every platform, then no. It will typically be 32-bit on platforms without largefile support, and 64-bit elsewhere. But it shouldn't matter. We'll first sort the entries by the lower 16 bits, and then if we have more bits, by the next 16 bits, and so on. We quit when the maximum value to sort (which we know ahead of time from the size of the packfile) is smaller than the 16-bits we are on. So we don't need to know the exact size of off_t, only the maximum value in our list (which must, by definition, be smaller than what can be represented by off_t).

I specifically avoided an inline function because they are subject to compiler settings. This isn't just "it would be a bit faster if this got inlined, and OK otherwise" but "this would be horribly slow if not inlined".

I'm also not sure that

  static inline unsigned bucket_for(const struct revindex *a,
                                    unsigned i,
                                    unsigned bits)
  {
          return a[i].offset >> bits & (BUCKETS-1);
  }

is actually any more readable.

I'm not sure what you mean by base-16. No matter the radix digit size, as long as it is an integral number of bits, we can mask it off, which is more efficient than modulo. A good compiler should see that it is a constant and convert it to a bit-mask, but I'm not sure I agree that modular arithmetic is more readable. This is fundamentally a bit-twiddling operation, as we are shifting and masking.

I tried to explain it in the comment; suggestions to improve that are welcome.

No, the variable is declared (but uninitialized) in its initializer. Despite its syntax, sizeof() is not a function and does not care about the state of the variable, only its type.

What name would you suggest be be more appropriate for tmp?

I disagree; in general, I prefer using sizeof(*var) rather than sizeof(type), because it avoids repeating ourselves, and there is no compile-time check that you have gotten it right.

In the initializer it is less important, because the type is right there. But when you are later doing:

  memset(pos, 0, BUCKETS * sizeof(*pos));

this is much more robust. If somebody changes the type of pos, the memset line does not need changed. If you used sizeof(unsigned), then the code is now buggy (and the compiler cannot notice).

Yes. We have to zero-initialize in each loop, so there is no point spending the extra effort on calloc.

We could also xcalloc inside each loop iteration, but since we need the same-size allocation each time, I hoisted the malloc out of the loop.

Exactly. I called it "pos" rather than "buckets" because the goal is to get the start-position of each bucket (as explained in the comment in the loop).

It's larger than the largest sort key in the array. On an LSD radix sort, we can stop sorting when we are looking at a radix digit whose value is larger than the max, because we know all of the entries will simply have "0" in that digit.

So even if off_t is 64-bit, we can quit after the 32nd bit (i.e., k=2) if the packfile is smaller than 4G.

An MSD radix sort could do the same trick, but would obviously skip the zero digits at the beginning rather than the end.

No, that would zero only the first entry of the array. We allocated BUCKETS * sizeof(*pos) bytes, and we want to zero them all.

For each iteration, we need to sort into temporary storage. So you can do it like:

  1. sort entries into tmp

  2. copy tmp back into entries

  3. bump radix digit and goto 1

But you can eliminate the copy in step 2 if you instead go back and forth, like:

  1. sort entries into tmp

  2. bump radix digit

  3. sort tmp into entries

  ...etc

To do that in a loop, we need an alias for "the thing we are sorting from" and "the thing we are sorting to". Hence the "a" and "b" pointers. Perhaps these comments make more sense now:

+       /*
+        * 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));
+       struct revindex_entry *a = entries, *b = tmp;
[...]
+               /*
+                * Now "b" contains the most sorted list, so we swap "a" and
+                * "b" for the next iteration.
+                */

Yeah, that would look like:

  for (bits = 0; max >> bits; bits += DIGIT_SIZE) {
     ...
  }

I don't really find one more readable than the other.

See the back-and-forth explanation above.

Clearly. It was confusing to write (especially because there are a number of optimizations, and because radix sort is not well known, at least to me), which is why I tried to comment profusely. It seems quite a few of them didn't help, as the answers to your questions were there. If you have suggestions for improvement to the comments, I'm all ears.

I forgot. I added them later (they were originally magic numbers in the code). Will add.

-Peff