那些遇到过的问题

如果调用是在一个单独的方法中,为什么Parallel.Invoke要快得多？

fab*_*fab 15 c# parallel-processing quicksort .net-core

我实施了3次QuickSort算法并测量了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); }
        }
    }

}
Run Code Online (Sandbox Code Playgroud)

3. Parallel.Invoke()在一个单独的方法

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

}
Run Code Online (Sandbox Code Playgroud)

完整代码

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

    }

}
Run Code Online (Sandbox Code Playgroud)

你在这里找到我的代码: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
Run Code Online (Sandbox Code Playgroud)

Evk*_*Evk 7

修复注释中提到的排序已排序数组的问题后,您的问题仍然会重现.

我认为原因在于你传递给lambda的方式和内容Parallel.Invoke.

在第一种情况下(何时Parallel.Invoke是内部QuickSort方法):

Parallel.Invoke(
    () => QuickSort(array, left, j),
    () => QuickSort(array, i, right)
);
Run Code Online (Sandbox Code Playgroud)

您捕获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--;
    }
  }
Run Code Online (Sandbox Code Playgroud)

这证实了上述观点.

但是,如果您转向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;
    }
  }
  ...
Run Code Online (Sandbox Code Playgroud)

现在,我假设访问对象字段(通常在堆上)比访问本地变量(通常在CPU寄存器中的堆栈上)慢一些,因此使用单独方法的版本更快.Eric Lippert在评论中也指出:

对于字段而言,抖动可能会比本地人更糟糕,因为它不会积极地注册它们.

您可以通过修改第一个版本来确认以上内容,如下所示:

    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);
            }
        }
    }
}
Run Code Online (Sandbox Code Playgroud)

然后两种方法的执行时间都是相同的.

正如@Eugene在评论和他的回答中提到的那样 - 除了字段和局部变量访问之外,可能还有其他一些东西可以减缓这种情况 - 例如构造和(可能)上面提到的编译器生成的类的垃圾收集.但是,这些都是相同源根的结果 - 以不同方式捕获闭包中的局部变量.

Eug*_*voy 3

!!!!!!!!! 这个答案目前并不实际！！！！我知道这不是一个正确的答案，只是想让它可见：尝试更改测试顺序：

Measure("P. Separate Method", () => ParallelSeparateMethodQuickSort.Sort(array));
Measure("Sequential\t", () => SequentialQuickSort.Sort(array));
Measure("Parallel\t", () => ParallelQuickSort.Sort(array));
Run Code Online (Sandbox Code Playgroud)

你会看到：

P. Separate Method:     Elapsed=8710
Sequential      :       Elapsed=4140
Parallel        :       Elapsed=7928
P. Separate Method:     Elapsed=9033
Sequential      :       Elapsed=4098
Parallel        :       Elapsed=7881
Run Code Online (Sandbox Code Playgroud)

所以我认为你的测试是错误的，这个问题没有意义。快速调查表明，在每个测试中您都更改了源数组，因此下一个测试已经对数组进行了排序。

ps但是我觉得这个问题确实存在。如果您尝试更正代码，您会发现调用单独的方法速度更快！

pps 请告诉我是否有人有答案或者问题是否得到纠正

归档时间：

查看次数：

275 次

最近记录：

7 年，7 月 前
相关归档
Selenium c#Webdriver:等到元素存在 173
C#Linq两个日期之间的日期 68
C#中的流畅接口和继承 57
GNU与rsync并行 7
并行动态规划 6
.NET Core Web API 部署到 Azure 后无法工作 6
Haskell:为什么`par`定义它的方式？ 5
CUDA:分散沟通模式 5
F#内部是否默认并行运行代码？ 3
瞬态BackgroundService，返回的实例总是不同？ 0
难疑归档
使用Git将最近的提交移动到新分支 4647
确定已安装的PowerShell版本 2543
如何通过引用传递变量？ 2480
SCSS和Sass有什么区别？ 1760
如何在Java中打破嵌套循环？ 1751
如何在Notepad ++中格式化XML？ 1661
没有指定分支的"git push"的默认行为 1339
如何在不使用存储库的情况下将Docker镜像从一个主机复制到另一个主机 1181
如何从Git存储库中删除.DS_Store文件？ 1167
Objective-C中的快捷方式用于连接NSStrings 1114