Распараллеливание циклов и нюансы связанные с ними

С Task Parallel Library (TPL) использовать параллельные циклы в своем коде кажется простым делом. Благодаря лямда синтаксису и методам расширения все как никогда просто. Очень просто изменить обычный цикл на параллельный – ведь синтаксис очень похож. Но также просто использовать параллельный цикл там где он не нужен. Все потому что иногда может быть сложно распознать, что итерации цикла действительно независимы друг от друга.

Это главное правильно параллельных циклов – итерации цикла должны быть независимыми друг от друга. Иногда, использование parallel loops (параллельных циклов) с зависимыми друг от друга итерациями цикла, приводит к совершенно неожиданному выполнению кода. В других случаях, параллельный цикл с зависимыми итерациями может привести к трудно находимым багам, которые можно выловить в одном из миллиона запусков, или же программа вообще перестанет отвечать. Поэтому использование независимых итераций является ключевым требованием к распараллеливанию циклом которое из-за простоты перехода можно легко упустить.

В случае использования parallel loop pattern из TPL, распараллеливание и создание необходимого количества потоков для этого (degree of paralellism) лежит полностью на TPL, и в зависимости от количества ядер процессора TPL создаст столько потоков сколько для этого необходимо. Поэтому если код выполняется на процессоре с одним ядром производительность параллельных циклов очень близка к последовательному выполнению.

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

К примеру цикл for

int n = … 
for (int i = 0; i < n; i++) 
{ 
// … 
});

Превращается в почти такой же по внешнему виду с помощью лямда синтаксиса и методов расширения

int n = … 
Parallel.For(0, n, i => 
{ 
// … 
});

Цикл foreach

IEnumerable items = … 
foreach (var item in items) 
{ 
// … 
});

Также очень похож на соответствующий вариант:

IEnumerable items = … 
Parallel.ForEach(items, item => 
{ 
// … 
});

Или в стиле PLINQ

IEnumerable items = …

// LINQ 
var query1 = from i in items select DoAction(i);

// PLINQ 
var query2 = from i in items.AsParallel() select DoAction(i);

Параллельные циклы в отличие от обычных поддерживают специальный механизм остановки. Фактически есть возможность сделать Break, а также Stop такому циклу. Две операции для остановки цикла немного сбивают с толку. Сложность в остановке параллельных циклов в том, что в один и тот же момент может выполнятся несколько разных итераций, которые необходимо остановить.

Вызов метода Break или Stop не останавливает параллельное выполнение тех итераций которые уже начали выполнятся. Но если вызван Break, все итерации с индексом меньше той которая его вызвала – выполнятся, даже после вызова Break и даже если они не были запущены до вызова Break. Если же останавливать параллельный цикл используя Stop то все итерации которые уже начали выполнятся – продолжать выполнятся до завершения, а новые даже с меньшим индексом выполнение не начнут.

Есть еще один способ остановить выполнение распараллеленных в разных потоках циклов – используя CancellationToken. Стандартный механизм отмены при работе с Task Parallel Library. Удобно использовать если в коде используется такой же механизм отмены не только для параллельных циклов но и для Task или потоков.

Механизм обработки исключений так же общий как и для TPL – с использованием AggregateException. Необработанное исключение приводит к тому что новые итерации не начнут выполнение, а вот уже начавшиеся продолжат, проверить случились ли параллельно исключения можно используя свойство IsExceptional класса ParallelLoopState.

Вот и вся хитрость параллельных циклов. Хотя еще остался механизм – Partitioner для использования с циклами итерации которого “маленькие”, т.е. выполняются быстро. Но в таких случаях есть ли смысл вообще распараллеливать цикл, разве что число итераций достаточно велико. Есть еще такой метод расширения как ForAll, например .AsParallel().ForAll(p => DoAction(p)), который можно использовать чтобы выполнить какое-то действие для всех объектов параллельно без возврата результат. Также можно задавать degree of parallelism для параллельных циклов. Вот пожалуй и все.

Но интересно другое. Какие подводные камни у такого очень просто подхода к параллелизму данных (data parallelism) который предоставляет нам TPL.

Итак, что ждать от параллельных циклов.

Первое, что отличает обычный цикл от параллельного – это exception handling. Для параллельных циклов исключения которые возникли в процессе будут складывается в AggregatedException и исключение будет выброшено контексте вызывающего потока.

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

Выше также говорилось, что не следует полагаться на последовательность выполнения при распараллеливании.

Не следует злоупотреблять degree of parallelism. Не нужно без явных на то причин менять degree of parallelism для параллельных циклов так как это может привести к ситуациям processor oversubcription/undersubscription – когда создано намного больше/меньше интенсивных рабочих потоков чем ядер.

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

• Запись в общую для итераций переменную. Если каждая из итераций производит какие-то действия над одной и той же переменной, то результат этих действий может быть неожиданным, потому что мы не можем полагаться в таком случае на последовательное выполнение и запись в переменную. Общими могут быть переменные которые объявлены вне цикла. Чтение и запись в файле будут иметь тот же эффект. Пример:

for (int i = 1; i < n; i++) 
total += data[i];

• Изменение общего состояния объекта. Это тоже что и если писать в общую для итераций цикла переменную. Состояния или свойства объекта могут меняться разными итерациями в разной последовательности и мы не сможем спрогнозировать что получим на выходе. Например:

for (int i = 1; i < n; i++) 
MyObject[i].StatePropertyOrParent.Update();

Также к последнему пункту можно отнести обработку дублирующихся объектов. Например, если на вход итераций Parallel.ForEach поступит дважды один и тот же объект, возможна такая ситуация когда два потока одновременно попытаются изменить этот объект.

• Использование в теле цикла не thread-safe типов, например попытка шарить между итерациями такие экземпляры не thread-safe классов как Random или DbConnection может привести к проблемам
• Привязка к разным значения счетчика цикла. Если в теле цикла производятся какие-то арифметические операции со счетчиком цикла. Это называется loop-carried dependence. Например:

for (int i = 1; i < n; i++) 
data[i] = data[i] + data[i –1];