C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц

Заголовочный файл 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 не всегда гарантирует ускорение работы. В зависимости от того, какую задачу мы пытаемся решить, ее размера, эффективности наших структур и других методов доступа, измеряемое ускорение будет значительно различаться или даже и вовсе не произойдет. Многопроцессорная обработка — это все еще довольно сложно.