C # TPL быстрее, чем C ++ PPL?

Question

Я написал очень простое приложение, которое использовало функцию Фибоначчи для сравнения значений TPL Parallel.ForEach против PPL parallel_for_each, и результат был действительно странным: на ПК с 8 ядрами c # на 11 секунд быстрее затем c ++.

Одинаковый результат как для предварительного просмотра vs2010, так и для предварительного просмотра 2011 года.

Код 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 ++код:

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

Можете ли вы указать мне, где часть моего кода на C ++ я ошибаюсь?

Ширина group_task У меня такое же время, как и в коде 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

Вот объяснения Rahul v Patil из команды Microsoft

Здравствуйте,

Спасибо, что подняли этот вопрос.Действительно, вы определили издержки, связанные с параллелью по умолчанию для * - особенно, когда число итераций мало, а размер работы - переменный.Параллель для по умолчанию начинается с разделения работы на 8 частей (по 8 ядер).По окончании работы работа динамически сбалансирована.По умолчанию прекрасно работает в большинстве случаев (большое количество итераций), и когда основная работа для каждой итерации не совсем понятна (скажем, вы вызываете библиотеку) - но в некоторых случаях она имеет неприемлемые накладные расходы.

Решение - это именно то, что вы определили в своей альтернативной реализации.Для этого в следующей версии Visual Studio будет параллель для разделителя, называемого «простым», который будет аналогичен альтернативной реализации, которую вы описываете, и будет иметь гораздо лучшую производительность.

PS: C #и параллельно C ++ для каждой реализации используют немного разные алгоритмы в том, как они проходят итерации - следовательно, вы увидите немного отличающиеся характеристики производительности в зависимости от рабочей нагрузки.

С уважением

Answer 2

Есть некоторые проблемы с вашим кодом, давайте рассмотрим их по очереди:

Использование рекурсии для вычисления Фибоначчи заставляет процесс использовать чрезмерный объем памяти, поскольку он использует стек вызовов для вычисления результата. Наличие рекурсивного Фибоначчи означает, что вы сравниваете не параллельные платформы C # / C ++, а средства стека вызовов. Вы можете вычислить Фибоначчи гораздо быстрее:

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

С этой функцией мне приходилось запускать не менее 1 миллиона раз, чтобы получить измеряемые значения.

Используйте GetTickCount64 вместо GetTickCount:

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

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

Имея в виду эти особенности, вот код на 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;
}

А вот код на 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;
        }
    }
}

Среднее время выполнения 12 миллионов вычислений Фибоначчи для чисел от 37 до 49:

C ++: 513 мс

C #: 2527мс

Answer 3

GetTickCount (http://msdn.microsoft.com/en-us/library/windows/desktop/ms724408%28v=vs.85%29.aspx) функция, используемая для измерения времени, переданного на нативной стороне, совсем не точна. В описании говорится так:

"Разрешение функции GetTickCount ограничено разрешением системного таймера, которое обычно находится в диапазоне от 10 миллисекунд до 16 миллисекунд."

Исходя из моего опыта, использование GetSystemTime дает лучшие результаты в Windows Vista и более поздних версиях (в Win XP, если я правильно помню, разрешение экрана примерно такое же, как и в счетчике тиков). Или лучше вы можете использовать для мелкозернистых измерений некоторые другие API, которые предлагают разрешение до мил. Возможно, в вашем случае создание больших наборов данных было бы более полезным, чтобы иметь некоторые значимые данные.