Вложенные циклы Parallel.ForEach в том же списке?

Мне нужно распараллелить метод, который выполняет исчерпывающее попарное сравнение элементов в списке. Последовательная реализация проста:

foreach (var element1 in list)
    foreach (var element2 in list)
        foo(element1, element2);

В этом случае foo не изменит состояние element1 или element2. Я знаю, что просто делать вложенные операторы Parallel.ForEach небезопасно:

Parallel.ForEach(list, delegate(A element1)
{
    Parallel.ForEach(list, delegate(A element2)
    {
        foo(element1, element2);
    });
});

Каким был бы идеальный способ реализовать это с помощью библиотеки параллельных задач?


c# parallel-processing task-parallel-library
person Wesley Tansey    schedule 19.07.2010    source источник

Ответы (3)


arrow_upward
12
arrow_downward

Не могли бы вы просто иметь один параллельный и один обычный цикл? Так что либо

Parallel.ForEach(list, delegate(A element1)
{
  foreach(A element2 in list)
    foo(element1, element2)
});

or

foreach(A element1 in list)
{
  Parallel.ForEach(list, delegate(A element2)
  {
    foo(element1, element2);
  });
}

Тоже должно ускориться. В любом случае никогда не будет потока на цикл, поэтому, вероятно, это будет так же быстро или немного медленнее, чем вложенные параллельные циклы.

person Jouke van der Maas    schedule 19.07.2010

arrow_upward
16
arrow_downward

По крайней мере, если вы выполняете код на машине, где количество ядер как минимум в два раза превышает количество элементов в списке, я не уверен, что встроенные Parallel.ForEach — это хорошая идея.

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

http://www.freeimagehosting.net/uploads/ca97f403f8.png

На каждой итерации Parallel.ForEach будет терять несколько миллисекунд, чтобы определить, какой поток должен выполнить следующую итерацию. Допустим, у вас есть набор из 7 предметов. Если вы распараллелите родительский цикл, эти миллисекунды будут потеряны 7 раз. Если вы распараллелите обе петли, вместо этого они будут потеряны 7 × 7 = 49 раз. Чем больше набор, тем больше перегрев.

person Arseni Mourzenko    schedule 19.07.2010
comment
Не думайте, что PFX создаст столько потоков, сколько существует параллельных задач — это разумнее. - person Jon Skeet; 19.07.2010
comment
Конечно, нет. По умолчанию он создает столько потоков, сколько ядер. Но проблема в том, что после каждой итерации он будет тратить время на поиск того, какой поток должен выполнить следующую итерацию. - person Arseni Mourzenko; 19.07.2010
comment
Я не думаю, что он говорит, что будет так много потоков, просто постановка задачи в очередь для каждого вызова функции будет иметь гораздо больше накладных расходов, чем просто вызов механизма PFX для каждого внешнего цикла. - person Gabe; 19.07.2010
comment
Спасибо МайнМа. Вероятно, стоит отметить, что foo, вероятно, займет много времени по сравнению со стоимостью вызова Parallel.ForEach. Я ценю общий аргумент в пользу распараллеливания только одного цикла. - person Wesley Tansey; 19.07.2010

arrow_upward
1
arrow_downward

Два вложенных цикла, по сути, означают, что вы хотите foo произвести декартово произведение списка с самим собой. Вы можете распараллелить всю операцию, сначала создав все пары во временном списке, а затем перебирая этот список с помощью Parallel.ForEach.

EDIT: вместо создания списка всех комбинаций вы можете использовать итератор для возврата двухэлементного кортежа с комбинацией. Parallel.ForEach по-прежнему будет распараллеливать обработку кортежей.

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

 const int SIZE = 10;
    static void Main(string[] args)
    {
        List<int> list = new List<int>(SIZE);
        for(int i=0;i<SIZE;i++)
        {
            list.Add(i);
        }


        Parallel.ForEach(GetCombinations(list),(t,state,l)=>
            Console.WriteLine("{0},{1},{2}",l,t.Item1,t.Item2));

    }

    static IEnumerable<Tuple<int,int>> GetCombinations(List<int> list)
    {
        for(int i=0;i<list.Count;i++)
            for(int j=0;j<list.Count;j++)
                yield return Tuple.Create(list[i],list[j]);
    }
person Panagiotis Kanavos    schedule 19.07.2010
comment
Вы, вероятно, не знаете о Enumerable.Range(). Это действительно удобно! Однако в коде вы выполняете 3 цикла (вместо 2), из которых 2 не параллельны вообще. Это зависит от того, что делает Foo() (Console.WriteLine в вашем ответе), но это, вероятно, будет медленнее, чем отсутствие параллелизма и просто двойной цикл в обычном режиме. - person Jouke van der Maas; 06.07.2011