c# - 为什么我的并行快速排序方法比顺序方法慢？

Question

我是并行编程的新手，我不确定为什么 QuickSortParallel 方法比我的顺序版本(没有 Parallel.Invoke)慢。我有一个锯齿状数组，其中包含十万个 9 位数字，我传递这些数字进行排序。不幸的是，当我使用 QuickSortParallel 方法时，它最终比顺序版本慢了近 5 倍。

除了在数据源上使用 Parallel.Invoke，我还能做更多的事情吗？

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

Answer 1

您的问题很可能来自线程的开销。

使用线程通常会使 CPU 密集型工作更快，但是启动一个新线程会涉及大量开销，如果您为太多线程提供的工作太少，那么您的程序可能会运行得更慢。

当您运行以下行时:

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

...您可能导致当前线程产生另外两个线程(取决于 Parallel.Invoke 的实现方式)。如果我的心算是正确的(如果 Parallel.Invoke 确实创建了新线程)，那么您正在创建 n * log(n) 线程——数量巨大!

如果您想看到性能提升，您需要平衡线程数——越多并不总是越好。使用系统线程池限制线程数的好方法:

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

...或者类似的东西。如果您愿意，也可以实现自己的线程池。一个

另一种选择是限制递归深度，从而限制线程数。