CODEWITHSUNDEEP
c#parallel-processinginvokequicksort
Colin Roe
Colin Roe

Reputation: 804

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

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;
    }

Upvotes: 4

Views: 3246

Answers (3)

Larry OBrien
Larry OBrien

Reputation: 8606

All those recursive invokes are killing you. This article https://web.archive.org/web/20230128064428/http://reedcopsey.com/2010/02/26/parallelism-in-net-part-11-divide-and-conquer-via-parallel-invoke/ is very relevant.

Upvotes: 2

riwalk
riwalk

Reputation: 14233

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.

Upvotes: 2

dylansweb
dylansweb

Reputation: 684

Contention surrounding the use of the SwapElements method? Try dropping the logic of the SwapElements method right into your method/loop, rather than calling out to it...this will allow it to be a part of what happens on each parallell thread that is spawned, rather than being a potential bottleneck. See if that get's you anything...just a suggestion though, not sure if it will prove useful.

Upvotes: 0

Related Questions