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

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

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

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

Answer 2

所有这些递归调用都会害死你。本文https://web.archive.org/web/20230128064428/http://reedcopsey.com/2010/02/26/parallelism-in-net-part-11-divide-and-conquer-via-parallel -invoke/ 非常相关。

Answer 3

围绕 SwapElements 方法的使用存在争议？尝试将 SwapElements 方法的逻辑直接放入您的方法/循环中，而不是调用它......这将允许它成为生成的每个并行线程上发生的事情的一部分，而不是成为潜在的瓶颈。看看这是否对您有帮助……不过只是一个建议，不确定它是否有用。