Заголовочный файл execution мы еще не видели, он появился в C++17.
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <execution>
using namespace std;
2. В качестве примера создадим функцию-предикат, которая говорит, является ли число четным. Мы воспользуемся ею далее.
static bool odd(int n) { return n%2; }
3. Сначала определим в нашей функции main большой вектор. Заполним его большим количеством данных, чтобы для выполнения вычислений потребовалось какое-то время. Скорость выполнения этого кода будет значительно различаться в зависимости от того, на каком компьютере работает этот код. Для разных компьютеров скорее подойдут меньшие/большие размеры вектора.
int main()
{
vector<int> d (50000000);
4. Чтобы получить большое количество случайных данных для вектора, создадим генератор случайных чисел и распределение и упакуем их в вызываемый объект. Если это кажется странным, пожалуйста, взгляните сначала на примеры, в которых рассматриваются генераторы случайных чисел и распределения в главе 8.
mt19937 gen;
uniform_int_distribution<int> dis(0, 100000);
auto rand_num ([=] () mutable { return dis(gen); });
5. Теперь воспользуемся стандартным алгоритмом std::generate, чтобы заполнить вектор случайными данными. В С++17 существует новая версия этого алгоритма, которая принимает аргумент нового типа: политику выполнения. Здесь поместим std::par, что позволит автоматически распараллелить данный код. Сделав это, позволим нескольким потокам заполнять вектор одновременно; данное действие снижает время выполнения, если компьютер имеет более одного процессора, что обычно верно для современных машин.
generate(execution::par, begin(d), end(d), rand_num);
6. Метод std::sort тоже должен быть вам знаком. Версия C++17 также поддерживает дополнительный аргумент, определяющий политику выполнения:
sort(execution::par, begin(d), end(d));
7. Это верно и для std::reverse:
reverse(execution::par, begin(d), end(d));
8. Затем воспользуемся функцией std::count_if, чтобы подсчитать количество четных чисел в векторе. Мы даже можем распараллелить выполнение алгоритма, просто добавив политику выполнения снова!
auto odds (count_if(execution::par, begin(d), end(d), odd));
9. Вся эта программа не выполняет никакой реальной научной работы, поскольку мы просто смотрим, как можно распараллелить стандартные алгоритмы, но выведем что-нибудь на экран в конце работы.
cout << (100.0 * odds / d.size())
<< "% of the numbers are odd.n";
}
10. Компиляция и запуск программы дадут следующий результат. К этому моменту интересно посмотреть, как отличается скорость выполнения при использовании алгоритмов без политики выполнения в сравнении со всеми другими политиками выполнения. Данное упражнение оставим на откуп читателю. Попробуйте его сделать; доступными политиками выполнения являются seq, par и par_vec. Для каждой из них мы должны получить разное время выполнения:
$ ./auto_parallel
50.4% of the numbers are odd.
Как это работает
Поскольку в этом примере мы не отвлекались на решение сложных реальных задач, можем полностью сконцентрироваться на вызовах функций стандартных библиотек. Довольно очевидно, что их параллелизованные версии едва отличаются от классических последовательных вариаций. Они отличаются всего на один дополнительный аргумент — политику выполнения.
Взглянем на вызовы и ответим на три основных вопроса:
generate(execution::par, begin(d), end(d), rand_num);
sort( execution::par, begin(d), end(d));
reverse( execution::par, begin(d), end(d));
auto odds (count_if(execution::par, begin(d), end(d), odd));
Какие алгоритмы STL можно распараллелить таким образом?
Шестьдесят девять существующих алгоритмов STL получили поддержку параллелизма по стандарту C++17. Появились также семь новых алгоритмов, которые тоже поддерживают параллелизм. Несмотря на то что такое улучшение может оказаться довольно инвазивным для реализации, с точки зрения их интерфейса изменилось не очень много: все они получили дополнительный аргумент ExecutionPolicy&& policy и все. Это не значит, что мы всегда должны предоставлять аргумент, описывающий политику выполнения. Они просто дополнительно поддерживают передачу политики выполнения в качестве первого аргумента.
Перед вами 69 улучшенных стандартных алгоритмов. Кроме того, в этот список включены семь новых алгоритмов, изначально поддерживающих политики выполнения (выделены полужирным):
std::adjacent_difference
std::adjacent_find
std::all_of
std::any_of
std::copy
std::copy_if
std::copy_n
std::count
std::count_if
std::equal
std::exclusive_scan
std::fill
std::fill_n
std::find
std::find_end
std::find_first_of
std::find_if
std::find_if_not
std::for_each
std::for_each_n
std::generate
std::generate_n
std::includes
std::inclusive_scan
std::inner_product
std::inplace_merge
std::is_heap
std::is_heap_until
std::is_partitioned
std::is_sorted
std::is_sorted_until
std::lexicographical_compare
std::max_element
std::merge std::min_element
std::minmax_element
std::mismatch std::move
std::none_of
std::nth_element
std::partial_sort
std::partial_sort_copy
std::partition
std::partition_copy
std::remove
std::remove_copy
std::remove_copy_if
std::remove_if
std::replace
std::replace_copy
std::replace_copy_if
std::replace_if
std::reverse
std::reverse_copy
std::rotate
std::rotate_copy
std::search
std::search_n
std::set_difference
std::set_intersection
std::set_symmetric_difference
std::set_union
std::sort
std::stable_partition
std::stable_sort
std::swap_ranges
std::transform
std::transform_exclusive_scan
std::transform_inclusive_scan
std::transform_reduce
std::uninitialized_copy
std::uninitialized_copy_n
std::uninitialized_fill
std::uninitialized_fill_n
std::unique
std::unique_copy
Улучшение этих алгоритмов — отличная новость! Чем больше алгоритмов STL используется в наших старых программах, тем проще добавить поддержку параллелизма задним числом. Обратите внимание: это не значит, что такие изменения автоматически сделают программу в N раз быстрее, поскольку концепция многопроцессорной обработки гораздо сложнее.
Однако вместо того, чтобы разрабатывать собственные сложные параллельные алгоритмы с помощью std::thread, std::async или внешних библиотек, можно распараллелить выполнение стандартных задач способом, не зависящим от операционной системы.
Как работают эти политики выполнения
Политика выполнения указывает, какую стратегию автоматического распараллеливания необходимо использовать при вызове стандартных алгоритмов.
Следующие три типа политик существуют в пространстве имен std::execution (табл. 9.1).
Политики выполнения подразумевают конкретные ограничения. Чем они строже, тем больше мер по распараллеливанию можно позволить:
□ все элементы функций доступа, используемые параллелизованными алгоритмами, не должны вызывать взаимных блокировок и гонок;
□ в случае параллелизации и векторизации все функции получения доступа не должны использовать блокирующую синхронизацию.
До тех пор, пока подчиняемся этим правилам, мы не столкнемся с ошибками, которые могут появиться в параллельных версиях алгоритмов STL.
Обратите внимание: правильное использование параллельных алгоритмов STL не всегда гарантирует ускорение работы. В зависимости от того, какую задачу мы пытаемся решить, ее размера, эффективности наших структур и других методов доступа, измеряемое ускорение будет значительно различаться или даже и вовсе не произойдет. Многопроцессорная обработка — это все еще довольно сложно.
