Готовый перевод PATTERNS OF PARALLEL PROGRAMMING / ПАТТЕРНЫ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ: Восхитительные параллельные циклы

Возможно наиболее известным шаблоном параллелизма является тот, под который подходят "ошеломляюще параллельные" алгоритмы. Программы, удовлетворяющие этому шаблону, способны распараллеливаться, потому что многие отдельные операции могут работать относительно независимо, с малым количеством зависимостей между операциями (или вообще без них), так что они могут быть эффективно вынесены в параллельные вычисления. Досадно, что к таким программам применяется термин "ошеломляющий", поскольку ничего ошеломляющего в них нет вообще. Фактически, чем больше алгоритмов и задач попадают в область "ошеломляющего параллелизма", тем больше следует улучшать положение дел в индустрии ПО. Поэтому, многие авторы начали использовать альтернативные названия этого шаблона "удобный параллелизм", "приятный параллелизм" и "восхитительный параллелизм", для того чтобы проиллюстрировать настоящую природу этих задач. Если Вы обнаружите, что пытаетесь распараллелить задачу, подходящую под этот паттерн, считайте себя счасливчиком и рассчитывайте, что Ваша работа будет гораздо проще, чем могла бы быть, возможно даже "восхитительной".

Значительная часть работы во многих приложения и алгоритмах делается с помощью управляющих циклов. Циклы, как никак, позволяют приложению исполнять набор инструкций снова и снова, применяя логику к отдельным сущностям, будь то неделимые значения (как в случае с циклом for), или наборы данных (как в случае с циклом foreach). Многие языки содержат встроенные конструкции управления для таких видов циклов (Microsoft Visual C#® и Microsoft Visual Basic® в том числе: первый с инструкциями for и foreach, второй - с For и For Each). Касательно проблемы параллелизма: сущности, обрабатываемые отдельными итерациями цикла могут выполняться одновременно, поэтому нам нужен механизм для выполнения подобного распараллеливания.

РЕАЛИЗАЦИЯ КОНСТРУКЦИИ ПАРАЛЛЕЛЬНОГО ЦИКЛА

Поскольку восхитительные параллельные циклы являются превалирующим шаблоном, важно понимать все детали их работы, а также все договоренности, связанные с паттерном. Для понимания этих основ в дальнейшем, мы напишем простой распараллеленый цикл с помощью .NET Framework 3.5, до включения полноценной поддержки параллельности в .NET Framework 4.

Во первых, нам нужна сигнатура. Для распараллеливания цикла for, мы реализуем метод, принимающий три параметра: нижняя граница, верхняя граница и делегат для тела цикла, в который поступает целочисленный параметр, представляющий индекс итерации (делегат будет вызываться для каждой итерации). Обратите внимание, что у нас есть несколько вариантов поведения этих параметров. В C# и Visual Basic большая часть циклов for пишется примерно следующим образом:

При беглом чтении Вы можете подумать, что эти циклы идентичны, но это не так: цикл на Visual Basic выполнит на одну итерацию больше своего аналога на C#. Вот почему Visual Basic включает верхнюю границу, в то время как в C# явно исключается верхняя граница с помощью оператора "меньше". Для наших целей последуем примеру реализации на C#, то есть параметр верхней границы для нашего метода параллельного цикла представляет исключающую верхнюю границу.

Наша реализация этого метода вызовет тело цикла по разу для каждого элемента в диапазоне [нижняя граница, верхняя граница), и выполнит это максимально параллельно. Для этого следует понять, до каких пор вообще можно распараллеливать.

Здравый смысл в среде параллелизма часто предполагает, что хорошая реализация использует один поток на ядро. Ведь с таким подходом мы полностью задействуем все ядра. Если окажется больше потоков - операционная система вынуждена будет переключать контекст между ними, что выльется в лишние затраты; если меньше - мы не сможем использовать преимущества всех предлагаемых машин, поскольку по меньшей мере одно ядро останется неиспользованным. Это логика не лишена смысла, по крайней мере для определенного класса задач. Но она также основана на идеализированной и теоретической идее компьютера. Вот пример, о который разбивается это утверждение: для выполнения полезных действий потокам, вовлеченным в параллельные вычисления, требуется доступ к данным, что в свою очередь приводит к обращению к кэшу или основной памяти или диску или сети или другим хранилищам, что в терминах времени доступа, может быть затратным; пока выполняются подобные действия CPU может простаивать. Раз так, пока хорошая реализация параллелизма по умолчанию подразумевает один-поток-на-ядро, готовность к иному распределению может оказаться полезной. Однако для начала мы будем придерживаться договоренности "один-поток-на-ядро".

В .NET Framework получение числа логических процессоров выполняется с помощью класса System.Environment и свойства ProcessorCount в частности. Внутри .NET получает соответствующее значение при помощи функции операционной системы GetSystemInfo из библиотеки kernel32.dll.

Это значение необязательно соответствует числу физических процессоров и даже числу физических ядер на машине. Скорее, оно учитывает количество доступных аппаратных потоков. Например, на компьютере с двумя сокетами, каждый из которых имеет по четыре ядра, каждое из которых в свою очередь имеет по два аппаратных потока (иногда упоминаемые как hyperthreads) Environment.ProcessorCount вернет 16.

Начиная с Windows 7 и Windows Server 2008 R2, операционная система Windows поддерживает более 64 логических процессоров, и по умолчанию (по большей части для устаревших приложений), программный доступ к этим ядрам организован через новую концепцию, известную как "группы процессоров". .NET Framework не предоставляетуправляемый доступ к API групп процессоров, поэтому Environment.ProcessorCount ограничено значением 64 (максимальный размер группы процессоров), даже если на машине имеется больше процессоров. Вдобавок, в 32х-битном процессе ProcessorCount ограничен значением 32 для совместимости с 32х-битной маской, представляющую общность процессоров (требование, согласно которому, поток направляется на исполнение только в определенное подмножество процессоров).

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

Наша начальная реализация

Отметим несколько интересных соображений по поводу этой реализации. Первое: для каждой порции используется новый поток. Этот поток используется чисто для обработки указанной части и впоследствии уничтожается. У такого подхода есть как положительные, так и отрицательные стороны. Очевидным плюсом является то, что ресурсы потока отданы только нашему циклу, и позволяют операционной системе беспристрастно планировать работу потоков. Однако, этот плюс зачастую перевешивается несколькими значительными недостатками. Одним из которых является стоимость потока. По умолчанию, в .NET Framework 4 потоку выделяется мегабайт для стека, вне зависимости от того, используется ли все это пространство для выполняемых задач или нет. Вдобавок, запуск нового потока и его остановка являются относительно затратными, особенно в сравнении с затратами маленького цикла с условно небольшим количеством итераций и примитивной работой внутри каждой из них. При каждом вызове реализации нашего цикла запускаются и уничтожаются новые потоки.

Есть и другое, более вредное воздействие: чрезмерная подписка. Поскольку мы движемся в многоядерный мир, умеющие работать параллельно компоненты становятся все более и более распространенными, и было бы замечательно, если бы такие компоненты могли работать совместно. Если компоненты используют циклы наподобие приведенных выше, а следовательно запускают по потоку на ядро, мы получим два компонента, соперничающие за аппаратные ресурсы, заставляя операционную систему тратить больше времени на переключение контекстов между компонентами. Переключение контекстов затратное по многим причинам, включая необходимость сохранения деталей выполняемого потока до того, как операционная система выключит поток и заменит его другим. Возможно, важнее то, что такое переключение контекстов может оказать крайне отрицательное влияние на подсистему кеширования процессора. Когда потоку требуются данные, их нужно откуда-то доставить, зачастую из основной памяти. В современных архитектурах стоимость доступа к данным в основной памяти относительно выше, чем исполнение нескольких инструкций над ними. Для уравнивания разработчики процессоров ввели слои кэша, предназначенные для хранения на аппаратном уровне небольшого количества часто используемых данных, доступ к котором значительно эффективнее, чем к основной памяти. Во время выполнения потока, кеш для ядра, на котором он исполняется, стремится заполниться подходящими данными, улучшая его производительность. Когда выключается контекст потока, кеш меняет данные, необходимые новому потоку. Заполнение кэша требует затратных обращений к основной памяти. Поэтому, чем больше переключений контекста между потоками, тем больше будет обращений к памяти, поскольку кеш мечется между нуждами потоков, которые с ним работают. Учитывая эти затраты, чрезмерная подписка может быть причиной серьезных проблем производительности. К счастью, снимки из нового параллельного профилировщика в Visual Studio 2010 могут помочь в обнаружении этих проблем, как показано ниже:

На этом снимке каждая горизонтальная линия представляет поток, а ось абсцисс представляет время. Зеленым обозначено время исполнения, красным - время блокировки, а желтым время, когда поток мог исполняться, но был вытеснен другим потоком. Чем больше желтого - тем больше чрезмерной подписки, влияющей на производительность.

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

Начиная с .NET Framework 1.0 класс System.Threading.ThreadPool предоставлял подобную функциональность, и хотя его реализация менялась с каждой версией (причем для .NET Framework 4 весьма ощутимо), основной принцип остался тем же: .NET Framework предоставляет пул потоков для обслуживания предоставленных ему рабочих элементов. Статический метод QueueUserWorkItem - основной способ добиться этого. Обновим реализацию параллельного цикла for с учетом этой возможности:

В ней удалена неэффективная работа нашего приложения, связанная с чрезмерным созданием и удалением потоков, а также уменьшена возможности чрезмерной подписки. Однако, неэффективность была не единственной проблемой нашей реализации. Еще одной может оказаться статическое партиционирование, взятое нами на вооружение. Для задач, требующих приблизительного одинаковой работы на каждой итерации, и запущенных на относительно "спокойном" компьютере (имеется ввиду компьютер, на котором выполняется мало работы помимо целевой задачи), статическое партиционирование является успешным и эффективным способом разбиения нашего набора данных. Однако, если нагрузка на каждой итерации различается, будь то вследствие природы решаемой задачи, либо в вследствие того, что некоторые партиции выполняются дольше из-за вытеснения более важными задачами системы, мы можем столкнуться с дисбалансом нагрузки. Симптом дисбаланса нагрузки весьма заметен на следующих снимках из параллельного профилировщика Visual Studio 2010.

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

В качестве примера рассмотрим параллельный цикл от 1 до 12 (включительно), где каждая итерация выполняется N секунд, где N - порядковый номер итерации (первая итерация потребует 1 секунду вычислений, вторая - 2 секунды и так далее). В целом, этому циклу потребуется (12*13)/2 = 78 секунд последовательного времени обработки. При идеальной реализации цикла на двухядерной системе, мы можем выполнить его за 39 секунд. Добиться этого можно, если одно ядро займется 6й,10й,11й и12й итерациями, а другое ядро - всеми остальными.

Однако, при статическом партиционировании, которое мы используем, одному ядру выделится диапазон [1;6], а другому - [7;12].

А раз так, первое ядро получит полезной работы на 21 секунду, в то время как второму ядру достанется 57 секунд. Поскольку цикл не завершается, пока не обработаются все итерации - время работы нашего цикла определяется максимальным временем работы любой из партиций, а поэтому цикл закончится через 57 секунд вместо ранее упомянутых теоретических 39. Это снижает возможную производительность приблизительно на 50%, и это только вследствие неэффективного разбиения. Теперь Вы понимаете, почему партиционирование занимает такое важное место в параллельном программировании.

Возможны различные варианты статического разбиения. Например, вместо распределения диапазонов, мы могли бы использовать некое подобие карусели, где каждому потоку присвоен уникальный идентификатор в диапазоне [0; количество потоков), и где каждый поток обрабатывает индексы цикла, для которых остаток от деления на количество потоков совпадает с идентификатором потока. То есть, при входном диапазоне [0;12) и 4х потоках, поток №0 обработает итерации под индексами 0, 3, 6, 9, поток №1 под индексами 1, 4, 7, 10 и так далее. Если мы применим такого рода разбиение к предыдущему примеру, то вместо 21 секунды для первого потока и 57 - для второго, потребуется 36 и 42 секунды соответственно, что означает гораздо меньший разброс относительно оптимального времени работы (39 секунд).

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

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

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

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

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

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

Неважно, на какие компромиссы между балансировкой и затратами Вы идете, это все равно компромиссы. Для конкретных задач Вы можете написать произвольную реализацию параллельного цикла, удовлетворяющего паттерну, который справляется с задачей наилучшим образом. Однако, это потребует дополнительного кодирования. В целом, хорошим решением считается то, которое показывает хорошие результаты для большинства проблем, минимизируя потери за счет достаточной балансировки. .NET Framework содержит такую реализацию в новом классе System.Threading.Tasks.Parallel.

PARALLEL.FOR

Замечательно-параллельные задачи представляют один из наиболее распространенных шаблонов параллельного программирования, и нормально, что при включении в основную библиотеку поддержки параллельного программирования, включают ее и для замечательно-параллельных циклов. В .NET Framework 4 этим занимается класс Parallel из пространства имен System.Threading.Tasks в mscorlib.dll. Класс Parallel имеет только три метода, хотя у каждого есть по несколько сигнатур, одна из которых полностью совпадает с сигнатурой реализованного выше метода MyParallelFor:

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

Внутри, метод For организован на манер наших реализации. По умолчанию, он использует класс ThreadPool для выполнения работы с максимально возможным параллелизмом, и вызывает предоставленный делегат однажды за итерацию. Однако, Parallel.For и его перегрузки предоставляют гораздо больше этого:

Обработка исключений. Если одна итерация в цикле бросит исключение, будет выполнена попытка скорейшей остановки всех потоков, участвующих в цикле (по умолчанию, исполняемые в тот момент итерации прерваны не будут, но управляющий циклом механизм предотвратит запуск новых итераций). Когда обработка полностью остановлена, все необработанные исключения объединяются и генерируется экземпляр AggregateException. Это исключение предоставляет поддержку нескольких внутренних исключений, в то время как большинство исключений в .NET Framework поддерживают только одно вложенное исключение. Дополнительная информация об AggregateException находится по адресу http://msdn.microsoft.com/magazine/ee321571.aspx.

Предварительный выход из цикла. Работает аналогично ключевому слову break в C# и Exit For в Visual Basic. Также есть возможность понять должна ли текущая итерация отказаться от результатов своей работы, если в других итерациях происходит предварительный выход из цикла. Это главная причина наличия возвращаемого значения ParallelLoopResult в сигнатуре Parallel.For, которое помогает вызывающему коду понять, закончился ли цикл преждевременно и, если да, то почему.

Широкие диапазоны. Наряду с перегрузками для работы с 32-х битными диапазонами, предоставляются перегрузки, обслуживающие 64-х битные диапазоны.

Локальное состояние потока. Некоторые перегрузки предоставляют поддержку локального состояния потока. Подробно эта тема будет обсуждаться позже в разделе паттернов аггрегации.

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

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

Плавающее число потоков. Parallel.For разработан приспосабливаемым к задачам, чья сложность меняется со временем, таким образом, что некоторым порции требуют больше вычислений, чем другие. Раз так, для обработки цикла было бы лучше, чтобы количество потоков, вовлеченных в расчет, менялось со временем, а не задавалось статически, как было во всех наших реализациях.

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

Parallel.For применим к широкому кругу идеально параллельных задач, предоставляя реализацию этого важнейшего шаблона. В качестве демонстрации такого приложения, примеры параллельного программирования для .NET Framework 4 (доступны по адресу http://code.msdn.microsoft.com/ParExtSamples) содержат трассировщик лучей. Ниже приведен снимок экрана:

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

Заметьте, что практически нет разницы между последовательным и параллельным кодом, кроме замены ключевого слова for для C#(For для Visual Basic) на вызов метода Parallel.For

PARALLEL.FOREACH

Цикл for является узко специализированным. Его цель - перебирать набор данных определенного типа, набор данных из чисел, представляющих диапазон. Более обобщенной концепцией является обход любого набора данных, что в C# поддерживается с помощью ключевого слова foreach, в Visual Basic - For Each.

Рассмотрим следующий цикл:

Задействовав класс Enumerable из LINQ, мы можем создать IEnumerable, представляющий тот же диапазон, и обходить этот набор данных с помощью foreach:

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

Реализация параллельного foreach в принципе похожа на реализацию параллельного for. Нужно несколько потоков для параллельной обработки данных, нужно разбивать данные и направлять партиции в обрабатывающие потоки. В нашей, делящей динамически, реализации MyParallelFor, оставшийся к обработке набор данных был представлен целым числом, обозначавшим следующую итерацию. В реализации foreach мы можем хранить IEnumerator набора данных. Он должен быть защищен критической секцией так, чтобы в любое время его мог менять только один поток. Ниже приведен пример реализации:

Как и в ранних реализациях MyParallelFor, здесь полно очевидных побочных эффектов, и все они упираются в компромисс между простотой, чрезмерными затратами и балансировкой нагрузки. Вхождение в lock - дорогое, а в этой реализации вход/выход из lock происходит на каждом элементе последовательности, но такая дороговизна делает возможной максимальную балансировку нагрузки, поскольку каждый поток захватывает по одному элементу за раз, позволяя другим потокам помогать, если ему неожиданно достался долгий элемент. Мы можем частично компенсировать дороговизну за счет балансировки нагрузки, извлекая не один, а несколько элементов внутри блокировки. Захватывая блокировку, получая несколько элементов и отпуская блокировку, мы смягчаем цену блокировки для нескольких элементов, что лучше чем затраты на блокировку каждого элемента. Это преимущество достигается за счет меньшей балансировки нагрузки, поскольку если поток забрал несколько единиц, он отвечает за их обработку, даже если некоторые их них окажутся сложнее остальных всех вместе взятых.

Впрочем, мы можем уменьшить затраты и другим способом. Например, в показанной выше реализации всегда используются методы перечислителя MoveNext/Current. Но может оказаться, что входной источник типа IEnumerable также реализует интерфейс IList, что позволяет использовать менее затратное разбиение, которое мы задействовали ранее в MyParallelFor:

Как и в случае с Parallel.For, класс Parallel из .NET Framework 4 предоставляет поддержку этого шаблона в виде метода ForEach. Перегрузки метода ForEach поддерживают многие вещи из перегрузок для For, включая предварительный выход из цикла, утонченное разбиение и динамическое число потоков. Сигнатура простейшей перегрузки почти совпадает с нашей:

В качестве примера рассмотрим объект Student, имеющий открытое на запись свойство GradePointAverage, а также коллекцию объектов Test, каждый из которых имеет оценку и значимость. У нас есть набор объектов Student, и мы хотим их обойти, рассчитав для каждого студента его среднюю оценку на основании связанных с ним экзаменов. Последовательный код выглядит так:

Для распареллеливания задействуем Parallel.ForEach:

ОБРАБОТКА НЕЦЕЛОЧИСЛЕННЫХ ДИАПАЗОНОВ

Класс Parallel в .NET Framework 4 содержит перегрузки для работы с индексами диапазонов типа Int32 и Int64 . Однако в языках типа C# и Visual Basic циклы for могут использоваться для обхода диапазонов, определяемых не целочисленными значениями.

Рассмотрим тип Node, представляющий связанный список:

Зная головной элемент такого Node, мы можем использовать цикл for для обхода списка:

Parallel.For не содержит перегрузок для работы с Node, а Node не реализует IEnumerable, что блокирует возможность использования Parallel.ForEach. Взамен мы можем задействовать итераторы C# для создания метода Iterate, который будет выдавать IEnumerable для обхода Node:

Имея такой метод, мы можем скомбинировать Parallel.ForEach и Iterate, чтобы приблизиться к реализации Parallel.For, работающего с Node:

Похожие подходы могут применяться в разнообразных сценариях. Однако, не забывайте, что интерфейс IEnumerator не потокобезопасный, а следовательно во время доступа к источнику данных внутри Parallel.ForEach нужно использовать блокировку. Хотя ForEach использует внутри некоторые трюки, пытаясь снизить цену таких блокировок, все равно остаются издержки, которые нужно перекрывать количеством работы внутри ForEach , чтобы достичь хорошей скорости.

Parallel.ForEach оптимизирован для работы с поддерживающими индексацию источниками данных, такими как списки и массивы, и в таких случаях необходимость блокировки отпадает (мы уже рассматривали похожий пример реализации, когда MyParallelForEach вызывал MyParallelFor при обработке IList). Итак, хотя на создание массива из перечисления необходимы время и память, производительность в некоторых случаях может оказаться выше от преобразования области итерации в массив или список, что можно сделать с помощью LINQ. Например:

Формат конструкции for в C# (For в Visual Basic) может быть также универсально описан в обобщенном методе Iterate:

Мы добавили себе затрат на вызов всех делегатов, зато теперь у нас есть универсальный механизм для обхода. Пример с Node можно переписать следующим образом:

ПРЕДВАРИТЕЛЬНЫЙ ВЫХОД ИЗ ЦИКЛОВ

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

ЗАПЛАНИРОВАННЫЙ ВЫХОД

Некоторые перегрузки Parallel.For и Parallel.ForEach передают экземпляр ParallelLoopState в тело делегата. Нас интересуют 4 члена из этого типа, относящиеся к теме: методы Stop и Break и свойства IsStopped и LowestBreakIteration.

Когда итерация вызывает Stop, механизм управления циклом пытается предотвратить от запуска дополнительные итерации. Как только заканчиваются все исполняемые итерации - метод цикла успешно завершается (то есть, без исключения). Возвращаемый методами Parallel.For и Parallel.ForEach тип ParallelLoopResult является типом значений: если Stop привел к предварительному выходу из цикла, свойство IsCompleted в возвращаемом результате будет равняться false.

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

Break очень похож на Stop, однако предоставляет дополнительные гарантии. Если Stop информирует управляющий циклом механизм, что не нужно больше запускать итерации, Break сообщает, что не нужно запускать итерации после текущей (например, если номер итерации выше или если поступают данные из источника данных после текущего элемента), но все итерации до текущей все-таки должны выполниться. Он не гарантирует, что итерации, следующие за текущей, уже не выполняются или не запускаются, однако попытается предотвратить запуск лишних итераций. Break может быть вызван из нескольких итераций, в таком случае имеет значение итерация с наименьшим номером, который можно получить из nullable-свойства ParallelLoopState.LowestBreakIteration. ParallelLoopResult имеет такое же свойство LowestBreakIteration.

Получается следующая матрица решений для анализа ParallelLoopResult:

IsCompleted == true

Все итерации были обработаны.

Если IsCompleted == true, LowestBreakIteration.HasValue будет false.

IsCompleted == false && LowestBreakIteration.HasValue == false

Для предварительного выхода из цикла использовался Stop.

IsCompleted == false && LowestBreakIteration.HasValue == true

Для предварительного выхода из цикла использовался Break, а в LowestBreakIteration.Value хранится наименьшая итерация, из которой вызывался Break.

Пример использования Break в цикле:

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

НЕЗАПЛАНИРОВАННЫЙ ВЫХОД

Ранее упомянутые механизмы предварительного выхода из цикла основаны на теле цикла, содержащем действие для выхода. Однако иногда мы хотим иметь возможность завершить цикл с помощью некоторой внешней сущности, также известной под именем "отмена".

Отмена в параллельных циклах поддерживается с помощью представленного в .NET Framework 4 типа System.Threading.CancellationToken. Перегрузки всех методов класса Parallel принимают экземпляр ParallelOptions, одним из свойств которого является CancellationToken. Просто задайте этому свойству значение CancellationToken, который должен использоваться для отслеживания отмены и передайте экземпляр настроек в вызов цикла. Цикл будет следить за маркером, и если обнаружит, что была запрошена отмена - прекратит запуск дополнительных итераций, дождется окончания уже запущенных и бросит исключение OperationCanceledException.

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

В последовательном цикле необработанное исключение выброшенное из цикла приводит к немедленной остановке исполняющей цикл конструкции. Параллельные циклы в e .NET Framework 4 максимально следуют этому поведению, оставаясь между тем надежными и предсказуемыми. На практике это означает, что когда возникает исключение в итерации, методы класса Parallel препятствуют запуску дополнительных итераций, хотя уже запущенные итерации принудительно не прекращаются. Как только все итерации остановлены, цикл собирает все брошенные исключения, оборачивает их в System.AggregateException и выбрасывает эту совокупность из цикла.

Как и в случае с Stop и Break, для ситуаций когда отдельные операции могут долго работать (и поэтому задерживать выход цикла), итерациям цикла может пригодиться возможность проверить были ли исключения в других итерациях. Для этого ParallelLoopState выставляет свойство IsExceptional (вдобавок к ранее упомянутым IsStopped и LowestBreakIteration), которое указывает бросила ли другая итерация необработанное исключение. Итерации могут совместно проверять это свойство, позволяя длительной итерации предварительно закончиться, когда обнаружена другая итерация с ошибкой.

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

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

Если Вам нужно такое поведение, похожую ручную обработку можно использовать и в Parallel.For:

ИСПОЛЬЗОВАНИЕ НЕСКОЛЬКИХ СТРАТЕГИЙ ВЫХОДА

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

Если исключений не было, но сработал CancellationToken и использовался Stop или Break, есть вероятность гонки по поводу того, что цикл заметил отмену до выхода. Если заметил, то цикл прервется исключением OperationCanceledException. Если нет - то, как уже пояснялось, завершится благодаря вызову Stop/Break.

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

Долгие итерации могут проверить некоторые свойства, чтобы прерваться раньше: IsStopped, LowestBreakIteration, IsExceptional и так далее. Для упрощения ParallelLoopState также предоставляет свойство ShouldExitCurrentIteration, которое эффективно упаковывает все проверки. Цикл самостоятельно проверяет это значение перед вызовом дополнительных итераций.

PARALLELENUMERABLE.FORALL

Parallel LINQ (PLINQ) из System.Core.dll в .NET Framework 4 предоставляет параллельную реализацию всех стандартных операторов запросов .NET Framework. Туда входят Select (проекция), Where(фильтр), OrderBy (сортировка) и многие другие. PLINQ также содержит несколько операторов, не представленных в его последовательном аналоге. Одним из таких операторов является AsParallel, который включает параллельную обработку LINQ-to-Objects запросов. Еще одним таким оператором является ForAll.

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

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

АНТИ ПАТТЕРНЫ

У Супермена есть криптонит. У материи есть антиматерия. А паттерны имеют свои антипаттерны. Паттерны предписывают хорошие способы решения определенных проблем, но это не значит, что в них нет потенциальных ловушек. Следует остерегаться некоторых возможных проблем в Parallel.For, Parallel.ForEach и ParallelEnumerable.ForAll.

РАЗДЕЛЯЕМЫЕ ДАННЫЕ

Новые конструкции для параллелизма в .NET Framework 4 помогают облегчить большинство шаблонного кода, который бы Вам пришлось написать для реализации восхитительно параллельных задач. Как Вы видели ранее, объем кода, необходимый только для реализации простенького цикла MyParallelFor, раздражает, а в хорошей реализации объем кода еще больше. Однако эти конструкции автоматически не обеспечивают потокобезопасности Вашего кода. Итерации внутри цикла должны быть независимы, а если это не так, Вы должны гарантировать, что итерации могут безопасно работать одновременно друг с другом, выполняя соответствующую синхронизацию.

В управляемых приложениях, один из наиболее распространенных паттернов, используемый для цикла for/For, – это итерация от 0 (включительно) до некоторой верхней границы (в C# исключающей, в Visual Basiс включающей). Впрочем, существует несколько вариаций этого паттерна, которые, не являясь общими, всё же встречаются не так редко.

НИСХОДЯЩАЯ ИТЕРАЦИЯ

Непривычно видеть циклы, перебирающие значения от исключительной верхней границы до 0 включительно:

Такой цикл обычно (хотя и не всегда), строится по причине зависимостей между итерациями; ведь, если все итерации независимы, зачем использовать более сложную форму цикла, если и восходящая и нисходящая итерации дают одинаковый результат?

Параллелизация такого цикла полна опасностей, из-за возможных зависимостей между итерациями. Если между итерациями нет зависимостей, метод Parallel.For можно использовать для обхода от включающей нижней границы до исключающей верхней, так как направление не имеет значения. В идеальном случае параллелизма – когда на компьютере количество ядер равно upperBound - все итерации будут исполняться одновременно, а само понятие направления нивелируется.

При распараллеливании циклов с нисходящей итерацией, нужно соблюдать осторожность. Нисходящая итерация зачастую является признаком отклонения от восхитительно параллельной задачи.

ИТЕРАЦИЯ С ШАГОМ БОЛЬШЕ 1

Еще одним шаблоном цикла for - не столь распространенным, как предыдущий, но и не редким – является вариант, использующий шаг больше единицы. Типичный цикл for выглядит так:

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

Parallel.For напрямую не поддерживает этот паттерн. Однако, класс Parallel все-таки можно использовать для реализации этого шаблона. Этого можно добиться, используя подход с итератором, наподобие показанного ранее для обхода связанных списков:

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

Как уже обсуждалось такая реализация, несмотря на очевидность, связана с дополнительными затратами на принудительную блокировку при доступе к итератору внутри метода Parallel.ForEach. Это приводит к поэлементным затратам на параллелизм и требует увеличения работы внутри элемента для того, чтобы компенсировать затраты и добиться преимуществ параллелизма.

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

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

СЛИШКОМ МАЛЕНЬКОЕ ТЕЛО ЦИКЛА

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

Вызовы делегатов. Если Вы поглядывали на предыдущие примеры с Parallel.For, вызов Parallel.For во многом похож на цикл for(C#) или For(Visual Basic). Не обманывайтесь: это все равно вызов метода. А главным следствием этого является то, что "тело цикла" передается в метод Parallel.For в виде делегата. Вызов делегата требует приблизительно столько же времени, что и вызов виртуального метода.

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

Для циклов с средним и большим телом этими затратами можно пренебречь. Но как только тело цикла уменьшается, расходы становятся более заметными. Если тело цикла очень мало, стоимость издержек может полностью перекрыть цикл. Поддержка параллелизма для циклов с маленьким телом требует обращения к вышеупомянутым пунктам #1 и #2. Первый паттерн заключается в разрезании входных данных на диапазоны и оборачивании последовательного цикла в параллельный цикл (вместо полной замены последовательного цикла на параллельный). Класс System.Concurrent.Collections.Partitioner содержит перегрузку метода Create, которая принимает целочисленный диапазон и возвращает OrderablePartitioner(доступна также вариация для Int64):

Перегрузки метода Parallel.ForEach принимают экземпляры Partitioner и OrderablePartitioner в качестве источников, делая возможной передачу результата вызова Partitioner.Create в вызов Parallel.ForEach. Теперь думайте о Partitioner и OrderablePartitioner, как о IEnumerable.

Tuple обозначает диапазон от включающей нижней границы до исключающей верхней. Рассмотрим следующий последовательный цикл:

Мы можем исполнить его параллельно с помощью Parallel.For следующим образом:

Или мы можем задействовать Parallel.ForEach с вызовом Partitioner.Create, выполняя последовательный цикл над диапазоном, содержащимся в Tuple, где inclusiveLowerBound соответствует свойству кортежа Item1, а exclusiveUpperBound - свойству Item2:

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

Хотя Parallel.For считается основным инструментом для параллелизации циклов, если измерения производительности показывают, что не удалось добиться ожидаемого выигрыша в скорости, можно попробовать описанный подход совместного использования Parallel.ForEach и Partitioner.Create.

ЧРЕЗМЕРНОЕ И НЕДОСТАТОЧНОЕ ДРОБЛЕНИЕ

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

Ранее в этом разделе мы демонстрировали упрощенный параллельный трассировщик лучей:

Обратите внимание, что здесь оба цикла можно безопасно распараллелить:

Однако возникает вопрос: когда и почему выбирается тот или другой цикл (или оба цикла) для параллелизации? Есть несколько противоречивых правил. С одной стороны, написание параллельного программного обеспечения, масштабируемого на любое количество ядер, подразумевает, что нужно разбивать как можно тщательнее, чтобы в независимости от количества доступных ядер, всегда иметь достаточно работы. Это правило подразумевает параллелизацию обоих циклов. С другой стороны, мы уже видели какие могут проблемы с производительностью, если внутри параллельного цикла будет недостаточно работы, окупающей затраты на его параллелизацию. Это означает, что для обеспечения содержательного тела цикла, следует исполнять параллельно только внешний цикл.

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

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

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

При таком выпрямлении тело цикла становится слишком мало (что ставит под сомнение производительность TraceRay из этого примера ) - можно задействовать рассмотренный ранее паттерн для маленьких тел циклов:

ПОТОКОНЕБЕЗОПАСНЫЕ РЕАЛИЗАЦИИ ILIST

И PLINQ и Parallel.ForEach запрашивают данные у источников, реализующих некоторые интерфейсы. Доступ к IEnumerable связан со значительными издержками из-за необходимости блокировки перечислителя и вызовов виртуальных методов MoveNext и Current для каждого элемента. С другой стороны, получение элемента из IList можно выполнять без блокировки, поскольку элементы IList независимы. Поэтому, и PLINQ и Parallel.ForEach автоматически используют реализацию IList, если таковую поддерживает источник.

В большинстве случаев это верное решение. Однако изредка реализация IList может быть не потокобезопасной для чтения вследствие того, что метод доступа get для индексатора списка изменяет разделяемое состояние. Для этого есть две основные причины:

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

Дорогостоящая загрузка структуры данных. В таких случаях может иметь место "ленивая" загрузка данных (загрузка по первому требованию), чтобы отложить или избежать некоторые расходы во время инициализации. Если запрос данных из списка запускает принудительную инициализацию, тогда его изменения могут происходить во время запроса элемента по индексу.

В .NET Framework всего несколько подобных сомнительных мест. Одним из которых является System.Data.Linq.EntitySet. Этот тип реализует IList с поддержкой ленивой загрузки, то есть первое, что делает метод доступа по индексу, так это загружает данные в EntitySet, если этого еще не было сделано.

Для обхода подобных проблем - если они перешли Вам дорогу - можно заставить и PLINQи Parallel.ForEach использовать реализацию IEnumerable вместо реализации IList. Есть два способа:

Используйте метод Create из класса System.Collections.Concurrent.Partitioner. У него есть перегрузка, заточенная под IEnumerable, которая гарантирует использование этого интерфейса (а не IList). Partitioner.Create возвращает экземпляр Partitioner, который принимают соответствующие перегрузки Parallel.ForEach и методов в PLINQ.

Добавить к источнику данных вызов Enumerable.Select. Select просто предотвращает обнаружение методами PLINQ и Parallel.ForEach реализации IList в исходном источнике данных .

PARALLEL.FOREACH НАД PARALLELQUERY{T}

Тип ParallelEnumerable из PLINQ работает с объектами ParallelQuery. Эти объекты возвращаются методом расширения AsParallel, а все операторы PLINQ производят и потребляют экземпляры ParallelQuery. Вообще-то ParallelQuery - это IEnumerable, то есть его можно итерировать и передавать в любой код, умеющий работать с IEnumerable.

Например, Parallel.ForEach - конструкция, работающая с IEnumerable. Раз так, есть соблазн написать код по следующему шаблону:

Хотя этот код и работает корректно, он содержит ненужные затраты. Для того, чтобы PLINQ передал данные в IEnumerable, сначала нужно соединить данные рассчитанные всеми потоками, участвующими в обработке запроса, чтобы несколько наборов данных могли обработаться кодом, требующим один набор данных. И наоборот, когда передается IEnumerable, Parallel.ForEach должен использовать цельный поток данных и разбивать его для параллельной обработки. То есть, при передаче ParallelQuery в Parallel.ForEach в .NET Framework 4 данные из запроса PLINQ будут объединены, а потом снова разделены на партиции методом Parallel.ForEach. Это может оказаться дорогостоящей процедурой.

Следует использовать метод ParallelEnumerable.ForAll из PLINQ. Переписав код следующим образом, мы избавимся от паразитного слияния и разбиения:

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

РОДСТВО С ПОТОКОМ ПРИ ДОСТУПЕ К ИСТОЧНИКУ ДАННЫХ

И Parallel.ForEach и ParallelEnumerable.ForAll считают, что каждый из участвующих в цикле потоков извлекает данные из перечислителя источника данных. Хотя оба метода гарантируют, что доступ в перечислителю выполняется потокобезопасным образом (только один поток в любой момент времени вызывает MoveNext и Current), все таки есть случаи множественного использования MoveNext. В целом, такая ситуация не должна быть проблемой. Однако изредка реализация MoveNext может учитывать родство с потоком, то есть из соображений корректности доступ к ней всегда идет через один поток, а возможно даже через отдельный поток. Таким примером может служить вызов MoveNext при доступе к элементу управления Windows Forms или Windows Presentation Foundation для получения данных. Или если элемент управления вытягивает данные из объектной модели приложения Microsoft Office. Хотя родство с потоком не рекомендуется, иногда его не всегда удается избежать.

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

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

ПАРАЛЛЕЛЬНЫЕ ЦИКЛЫ ДЛЯ СВЯЗАННЫХ С I/O ЗАДАЧ В МАСШТАБИРУЕМЫХ ПРИЛОЖЕНИЯХ

Очень соблазнительно применять конструкции идеально параллельных циклов в .NET Framework 4 для задач, связанных с I/O. Во многих случаях это совершенно разумно, потому что это быстрый и легкий способ повышения производительности.

Допустим, нам нужно опрашивать набор компьютеров. Мы можем реализовать это достаточно легко с помощью класса System.Net.NetworkInformation.Ping и LINQ:

Мы можем легко распараллелить эту операцию с помощью PLINQ, добавив всего несколько символов:

Вместо одного потока для опроса машин по очереди, этот код использует несколько потоков, что обычно сильно снижает необходимое для выполнения операции время. Конечно, в этом случае, выполняемая работа вообще не связана с процессорным временем. А еще по умолчанию PLINQ использует количество потоков равное количеству логических процессоров, что хорошо подходит для задач, связанных с CPU, а не с I/O. Поэтому мы можем использовать метод WithDegreeOfParallelism из PLINQ чтобы отработать еще быстрее, задействовав больше потоков (подразумевается, что у нас достаточно адресов для опроса чтобы качественно использовать все эти потоки):

Для клиентского приложения на настольном компьютере выполнение такой операции обычно не приводит к значительным проблемам. Однако, если этот код запустить в приложении для ASP.NET, он может оказаться смертельным. Создание потоков связано с затратами: на память, необходимую для структур данных потока и дополнительное воздействие на операционную систему и ее планировщик. Когда потоки выполняют реальную работу эти затраты окупаются. Но если потоки просто висят в заблокированном состоянии, ожидая завершения операции I/O, то они - мертвый груз. Особенно в web-приложениях, когда тысячи пользователей забрасывают систему запросами, дополнительная и ненужная ноша может тормозить систему. В масштабируемых системах, ориентированных на рост количества одновременно работающих пользователей, запрещается писать код наподобие показанного выше, хотя его написать проще простого. Есть другие решения.

Метод WithDegreeOfParallelism изменяет количество потоков, требуемых для выполнения запроса PLINQ, но не обеспечивает их существование. Если указанное число больше, чем число доступных потоков в ThreadPool, управляющему механизму ThreadPool потребуется некоторое время, чтобы подключить достаточно потоков для выполнения обработки запроса. Для ускорения Вы можете задействовать метод ThreadPool.SetMinThreads.

Класс System.Threading.Tasks.Task мы обсудим позже. Однаков вкратце отметим, что экземпляр Task представляет асинхронную операцию. Обычно такие операции занимаются интенсивными вычислениями, но абстракцию Task можно применять и в задачах, связанных с I/O, не думая о потоках. Подобный пример доступен по адресу http://code.msdn.microsoft.com/ParExtSamples в виде методов расширения для класса Ping, реализующих асинхронную версию метода Send и возвращающих Task. Используя эти методы, мы можем переписать предыдущую версию следующим образом:

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

Пример показанный выше использует класс Ping, построенный на шаблоне асинхронной модели, основанной на событиях (EAP). Этот шаблон был добавлен в .NET Framework 2.0 и использует события .NET, для уведомления о завершении асинхронной операции.

Более распространным паттерном в .NET Framework является Модель Асинхронного Программирования (APM), которая существовала в .NET Framework с самого начала. Иногда упоминается как паттерн "begin/end". Он основан на паре методов: метод "begin", начинающий асинхронную операцию и связывающийся с ней метод "end", который извлекает из операции результат вызова или исключение.

Для облегчения интерграции с этим паттерном, ранее упомянутый класс Task также можно применить для оборачивания APM вызова с помощью методаTask.Factory.FromAsync (что опять же улучшает масштабируемость). Впоследствии эту поддержку можно использовать для построения аналогов асинхронных методов, как сделано в методе расширения Task.Factory.Iterate (в примерах, доступных по адресу http://code.msdn.microsoft.com/ParExtSamples). Дополнительную информацию ищите по адресу http://blogs.msdn.com/pfxteam/9809774.aspx. Благодаря своему асинхронному функционалу для организации вычислительного процесса, F# в Visual Studio 2010 также предоставляет превосходную языковую поддержку для написания асинхронных методов. Как и развиваемый язык Axum, который можно скачать по адресу http://msdn.microsoft.com/en-us/devlabs/dd795202.aspx.

Внимание! Этот перевод, возможно, ещё не готов.
Его статус: перевод редактируется

Переведено на Нотабеноиде
http://notabenoid.org/book/16789/55189

Переводчики: vzhik