3
\$\begingroup\$

Now I have that parallel Quicksort for (primitive) integer arrays.

ParallelIntQuicksort.java:

package net.coderodde.util;

import static net.coderodde.util.Util.median;
import static net.coderodde.util.Util.swap;

/**
 * This class implements a parallel Quicksort.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 5, 2016)
 */
public class ParallelIntQuicksort {

    private static final int MINIMUM_THREAD_WORKLOAD = 131_072;

    public static void sort(int[] array) {
        sort(array, 0, array.length);
    }

    public static void sort(int[] array, int fromIndex, int toIndex) {
        int rangeLength = toIndex - fromIndex;
        int cores = Math.min(rangeLength / MINIMUM_THREAD_WORKLOAD,
                             Runtime.getRuntime().availableProcessors());
        sortImpl(array, 
                 fromIndex, 
                 toIndex, 
                 cores);
    }

    private ParallelIntQuicksort() {

    }

    private static void sortImpl(int[] array,
                                 int fromIndex, 
                                 int toIndex,
                                 int cores) {
        if (cores <= 1) {
            IntQuicksort.sort(array, fromIndex, toIndex);
            return;
        }

        int rangeLength = toIndex - fromIndex;
        int distance = rangeLength / 4;

        int a = array[fromIndex + distance];
        int b = array[fromIndex + (rangeLength >>> 1)];
        int c = array[toIndex - distance];

        int pivot = median(a, b, c);
        int leftPartitionLength = 0;
        int rightPartitionLength = 0;
        int index = fromIndex;

        while (index < toIndex - rightPartitionLength) {
            int current = array[index];

            if (current > pivot) {
                ++rightPartitionLength;
                swap(array, toIndex - rightPartitionLength, index);
            } else if (current < pivot) {
                swap(array, fromIndex + leftPartitionLength, index);
                ++index;
                ++leftPartitionLength;
            } else {
                ++index;
            }
        }

        ParallelQuicksortThread leftThread = 
                new ParallelQuicksortThread(array,
                                            fromIndex,
                                            fromIndex + leftPartitionLength,
                                            cores / 2);
        ParallelQuicksortThread rightThread =
                new ParallelQuicksortThread(array,
                                            toIndex - rightPartitionLength,
                                            toIndex,
                                            cores - cores / 2);

        leftThread.start();
        rightThread.start();

        try {
            leftThread.join();
            rightThread.join();
        } catch (InterruptedException ex) {
            throw new IllegalStateException(
                    "Parallel quicksort threw an InterruptedException.");
        }
    }

    private static final class ParallelQuicksortThread extends Thread {

        private final int[] array;
        private final int fromIndex;
        private final int toIndex;
        private final int cores;

        ParallelQuicksortThread(int[] array, 
                                int fromIndex, 
                                int toIndex, 
                                int cores) {
            this.array = array;
            this.fromIndex = fromIndex;
            this.toIndex = toIndex;
            this.cores = cores;
        }

        @Override
        public void run() {
            sortImpl(array, fromIndex, toIndex, cores);
        }
    }
}

IntQuicksort.java:

package net.coderodde.util;

import java.util.Arrays;
import java.util.Random;
import static net.coderodde.util.Util.median;
import static net.coderodde.util.Util.swap;

public class IntQuicksort {

    private static final int INSERTIONSORT_THRESHOLD = 16;

    private IntQuicksort() {

    }

    public static void sort(int[] array) {
        sort(array, 0, array.length);
    }

    public static void sort(int[] array, int fromIndex, int toIndex) {
        while (true) {
            int rangeLength = toIndex - fromIndex;

            if (rangeLength < 2) {
                return;
            }

            if (rangeLength < INSERTIONSORT_THRESHOLD) {
                insertionsort(array, fromIndex, toIndex);
                return;
            }

            int distance = rangeLength / 4;

            int a = array[fromIndex + distance];
            int b = array[fromIndex + (rangeLength >>> 1)];
            int c = array[toIndex - distance];

            int pivot = median(a, b, c);
            int leftPartitionLength = 0;
            int rightPartitionLength = 0;
            int index = fromIndex;

            while (index < toIndex - rightPartitionLength) {
                int current = array[index];

                if (current > pivot) {
                    ++rightPartitionLength;
                    swap(array, toIndex - rightPartitionLength, index);
                } else if (current < pivot) {
                    swap(array, fromIndex + leftPartitionLength, index);
                    ++index;
                    ++leftPartitionLength;
                } else {
                    ++index;
                }
            }

            if (leftPartitionLength < rightPartitionLength) {
                sort(array, fromIndex, fromIndex + leftPartitionLength);
                fromIndex = toIndex - rightPartitionLength;
            } else {
                sort(array, toIndex - rightPartitionLength, toIndex);
                toIndex = fromIndex + leftPartitionLength;
            }
        }
    }

    private static void insertionsort(int[] array, int fromIndex, int toIndex) {
        for (int i = fromIndex + 1; i < toIndex; ++i) {
            int current = array[i];
            int j = i  - 1;

            while (j >= fromIndex && array[j] > current) {
                array[j + 1] = array[j];
                --j;
            }

            array[j + 1] = current;
        }
    }

    private static final int SIZE = 500_000;
    private static final int FROM = 100;
    private static final int TO = SIZE - 100;

    public static void main(String[] args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);
        int[] array1 = getRandomArray(SIZE, 0, 1_000_000_000, random);
        int[] array2 = array1.clone();
        int[] array3 = array1.clone();

        System.out.println("Seed: " + seed);
        long startTime = System.nanoTime();
        IntQuicksort.sort(array1, FROM, TO);
        long endTime = System.nanoTime();

        System.out.printf("IntQuicksort.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        startTime = System.nanoTime();
        ParallelIntQuicksort.sort(array2, FROM, TO);
        endTime = System.nanoTime();

        System.out.printf("ParallelIntQuicksort.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        startTime = System.nanoTime();
        Arrays.sort(array3, FROM, TO);
        endTime = System.nanoTime();

        System.out.printf("Arrays.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        System.out.println("Arrays are equal: " + 
                           (Arrays.equals(array1, array2) &&
                            Arrays.equals(array2, array3)));
    }

    public static int[] getRandomArray(int size, 
                                       int minimum, 
                                       int maximum, 
                                       Random random) {
        int[] array = new int[size];

        for (int i = 0; i < size; ++i) {
            array[i] = random.nextInt(maximum - minimum + 1) + minimum;
        }

        return array;
    }
}

Util.java:

package net.coderodde.util;

/**
 * This class contains miscellaneous utility methods.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 5, 2016)
 */
public class Util {

    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static int median(int a, int b, int c) {
        if (a <= b) {
            if (c <= a) {
                return a;
            }

            return b <= c ? b : c;
        } 

        if (c <= b) {
            return b;
        }

        return a <= c ? a : c;
    } 
}

The most optimistic performance figures I got (at 500 000 elements, 2 physical cores) are as follows:


Seed: 534926229415440
IntQuicksort.sort in 105.80 milliseconds.
ParallelIntQuicksort.sort in 67.52 milliseconds.
Arrays.sort in 148.02 milliseconds.
Arrays are equal: true

Please, tell me anything that comes to mind.

\$\endgroup\$
4
  • \$\begingroup\$ (I expected Futures and Executors. Does it look worth-while splitting core-count according to the actual size of the partitions?) \$\endgroup\$
    – greybeard
    Mar 5, 2016 at 18:59
  • \$\begingroup\$ Gives me a little bit more control over what happens. Also, it makes no sense to create threads for rather small ranges; hence, I require that each thread receives no less than MINIMUM_THREAD_WORKLOAD array components to sort. \$\endgroup\$
    – coderodde
    Mar 5, 2016 at 20:58
  • \$\begingroup\$ (Quick take - have to sort things out first, including Sunday, Cray, weather, Floyd-Rivest, …) partition is duplicated, run-time of tests too small to give me confidence in steady-state, use fork/join/Future/Executor(CommonPool, …), the key to finishing early is to put available resources to use from beginning to end: not paralleling partition is harmful. (Another interesting minimisation goal is energy spent.) \$\endgroup\$
    – greybeard
    Mar 6, 2016 at 8:19
  • \$\begingroup\$ (Somehow feel that with Mergesort using two threads to the end, Quicksort is at a disadvantage. Anybody know about the Merge part in PPMQSort? "The [Parallel Partition and Merge QuickSort] recursively divides an unsorted input array into partially sorted partitions up to Cutoff length using nested multithreading...") \$\endgroup\$
    – greybeard
    Mar 7, 2016 at 8:21

2 Answers 2

4
\$\begingroup\$

One thing that comes to mind is that you are forking more new threads than you need to.

    ParallelQuicksortThread leftThread = 
            new ParallelQuicksortThread(array,
                                        fromIndex,
                                        fromIndex + leftPartitionLength,
                                        cores / 2);
    ParallelQuicksortThread rightThread =
            new ParallelQuicksortThread(array,
                                        toIndex - rightPartitionLength,
                                        toIndex,
                                        cores - cores / 2);

Since the current thread is not going to be doing anything until it joins with both of leftThread and rightThread, you could actually do the work of one of those two threads on the current thread. That saves the overhead of creating a thread.

The other comment is that the "best" speedup (IntQuicksort versus ParallelIntQuicksort) that you are seeing is in the ballpark of what I would expect for a 2 core machine. A significant amount of work (the initial partitioning) has to be done on the first thread before it forks the child threads. Also note that if the initial partitioning gives partitions whose sizes are very different, then workload won't be balanced. One thread will finish a lot sooner than the other, and the overall speedup won't be as great.

Finally, I am a bit dubious of your benchmarking methodology. You don't seem to allow for JVM warmup effects.

\$\endgroup\$
0
\$\begingroup\$

I would use Fork/Join Framework and don't manage threads manually.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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