我执行了 3 次 QuickSort-Algorithm 并测量了对 5000 万个随机数进行排序的时间:

1. 顺序(大约需要 14 秒)

2. 使用 Parallel.Invoke() 作为排序算法的相同方法(耗时约 12 秒)

3. 使用 Parallel.Invoke() 在单独的方法中(耗时约 7 秒)

所以我的问题是:如果在单独的方法中调用，为什么 Parallel.Invoke() 会快得多？ 在我的电脑上，示例 3. 的速度是示例 2 的两倍多。

2。使用 Parallel.Invoke() 作为排序算法的相同方法

public class ParallelQuickSort
{

    private const int Threshold = 100;

    public static void Sort(int[] array)
    {
        if (array == null || array.Length == 0)
        {
            new ArgumentException("number array must be at least of length 1");
        }
        QuickSort(array, 0, array.Length - 1);
    }

    private static void QuickSort(int[] array, int left, int right)
    {
        var i = left;
        var j = right;
        var m = array[(left + right) / 2];
        while (i <= j)
        {
            while (array[i] < m) { i++; }
            while (array[j] > m) { j--; }
            if (i <= j)
            {
                var t = array[i]; array[i] = array[j]; array[j] = t;
                i++; j--;
            }
        }
        if (j - left > Threshold && right - i > Threshold)
        {
            Parallel.Invoke(
                () => QuickSort(array, left, j),
                () => QuickSort(array, i, right)
            );
        }
        else
        {
            if (j > left) { QuickSort(array, left, j); }
            if (i < right) { QuickSort(array, i, right); }
        }
    }

}

3。在单独的方法

public class ParallelSeparateMethodQuickSort
{

    private const int Threshold = 100;

    public static void Sort(int[] array)
    {
        if (array == null || array.Length == 0)
        {
            new ArgumentException("number array must be at least of length 1");
        }
        QuickSort(array, 0, array.Length - 1);
    }

    private static void QuickSort(int[] array, int left, int right)
    {
        var i = left;
        var j = right;
        var m = array[(left + right) / 2];
        while (i <= j)
        {
            while (array[i] < m) { i++; }
            while (array[j] > m) { j--; }
            if (i <= j)
            {
                var t = array[i]; array[i] = array[j]; array[j] = t;
                i++; j--;
            }
        }
        if (j - left > Threshold && right - i > Threshold)
        {
            ParallelInvoke(array, left, j, i, right);
        }
        else
        {
            if (j > left) { QuickSort(array, left, j); }
            if (i < right) { QuickSort(array, i, right); }
        }
    }

    private static void ParallelInvoke(int[] array, int left, int j, int i, int right)
    {
        Parallel.Invoke(
                () => QuickSort(array, left, j),
                () => QuickSort(array, i, right)
            );
    }

}

完整代码

using System;
using System.Threading.Tasks;
using System.Diagnostics;

namespace parallelQuicksort
{
    class Program
    {
        static void Main(string[] args)
        {
            const int N = 50_000_000;
            for (int i = 0; i < 5; i++)
            {
                var array = GetRandomArray(N);
                Measure("Sequential\t", () => SequentialQuickSort.Sort(array));
                array = GetRandomArray(N);
                Measure("Parallel\t", () => ParallelQuickSort.Sort(array));
                array = GetRandomArray(N);
                Measure("P. Separate Method", () => ParallelSeparateMethodQuickSort.Sort(array));
            }
        }

        private static int[] GetRandomArray(int length)
        {
            var random = new Random(4711);
            var array = new int[length];
            for (int i = 0; i < length; i++)
            {
                array[i] = random.Next();
            }
            return array;
        }

        public static void Measure(string name, Action action)
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            action();
            stopwatch.Stop();
            var time = stopwatch.ElapsedMilliseconds;
            Console.WriteLine($"{name}: \tElapsed={time}");
        }
    }

    public class SequentialQuickSort
    {
        public static void Sort(int[] array)
        {
            if (array == null || array.Length == 0)
            {
                new ArgumentException("number array must be at least of length 1");
            }
            QuickSort(array, 0, array.Length - 1);
        }

        private static void QuickSort(int[] array, int left, int right)
        {
            var i = left;
            var j = right;
            var m = array[(left + right) / 2];
            while (i <= j)
            {
                while (array[i] < m) { i++; }
                while (array[j] > m) { j--; }
                if (i <= j)
                {
                    var t = array[i]; array[i] = array[j]; array[j] = t;
                    i++; j--;
                }
            }

            if (j > left) { QuickSort(array, left, j); }
            if (i < right) { QuickSort(array, i, right); }
        }
    }

    public class ParallelQuickSort
    {

        private const int Threshold = 100;

        public static void Sort(int[] array)
        {
            if (array == null || array.Length == 0)
            {
                new ArgumentException("number array must be at least of length 1");
            }
            QuickSort(array, 0, array.Length - 1);
        }

        private static void QuickSort(int[] array, int left, int right)
        {
            var i = left;
            var j = right;
            var m = array[(left + right) / 2];
            while (i <= j)
            {
                while (array[i] < m) { i++; }
                while (array[j] > m) { j--; }
                if (i <= j)
                {
                    var t = array[i]; array[i] = array[j]; array[j] = t;
                    i++; j--;
                }
            }
            if (j - left > Threshold && right - i > Threshold)
            {
                Parallel.Invoke(
                    () => QuickSort(array, left, j),
                    () => QuickSort(array, i, right)
                );
            }
            else
            {
                if (j > left) { QuickSort(array, left, j); }
                if (i < right) { QuickSort(array, i, right); }
            }
        }

    }

    public class ParallelSeparateMethodQuickSort
    {

        private const int Threshold = 100;

        public static void Sort(int[] array)
        {
            if (array == null || array.Length == 0)
            {
                new ArgumentException("number array must be at least of length 1");
            }
            QuickSort(array, 0, array.Length - 1);
        }

        private static void QuickSort(int[] array, int left, int right)
        {
            var i = left;
            var j = right;
            var m = array[(left + right) / 2];
            while (i <= j)
            {
                while (array[i] < m) { i++; }
                while (array[j] > m) { j--; }
                if (i <= j)
                {
                    var t = array[i]; array[i] = array[j]; array[j] = t;
                    i++; j--;
                }
            }
            if (j - left > Threshold && right - i > Threshold)
            {
                ParallelInvoke(array, left, j, i, right);
            }
            else
            {
                if (j > left) { QuickSort(array, left, j); }
                if (i < right) { QuickSort(array, i, right); }
            }
        }

        private static void ParallelInvoke(int[] array, int left, int j, int i, int right)
        {
            Parallel.Invoke(
                    () => QuickSort(array, left, j),
                    () => QuickSort(array, i, right)
                );
        }

    }

}

您可以在这里找到我的代码:https://github.com/Lazzaretti/ParallelQuicksort

输出

Sequential      :       Elapsed=14534
Parallel        :       Elapsed=11960
P. Separate Method:     Elapsed=6353
Sequential      :       Elapsed=14620
Parallel        :       Elapsed=11954
P. Separate Method:     Elapsed=6647
Sequential      :       Elapsed=14529
Parallel        :       Elapsed=11870
P. Separate Method:     Elapsed=6389
Sequential      :       Elapsed=14512
Parallel        :       Elapsed=11787
P. Separate Method:     Elapsed=6590
Sequential      :       Elapsed=16203
Parallel        :       Elapsed=11738
P. Separate Method:     Elapsed=6674

最佳答案

解决了对评论中提到的已排序数组进行排序的问题后，您的问题仍然重现。

我认为原因是您传递给 Parallel.Invoke 的 lambda 捕获的内容和方式。

第一种情况(当 Parallel.Invoke 位于 QuickSort 方法中时):

Parallel.Invoke(
    () => QuickSort(array, left, j),
    () => QuickSort(array, i, right)
);

您捕获了 5 个变量，所有这些变量都用于整个 QuickSort 方法。所有这些变量都成为编译器生成类的字段。这意味着整个 QuickSort 方法现在适用于对象字段而不是局部变量。如果你反编译那个方法，你会看到类似这样的东西:

  var cDisplayClass20 = new SomeCompilerGeneratedClass();
  cDisplayClass20.array = array;
  cDisplayClass20.left = left;
  cDisplayClass20.right = right;
  cDisplayClass20.i = cDisplayClass20.left;
  cDisplayClass20.j = cDisplayClass20.right;
  int num1 = cDisplayClass20.array[(cDisplayClass20.left + cDisplayClass20.right) / 2];
  while (cDisplayClass20.i <= cDisplayClass20.j) // field access
  {
    while (cDisplayClass20.array[cDisplayClass20.i] < num1) // field access
      cDisplayClass20.i++;
    while (cDisplayClass20.array[cDisplayClass20.j] > num1) // and again
      cDisplayClass20.j--;
    if (cDisplayClass20.i <= cDisplayClass20.j) // again field access
    {
      // they are everywhere
      int num2 = cDisplayClass20.array[cDisplayClass20.i];
      cDisplayClass20.array[cDisplayClass20.i] = cDisplayClass20.array[cDisplayClass20.j];
      cDisplayClass20.array[cDisplayClass20.j] = num2;
      cDisplayClass20.i++;
      cDisplayClass20.j--;
    }
  }

这证实了上面的观点。

但是，如果您将 Parallel.Invoke 移动到单独的方法中，情况就不再是这样了。仍然捕获了 5 个变量，但这并不影响整个 QuickSort 方法，因为捕获现在发生在单独的 ParallelInvoke 方法中，因此是本地化的。 QuickSort 仍然适用于局部变量，而不适用于编译器生成类的字段。如果你用单独的方法反编译版本，它看起来就像你写的一样:

  int index1 = left;
  int index2 = right;
  int num1 = array[(left + right) / 2];
  while (index1 <= index2) // local variables
  {
    while (array[index1] < num1) // num1 is local variable
      ++index1;
    while (array[index2] > num1)
      --index2;
    if (index1 <= index2) // local variables again
    {
      int num2 = array[index1];
      array[index1] = array[index2];
      array[index2] = num2;
      ++index1;
      --index2;
    }
  }
  ...

现在，我假设访问对象字段(通常在堆上)比访问局部变量(通常在堆栈上\在 CPU 寄存器中)要慢一些，因此具有单独方法的版本更快。 Eric Lippert 还在评论中指出:

The jitter will likely do a worse job with the fields than it will with the locals because it will not enregister them as aggressively.

您可以像这样修改您的第一个版本来确认以上内容:

    private static void QuickSort(int[] array, int left, int right) {
        var i = left;
        var j = right;
        var m = array[(left + right) / 2];
        while (i <= j) {
            while (array[i] < m) {
                i++;
            }

            while (array[j] > m) {
                j--;
            }

            if (i <= j) {
                var t = array[i];
                array[i] = array[j];
                array[j] = t;
                i++;
                j--;
            }
        }

        if (j - left > Threshold && right - i > Threshold) {
            // copy all variables you pass to lambda
            // so that their capture does not affect the whole method
            var tmpArray = array;
            var tmpLeft = left;
            var tmpJ = j;
            var tmpI = i;
            var tmpRight = right;
            Parallel.Invoke(
                () => QuickSort(tmpArray, tmpLeft, tmpJ),
                () => QuickSort(tmpArray, tmpI, tmpRight)
            );
        }
        else {
            if (j > left) {
                QuickSort(array, left, j);
            }

            if (i < right) {
                QuickSort(array, i, right);
            }
        }
    }
}

然后两种方法的执行时间将相同。

正如@Eugene 在评论和他的回答中提到的那样 - 除了字段与局部变量访问之外，可能还有其他事情会减慢速度 - 例如上述编译器生成的类的构造和(可能)垃圾收集。然而，这些都是同源根的结果——以不同方式在闭包中捕获局部变量。

关于c# - 如果在单独的方法中调用，为什么 Parallel.Invoke 会快得多？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49818054/