Параллельное программирование на С++ в действии

Раз уж мы выбрали интерфейс в духе ФП, то для рекурсивной сортировки обеих «половин» нужно создать два списка. Для этого мы снова используем функцию splice(), чтобы переместить значения из списка input до divide_point включительно в новый список lower_part (4). После этого input будет со держать только оставшиеся значения. Далее оба списка можно отсортировать путем рекурсивных вызовов (5), (6). Применяя std::move() для передачи списков, мы избегаем копирования — результат в любом случае неявно перемещается. Наконец, мы еще раз вызываем splice(), чтобы собрать result в правильном порядке. Значения из списка new_higher попадают в конец списка (7), после опорного элемента, а значения из списка new_lower — в начало списка, до опорного элемента (8).

Параллельная реализация Quicksort в духе ФП

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

Листинг 4.13. Параллельная реализация Quicksort с применением будущих результатов

template

std::list parallel_quick_sort(std::list input) {

 if (input.empty()) {

  return input;

 }

 std::list result;

 result.splice(result.begin(), input, input.begin());

 T const& pivot = *result.begin();

 auto divide_point = std::partition(input.begin(), input.end(),

  [&](T const& t) {return t

 std::list lower_part;

 lower_part.splice(

  lower_part.end(), input, input.begin(), divide_point);

 std::future > new_lower( ←(1)

  std::async(∥_quick_sort, std::move(lower_part)));

 auto new_higher(

  parallel_quick_sort(std::move(input))); ←(2)

 result.splice(result.end(), new_higher); ←(3)

 result.splice(result.begin(), new_lower.get()); ←(4)

 return result;

}

Существенное изменение здесь заключается в том, что сортировка нижней части списка производится не в текущем, а в отдельном потоке — с помощью std::async() (1). Верхняя часть списка сортируется путем прямой рекурсии, как и раньше (2). Рекурсивно вызывая parallel_quick_sort(), мы можем задействовать доступный аппаратный параллелизм. Если std::async() создает новый поток при каждом обращении, то после трех уровней рекурсии мы получим восемь работающих потоков, а после 10 уровней (когда в списке примерно 1000 элементов) будет работать 1024 потока, если оборудование позволяет. Если библиотека решит, что запущено слишком много задач (быть может, потому что количество задач превысило уровень аппаратного параллелизма), то может перейти в режим синхронного запуска новых задач. Тогда новая задача будет работать в том же потоке, который обратился к get(), а не в новом, так что мы не будем нести издержки на передачу задачи новому потоку, если это не увеличивает производительность. Стоит отметить, что в соответствии со стандартом реализация std::async вправе как создавать новый поток для каждой задачи (даже при значительном превышении лимита), если явно не задан флаг std::launch::deferred, так и запускать все задачи синхронно, если явно не задан флаг std::launch::async. Рассчитывая, что библиотека сама позаботится об автоматическом масштабировании, изучите, что говорится на эту тему в документации, поставляемой вместе с библиотекой.

Можно не использовать std::async(), а написать свою функцию spawn_task(), которая будет служить оберткой вокруг std::packaged_task и std::thread, как показано в листинге 4.14; нужно создать объект std::packaged_task для хранения результата вызова функции, получить из него будущий результат, запустить задачу в отдельном потоке и вернуть будущий результат. Само по себе это не дает большого преимущества (и, скорее всего, приведёт к значительному превышению лимита), но пролагает дорогу к переходу на более хитроумную реализацию, которая помещает задачу в очередь, обслуживаемую пулом потоков. Рассмотрение пулов потоков мы отложим до главы 9. Но идти по такому пути вместо использования std::async имеет смысл только в том случае, когда вы точно знаете, что делаете, и хотите полностью контролировать, как пул потоков строится и выполняет задачи.