Why is my Parallel QuickSort method slower than the sequential method?

Question

I am new to parallel programming and I am unsure why the QuickSortParallel method is slower than my sequential version (Without the Parallel.Invoke). I have a jagged array that consists of a hundred thousand 9 digit numbers that I pass to be sorted. Unfortunately, when I use the QuickSortParallel method it ends up being almost 5 times slower than the sequential version.

Could I do more than just using Parallel.Invoke on the data source?

    public static void QuickSort_Parallel<T>(T[] array2) where T : IComparable<T>
    {
        QuickSortParallel(array2, 0, array2.Length - 1);
    }

    private static void QuickSortParallel<T>(T[] array2, int left, int right)
        where T : IComparable<T>
    {
        if (left >= right)
        {
            return;
        }

        SwapElements(array2, left, (left + right) / 2); //median pivot
        int last = left;
        for (int current = left + 1; current <= right; ++current)
        {
            //CompareTo, compares current array index value with
            if (array2[current].CompareTo(array2[left]) < 0)
            {
                ++last;
                SwapElements(array2, last, current);
            }
        }

        SwapElements(array2, left, last);
        //Recursive
        //Executes each of the provided actions in parallel.
        Parallel.Invoke(
            () => QuickSortParallel(array2, left, last - 1),
            () => QuickSortParallel(array2, last + 1, right)
        );
    }

    static void SwapElements<T>(T[] array2, int i, int j)
    {
        T temp = array2[i];
        array2[i] = array2[j];
        array2[j] = temp;
    }

What are you actual timings like? Are we talking milliseconds or seconds? (I'm hoping ms for just 100K elements.) — Larry OBrien
What about checking recursive depth and going sequencial (calling QuickSortParallel() sequencially) after it exceed a certain thresold (ex : greater than the NumberOfPhysicalCPU * someconstant ) ? — tigrou

riwalk riwalk · Accepted Answer · 2012-10-16T00:48:34

More than likely, you're problems are coming from overhead with the threads.

Using threads normally makes CPU intensive work faster, however starting a new thread involves substantial overhead, and if you're giving too many threads too little work, then you can make your program run slower.

When you run the following line:

    Parallel.Invoke(
        () => QuickSortParallel(array2, left, last - 1),
        () => QuickSortParallel(array2, last + 1, right)
    );

...you are possibly causing the current thread to spawn two more threads (depending on how Parallel.Invoke is implemented). If my mental math is correct (and if Parallel.Invoke does indeed create new threads), you're creating n * log(n) threads--an enormous number!

If you want to see performance gains, you need to balance the # of threads--more is not always better. A good way to limit the number of threads by using the system thread pool:

System.Threading.ThreadPool.QueueUserWorkItem(
        () => QuickSortParallel(array2, left, last - 1));
System.Threading.ThreadPool.QueueUserWorkItem(
        () => QuickSortParallel(array2, last + 1, right));

...or something along those lines. You could also implement your own threading pool, if you feel inclined to do so. a

Another option is to limit the depth of recursion, thus limiting the number of threads.

Why is my Parallel QuickSort method slower than the sequential method?

3 Answers