C# TPL más rápido que C++ PPL?

Question

que codifica una aplicación muy simple que utiliza la fonction de Fibonacci para comparar el TPL de Parallel.ForEach vs PPL de parallel_for_each, y el resultado fue muy extraño, en el PC con 8 núcleos, el C# es 11 segundos más rápido entonces C++.

El mismo resultado en la vista previa de vs2010 y de 2011.

código C#:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Collections.Concurrent; 
using System.Threading.Tasks; 
using System.Diagnostics; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 

      static void Main(string[] args) 
      { 
       var ll = new ConcurrentQueue<Tuple<int, int>>(); 
       var a = new int[12] { 40, 41, 42, 43, 44, 45, 46, 47, 35, 25, 36, 37 }; 

       long elapsed = time_call(() => 
       { 
        Parallel.ForEach(a, (n) => { ll.Enqueue(new Tuple<int, int>(n, fibonacci(n))); }); 
       }); 

       Console.WriteLine("TPL C# elapsed time: " + elapsed + "\n\r"); 
       foreach (var ss in ll) 
       { 
        Console.WriteLine(String.Format("fib<{0}>: {1}", ss.Item1, +ss.Item2)); 
       } 

       Console.ReadLine(); 
      } 

      static long time_call(Action f) 
      { 
       var p = Stopwatch.StartNew(); 
       p.Start(); 
       f(); 
       p.Stop(); 
       return p.ElapsedMilliseconds; 
      } 

      Computes the nth Fibonacci number. 
      static int fibonacci(int n) 
      { 
       if (n < 2) return n; 
       return fibonacci(n - 1) + fibonacci(n - 2); 
      } 
     } 
    } 

código C++:

#include <windows.h> 
#include <ppl.h> 
#include <concurrent_vector.h> 
#include <array> 
#include <tuple> 
#include <algorithm> 
#include <iostream> 

using namespace Concurrency; 
using namespace std; 

template <class Function> 
__int64 time_call(Function&& f) { 
    __int64 begin = GetTickCount(); 
    f(); 
    return GetTickCount() - begin; 
} 

// Computes the nth Fibonacci number. 
int fibonacci(int n) { 
    if (n < 2) return n; 
    return fibonacci(n-1) + fibonacci(n-2); 
} 

int wmain() { 
    __int64 elapsed; 
    array<int, 12> a ={ 40, 41, 42, 43, 44, 45, 46, 47, 35, 25, 36, 37 }; 
    concurrent_vector<tuple<int,int>> results2; 

    elapsed = time_call([&]{ 
     parallel_for_each(a.begin(), a.end(), [&](int n) { 
      results2.push_back(make_tuple(n, fibonacci(n))); 
     }); 
    }); 

    wcout << L"PPL time: " << elapsed << L" ms" << endl << endl; 
    for_each (results2.begin(), results2.end(), [](tuple<int,int>& pair) { 
     wcout << L"fib(" << get<0>(pair) << L"): " << get<1>(pair) << endl; 
    }); 

    cin.ignore(); 
} 

¿Me podría indicar, en donde parte de mi código C++ me equivoco?

group_task Ancho tengo el mismo tiempo como el código C#:

task_group tasks; 
    elapsed = time_call([&] 
    { 
     for_each(begin(a), end(a), [&](int n) 
     { 
      tasks.run([&,n]{results2.push_back(make_tuple(n, fibonacci(n)));}); 
     }); 
     tasks.wait(); 

Answer 1

GetTickCount (http://msdn.microsoft.com/en-us/library/windows/desktop/ms724408%28v=vs. 85% 29.aspx) la función utilizada para medir el tiempo pasado en el lado nativo no es precisa en absoluto. La descripción lo dice:

"La resolución de la función GetTickCount está limitada a la resolución del temporizador del sistema, que normalmente está en el rango de 10 milisegundos a 16 milisegundos."

Según mi experiencia con GetSystemTime, arroja mejores resultados en Windows Vista y más (en Windows XP tiene una resolución similar a la del tick si no recuerdo mal). O mejor, puede usar para mediciones de grano fino algunas otras API-s que ofrecen una resolución de sub mils. Probablemente en su caso, la creación de grandes conjuntos de datos sería más útil, para tener algunos datos significativos.

Answer 2

Estas son las explicaciones de Rahul Patil v Microsoft equipo

Hola,

Gracias por traer esto para arriba. De hecho, ha identificado la sobrecarga asociada con el paralelo predeterminado para *, especialmente cuando el número de iteraciones es pequeño y el tamaño del trabajo es variable. El paralelo predeterminado comienza con la división del trabajo en 8 segmentos 0 (en 8 núcleos). A medida que el trabajo finaliza, el trabajo es dinámicamente con carga equilibrada. El valor predeterminado funciona bien en la mayoría de los casos (gran número de iteraciones ), y cuando el trabajo subyacente por iteración no está bien comprendido (digamos que llama a una biblioteca), pero en algunos casos viene con gastos indirectos inaceptables.

La solución es exactamente lo que ha identificado en su implementación alternativa . Para ese efecto, tendremos un paralelo para el particionador llamado "simple" en la próxima versión de Visual Studio, que será similar a la implementación alternativa que describa y tendrá un rendimiento mucho mejor.

PS: El C# y C++ en paralelo para cada implementaciones utilizan un poco algoritmos diferentes en la forma en que van a través de las iteraciones - de ahí que verá ligeramente diferentes características de rendimiento en función de la carga de trabajo .

Saludos

Answer 3

Hay algunos problemas con su código, vamos a abordar uno por uno:

El uso de la recursividad para el cálculo de Fibonacci hace que el proceso de usar una cantidad excesiva de memoria, ya que es el uso la pila de llamadas para calcular el resultado. Tener Fibonacci recursivo significa que no está comparando los marcos paralelos C#/C++, está comparando los mecanismos de la pila de llamadas. Se puede calcular Fibonacci mucho más rápido:

int fibonacci(int n) 
{ 
    int curr = 1, prev = 0, total = 0; 
    for (int i = 0; i < n; i++) 
    { 
     int pc = curr; 
     curr += prev; 
     total += curr; 
     prev = pc; 
    } 
    return total; 
} 

Con esa función, tuve que correr al menos 1 millón de veces para obtener valores medibles.

Uso GetTickCount64 en lugar de GetTickCount:

template <class Function> 
__int64 time_call(Function&& f) 
{ 
    __int64 begin = ::GetTickCount64(); 
    f(); 
    return GetTickCount64() - begin; 
} 

Correr parallel_for con tan pequeño cuerpo puede ser realmente perjudicial para el rendimiento. Es mejor usar un functor más granular.

Con estos rasgos en mente, aquí es el código en C++:

// ParallelFibo.cpp : Defines the entry point for the console application. 
// 

#include "stdafx.h" 
#include <windows.h> 
#include <ppl.h> 
#include <concurrent_vector.h> 
#include <array> 
#include <tuple> 
#include <algorithm> 
#include <iostream> 
#include <random> 

using namespace Concurrency; 
using namespace std; 

template <class Function> 
__int64 time_call(Function&& f) 
{ 
    __int64 begin = ::GetTickCount64(); 
    f(); 
    return GetTickCount64() - begin; 
} 

// Computes the nth Fibonacci number. 
inline int fibonacci(int n) 
{ 
    int curr = 1, prev = 0, total = 0; 
    for (int i = 0; i < n; i++) 
    { 
     int pc = curr; 
     curr += prev; 
     total += curr; 
     prev = pc; 
    } 
    return total; 
} 

#define NUMBER_OF_REPETITIONS 1000000 
#define MIN_FIBO    37 
#define MAX_FIBO    49 

int main() 
{ 
    __int64 elapsed; 
    vector<int> v; 
    for (int i = MIN_FIBO; i < MAX_FIBO; i++) 
    { 
     v.emplace_back(i); 
    } 

    concurrent_vector<tuple<int, int>> results; 
    elapsed = time_call([&] { 
     parallel_for(MIN_FIBO, MAX_FIBO, [&](int n) { 
      for (int i = 0; i < NUMBER_OF_REPETITIONS; i++) 
      { 
       results.push_back(make_tuple(n, fibonacci(n))); 
      } 
     }); 
    }); 
    wcout << L"PPL time: " << elapsed << L" ms" << endl << endl; 
    cin.ignore(); 
    return 0; 
} 

Y aquí está el código en C#:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 
using System.Collections.Concurrent; 
using System.Diagnostics; 

namespace ParallelFiboCS 
{ 
    class Program 
    { 
     const int NUMBER_OF_REPETITIONS = 1000000; 
     const int MIN_FIBO = 37; 
     const int MAX_FIBO = 49; 
     static void Main(string[] args) 
     { 
      var ll = new ConcurrentQueue<Tuple<int, int>>(); 

      var a = new int[MAX_FIBO - MIN_FIBO]; 
      for (int i = MIN_FIBO; i < MAX_FIBO; i++) 
      { 
       a[i - MIN_FIBO] = i; 
      } 

      long elapsed = time_call(() => 
      { 
       Parallel.ForEach(a, (n) => 
       { 
        for (int i = 0; i < NUMBER_OF_REPETITIONS; i++) 
        { 
         ll.Enqueue(new Tuple<int, int>(n, fibonacci(n))); 
        } 
       }); 
      }); 

      Console.WriteLine("TPL C# elapsed time: " + elapsed + "\n\r"); 

      Console.ReadLine(); 
     } 

     static long time_call(Action f) 
     { 
      var p = Stopwatch.StartNew(); 
      p.Start(); 
      f(); 
      p.Stop(); 
      return p.ElapsedMilliseconds; 
     } 

     static int fibonacci(int n) 
     { 
      int curr = 1, prev = 0, total = 0; 
      for (int i = 0; i < n; i++) 
      { 
       int pc = curr; 
       curr += prev; 
       total += curr; 
       prev = pc; 
      } 
      return total; 
     } 
    } 
} 

El tiempo promedio para ejecutar 12 millones de cálculos de Fibonacci de números entre 37 y 49:

C++: 513ms

C#: 2527ms