Parallel.ForEach медленнее, чем обычно, foreach

Question

Я играю с Parallel.ForEach в консольном приложении C#, но, похоже, не может быть прав. Я создаю массив со случайными числами, и у меня есть последовательный foreach и Parallel.ForEach, который находит наибольшее значение в массиве. Примерно с тем же кодом в C++ я начал видеть компромисс с использованием нескольких потоков при значениях 3M в массиве. Но Parallel.ForEach в два раза медленнее даже при значениях 100M. Что я делаю не так?

class Program 
{ 
    static void Main(string[] args) 
    { 
     dostuff(); 

    } 

    static void dostuff() { 
     Console.WriteLine("How large do you want the array to be?"); 
     int size = int.Parse(Console.ReadLine()); 

     int[] arr = new int[size]; 
     Random rand = new Random(); 
     for (int i = 0; i < size; i++) 
     { 
      arr[i] = rand.Next(0, int.MaxValue); 
     } 

     var watchSeq = System.Diagnostics.Stopwatch.StartNew(); 
     var largestSeq = FindLargestSequentially(arr); 
     watchSeq.Stop(); 
     var elapsedSeq = watchSeq.ElapsedMilliseconds; 
     Console.WriteLine("Finished sequential in: " + elapsedSeq + "ms. Largest = " + largestSeq); 

     var watchPar = System.Diagnostics.Stopwatch.StartNew(); 
     var largestPar = FindLargestParallel(arr); 
     watchPar.Stop(); 
     var elapsedPar = watchPar.ElapsedMilliseconds; 
     Console.WriteLine("Finished parallel in: " + elapsedPar + "ms Largest = " + largestPar); 

     dostuff(); 
    } 

    static int FindLargestSequentially(int[] arr) { 
     int largest = arr[0]; 
     foreach (int i in arr) { 
      if (largest < i) { 
       largest = i; 
      } 
     } 
     return largest; 
    } 

    static int FindLargestParallel(int[] arr) { 
     int largest = arr[0]; 
     Parallel.ForEach<int, int>(arr,() => 0, (i, loop, subtotal) => 
     { 
      if (i > subtotal) 
       subtotal = i; 
      return subtotal; 
     }, 
     (finalResult) => { 
      Console.WriteLine("Thread finished with result: " + finalResult); 
      if (largest < finalResult) largest = finalResult; 
     } 
     ); 
     return largest; 
    } 
} 

Answer 1

Это производственные характеристики, имеющие очень небольшое тело делегата.

Мы можем добиться более высокой производительности, используя разбиение. В этом случае делегат тела выполняет работу с большим объемом данных.

static int FindLargestParallelRange(int[] arr) 
{ 
    object locker = new object(); 
    int largest = arr[0]; 
    Parallel.ForEach(Partitioner.Create(0, arr.Length),() => arr[0], (range, loop, subtotal) => 
    { 
     for (int i = range.Item1; i < range.Item2; i++) 
      if (arr[i] > subtotal) 
       subtotal = arr[i]; 
     return subtotal; 
    }, 
    (finalResult) => 
    { 
     lock (locker) 
      if (largest < finalResult) 
       largest = finalResult; 
    }); 
    return largest; 
} 

Обратите внимание на синхронизацию локального делегирования. Также обратите внимание на необходимость правильной инициализации localInit: () => arr[0] вместо () => 0.

Разметка с PLINQ:

static int FindLargestPlinqRange(int[] arr) 
{ 
    return Partitioner.Create(0, arr.Length) 
     .AsParallel() 
     .Select(range => 
     { 
      int largest = arr[0]; 
      for (int i = range.Item1; i < range.Item2; i++) 
       if (arr[i] > largest) 
        largest = arr[i]; 
      return largest; 
     }) 
     .Max(); 
} 

Я настоятельно рекомендую бесплатную книгу Patterns of Parallel Programming Стивен Toub.

Answer 2

Некоторые мысли здесь: В параллельном случае задействована логика управления потоками, которая определяет, сколько потоков оно хочет использовать. Вероятно, эта логика управления потоками работает на вашем основном потоке. Каждый раз, когда поток возвращается с новым максимальным значением, логика управления запускает и определяет следующий рабочий элемент (следующий номер для обработки в вашем массиве). Я почти уверен, что для этого требуется какая-то блокировка. В любом случае определение следующего элемента может даже стоить больше, чем сама операция сравнения.

Это звучит как большая работа (накладные расходы) для меня, чем один поток, который обрабатывает одно число за другим. В однопоточном случае есть ряд оптимизаций в игре: никаких проверок границ, ЦП может загружать данные в кеш первого уровня в ЦП и т. Д. Не уверен, какая из этих оптимизаций применяется для параллельного случая.

Имейте в виду, что на обычной настольной машине доступно только 2-4 физических ядра процессора, поэтому у вас никогда не будет больше, чем на самом деле. Поэтому, если накладные расходы параллельной обработки превышают 2-4 раза от однопоточной операции, параллельная версия будет неизбежно медленнее, что вы наблюдаете.

Вы пытались запустить это на 32-ядерном компьютере? ;-)

Лучшим решением будет определение неперекрывающихся диапазонов (начальный + стоп-индекс), охватывающих весь массив, и каждая параллельная задача обрабатывает один диапазон. Таким образом, каждая параллельная задача может внутренне выполнять жесткий однопоточный цикл и возвращаться только после обработки всего диапазона. Вероятно, вы даже можете определить почти оптимальное количество диапазонов, основанное на количестве логических ядер машины. Я не пробовал это, но я уверен, что вы увидите улучшение по однопоточному случаю.

Answer 3

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

В одном потоке, чтобы найти максимальное значение, мы можем взять первое число в качестве нашего максимального значения и сравнить его с любым другим числом в массиве. Если один из чисел больше нашего первого числа, мы поменяемся и продолжим. Таким образом, мы получаем доступ к каждому числу в массиве один раз, в общей сложности N сравнений.

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

В Parallel For Loop ниже массив делится на явное количество потоков, определяемое переменной threadNumber. Это ограничивает накладные расходы на вызовы функций на низкое число.

Обратите внимание, что при низких значениях параллельные петли работают медленнее. Тем не менее, за 100 М, происходит уменьшение времени.

static int FindLargestParallel(int[] arr) 
{ 
    var answers = new ConcurrentBag<int>(); 
    int threadNumber = 4; 

    int partitionSize = arr.Length/threadNumber; 
    Parallel.For(0, /* starting number */ 
     threadNumber+1, /* Adding 1 to threadNumber in case array.Length not evenly divisible by threadNumber */ 
     i => 
     { 
      if (i*partitionSize < arr.Length) /* check in case # in array is divisible by # threads */ 
      { 
       var max = arr[i*partitionSize]; 
       for (var x = i*partitionSize; 
        x < (i + 1)*partitionSize && x < arr.Length; 
        ++x) 
       { 
        if (arr[x] > max) 
         max = arr[x]; 
       } 
       answers.Add(max); 
      } 
     }); 

    /* note the shortcut in finding max in the bag */  
    return answers.Max(i=>i); 
} 

Answer 4

Как уже отмечали другие ответчики, действие, которое вы пытаетесь выполнить против каждого элемента здесь, настолько незначительно, что существует множество других факторов, которые в конечном итоге имеют больший вес, чем фактическая работа, которую вы делаете. Они могут включать в себя:

• JIT оптимизация
• предсказание ветвлений процессора
• ввод/вывод (вывод результатов резьбы в то время как таймер работает)
• стоимости ссылающихся делегатов
• стоимость управления задачами
• система неправильно угадывает, какая стратегия потока будет оптимальной
• кеширование памяти/процессора
• давление памяти
• среда (отладка)
• т.д.

Запуск каждого подхода один раз не является адекватным способом тестирования, поскольку он позволяет ряд вышеперечисленных факторов взвешивать в большей степени на одна итерация, чем другая. Вы должны начать с более надежной стратегии бенчмаркинга.

Кроме того, ваша реализация на самом деле опасна неправильно. The documentation в частности, говорится:

localFinally делегат вызывается один раз в задачу выполнить окончательное решение о локальном состоянии каждой задачи. Этот делегат может одновременно запускаться по нескольким задачам; поэтому вы должны синхронизировать доступ к любым общим переменным.

Вы не синхронизировали свой последний делегат, поэтому ваша функция подвержена условиям гонки, которые могут привести к неправильным результатам.

Как и в большинстве случаев, лучший подход к этому заключается в том, чтобы использовать работу, сделанную людьми умнее, чем мы.In my testing следующий подход оказывается самым быстрым в целом:

return arr.AsParallel().Max();