Почему Parallel.Invoke намного быстрее, если вызов осуществляется отдельным методом?

Я реализовал QuickSort-алгоритм 3 раза и измерил время сортировки 50 миллионов случайных чисел:

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

}

Полный код

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

Ответы

Ответ 1

После исправления этой проблемы с сортировкой уже отсортированного массива, упомянутого в комментариях, ваша проблема все еще воспроизводится.

Я думаю, что причина в том, как и что захвачено лямбдами, вы переходите к Parallel.Invoke.

В первом случае (когда 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), поэтому версия с отдельным методом выполняется быстрее. Эрик Липперт также замечает в комментариях, что:

Джиттер, скорее всего, сделает более худшую работу с полями, чем будет с местными жителями, потому что он не будет регистрировать их так агрессивно.

Вы можете подтвердить это, изменив первую версию следующим образом:

    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 в комментариях и в своем ответе - могут быть и другие вещи, которые замедляют это, помимо поля с доступом к локальным переменным, например, строительство и (потенциально) сборку мусора классов, созданных компилятором, упомянутых выше. Тем не менее, это все последствия одного и того же корня источника - по-разному захватывать локальные переменные.

Ответ 2

!!!!!!!!! Этот ответ сейчас не актуальен !!!!! Я знаю, что это не правильный ответ, просто хочу сделать его видимым: попробуйте изменить порядок тестов:

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

И вы увидите:

P. Separate Method:     Elapsed=8710
Sequential      :       Elapsed=4140
Parallel        :       Elapsed=7928
P. Separate Method:     Elapsed=9033
Sequential      :       Elapsed=4098
Parallel        :       Elapsed=7881

Поэтому я думаю, что ваши тесты ошибочны, и этот вопрос не имеет смысла. И быстрое расследование показывает, что в каждом из тестов вы меняете исходный массив, поэтому каждый следующий тест уже отсортировал массив.

ps Но я думаю, что этот вопрос действительно существует. Если вы попытаетесь исправить код, вы увидите, что вызов отдельного метода работает быстрее!

pps plz сообщите мне, если у кого-то есть ответ или если вопрос был исправлен

Ответ 3

Для этого есть две причины: дополнительный вызов конструктора (~ 30% времени) и полевой доступ вместо переменного доступа (~ 30% времени). Когда вы используете приложение непосредственно внутри вашего метода, автоматически генерируемый класс для этого приложения создается при каждом вызове этого метода (который в вашем случае приводит к сборкам мусора, рис. Ниже).

enter image description here

И все вызовы переменных теперь вызывают также и поля (что медленнее), как указано в @Evk.

enter image description here

Но когда ваше приложение обернуто внутри другого метода, оно создается только при вызове метода-оболочки. Таким образом, в случае выделенного объекта объекта оболочки создается только тогда, когда if (j - left> Threshold && right - i> Threshold) был "true". Как описано в @Evk, вы можете копировать значения в новые переменные, объявленные внутри if, это даст вам тот же результат, что и перенос его в метод.

Я запустил профайлер и получил это (посмотрите на выделенную строку): Profiler results

Это быстрый раздельный метод: enter image description here

И это медленный метод: enter image description here

Кроме того, посмотрите на скомпилированную версию (обратите внимание, что в медленном случае мы обращаемся к полям, а не к переменным):

 //Compilation of "if (j - left > Threshold && right - i > Threshold)"

//Slow method:
    // [106 13 - 106 63]
    IL_012f: ldloc.0      // 'CS$<>8__locals0'
    IL_0130: ldfld        int32 parallelQuicksort.ParallelQuickSort/'<>c__DisplayClass2_0'::j
    IL_0135: ldloc.0      // 'CS$<>8__locals0'
    IL_0136: ldfld        int32 parallelQuicksort.ParallelQuickSort/'<>c__DisplayClass2_0'::left
    IL_013b: sub          
    IL_013c: ldc.i4.s     100 // 0x64
    IL_013e: ble.s        IL_0153
    IL_0140: ldloc.0      // 'CS$<>8__locals0'
    IL_0141: ldfld        int32 parallelQuicksort.ParallelQuickSort/'<>c__DisplayClass2_0'::right
    IL_0146: ldloc.0      // 'CS$<>8__locals0'
    IL_0147: ldfld        int32 parallelQuicksort.ParallelQuickSort/'<>c__DisplayClass2_0'::i
    IL_014c: sub          
    IL_014d: ldc.i4.s     100 // 0x64
    IL_014f: cgt          
    IL_0151: br.s         IL_0154
    IL_0153: ldc.i4.0     
    IL_0154: stloc.s      V_8


//fast separate method

    // [151 13 - 151 63]
    IL_006b: ldloc.1      // j
    IL_006c: ldarg.1      // left
    IL_006d: sub          
    IL_006e: ldc.i4.s     100 // 0x64
    IL_0070: ble.s        IL_007b
    IL_0072: ldarg.2      // right
    IL_0073: ldloc.0      // i
    IL_0074: sub          
    IL_0075: ldc.i4.s     100 // 0x64
    IL_0077: cgt          
    IL_0079: br.s         IL_007c
    IL_007b: ldc.i4.0     
    IL_007c: stloc.s      V_8