6
\$\begingroup\$

I'm implementing a (hopefully) efficient MSB Radix Sort in Java. My current implementation isn't efficient enough for my use-case (see bottom for a brief performance comparison against Arrays.sort).

Please rip me to shreds over any general improvements you can suggest; I am currently most interested in suggestions for performance improvements, though.

I do use recursion, as I'm only copying references in each stack frame (so I don't think I'm going to be taking much of a hit there). I allocate two buffers and each layer in the recursion tree uses one arrays as an input and one as an output - each node on each layer sorts a different bucket within the input, storing its results in the output before recursing.

// Sort "amount" integers from "input" and write them to "output".
protected void radicsSort(DataInputStream input, DataOutputStream output, int amount) throws IOException
{
    // Read in our buffer to memory
    int[] inputBuffer = new int[amount];
    for (int x = 0; x < inputBuffer.length; ++x)
        inputBuffer[x] = input.readInt();

    // Allocate an output buffer as big as the input one
    int[] outputBuffer = new int[amount];

    //// Sort the input  buffer
    radicsSort(inputBuffer, outputBuffer, 0, amount, Integer.SIZE - 1);

    // Input and output are swapped each layer of recursion, and we recurse as many times
    // as there are bits in an integer, so ensure the final output is in outputBuffer.
    // Commented out at the moment as we get a warning as technically we already know the result...
    //if (Integer.SIZE % 2 == 0)
        outputBuffer = inputBuffer;

    // Write the output to the file
    for (int x = 0; x < outputBuffer.length; ++x)
        output.writeInt(outputBuffer[x]);
}
// Sort the integers in "inBuffer" at indices between "start" inclusive and "end" exclusive,
// by the value of the bit at "bit", storing the results in "outBuffer" in the same
// interval as they were taken from
protected void radicsSort(int[] inBuffer, int[] outBuffer, int start, int end, int bit)
{
    // TODO: Check negative numbers are sorted correctly with this
    int zeroIndex = start; // Counts up from the start
    int oneIndex = end; // Counts down from the end

    for (int x = start; x < end; ++x)
    {
        if (((inBuffer[x] >> bit) & 1) == 0) // Bit is 0
            outBuffer[zeroIndex++] = inBuffer[x];
        else // Bit is 1
            outBuffer[--oneIndex] = inBuffer[x];
    }

    if (bit > 0)
    {
        // Recurse to sort the two sub-regions, moving one bit towards the LSB.
        // Swap the input/output buffers
        radicsSort(outBuffer, inBuffer, start, oneIndex, bit - 1);
        radicsSort(outBuffer, inBuffer, oneIndex, end, bit - 1);
    }
}

Performance comparison with Arrays.sort, times given in milliseconds:

Number of integers        Arrays.sort        Above implementation
1024                      1                  8328
1048576                   1221               19367

I understand that radix sort has a high constant overhead, but I thought it would have overcome that by the time we're sorting 4MiB of data.

The things I can think of to tweak are:

  • Use iteration instead of recursion (don't think this will change much).
  • Sort by eg. decimal digit instead of binary digit. Again, don't know how much of a performance impact this'll have.
  • Switch to eg. insertion sort after a threshold. I believe this is normally done to overcome the overhead of allocating new structures when you're working with small buckets. I think my implementation avoids this overhead anyway, by using a common output buffer and swapping input/output buffers, so I don't think this'll have much of an impact.
\$\endgroup\$
  • 1
    \$\begingroup\$ Two datapoint do not really convey a feel of complexity. However, on a 1000-fold increase of size of input Arrays.sort takes 1000-fold time, while the Above implementation is just 2.5 longer. More datapoint will be seriously enlightening. \$\endgroup\$ – vnp Aug 12 '17 at 22:51
  • \$\begingroup\$ You should try using 256 buckets and handling 8 bits at a time instead of 2 buckets and 1 bit at a time. I have a feeling this will make your sort run at least 8x faster. I've written an inplace MSD radix sort using 8 bits at a time which switches to insertion sort below a threshold, and it was much faster than the standard library sort. See here for a java example from this site. \$\endgroup\$ – JS1 Aug 13 '17 at 2:21
4
\$\begingroup\$
  • Post line-oriented timings from a profiling run, please. Where does it actually spend its time?

  • Curly braces {} are good for you, even when your for or if statement is a one-liner. Someone will be maintaining this code later, and it might not be you.

  • Please rename to radixSort(), from the Latin word for root.

  • Recursion overhead is simply not an issue here.

  • I imagine you're testing with random integers, so stability or reversing would not affect that. But think about timsort https://en.wikipedia.org/wiki/Timsort which is stable. If there are runs of non-descending input values, you would really like to preserve them. That would let you verify and terminate early.

  • Arrays.sort() runs in \$O(n \log{n})\$ time. Your radix sort is "efficient" in the sense that it runs in \$O(n)\$ time, but the notation can hide impressively large constants, like bits per Integer in your case. A linear read scan tries to blow out memory bandwidth, and L2 (last level) cache won't help you. You're not even working on cache-size subproblems with a subsequent merge. Yes, I agree that switching to an \$n\log{n}\$ sort for limited size subproblems would be helpful.

  • You mentioned decimal digits, and I see no reason to go there. But consider sorting into 4 buckets during a pass, or 8, or 16....

\$\endgroup\$
  • \$\begingroup\$ In the O(n) speak, the n can be very misleading indeed. \$\endgroup\$ – vnp Aug 12 '17 at 23:29
2
\$\begingroup\$

The actual specifier is MSD (most-significant digit) and not MSB (most-significant bit, I suppose). What comes to performance, years ago I wrote a MSD radix sort that takes a parameter, call it \$d\$. Given such a \$d\$, the algorithm treats a \$d\$-bit sequence as a key. I benchmarked all the values \$d = 1, 2, \dots, 16\$, and \$d = 8\$ (one byte at a time) was a clear winner. The moral here is: process one byte at a time and not a single bit.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.