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

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

Что означает понятие «векторизация»

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

std::vector v {1, 2, 3, 4, 5, 6, 7 /*...*/};

int sum {std::accumulate(v.begin(), v.end(), 0)};

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

int sum {0};

for (size_t i {0}; i < v.size(); ++i) {

  sum += v[i];

}

С этого момента при разрешенной и включенной векторизации компилятор может создать следующий код. Цикл выполняет четыре шага сложения в одной итерации цикла, что сокращает количество итераций в четыре раза. Для простоты пример не работает с остатком, если вектор не содержит N*4 элементов:

int sum {0};

for (size_t i {0}; i < v.size() / 4; i += 4) {

  sum += v[i] + v[i+1] + v[i + 2] + v[i + 3];

}

// если операция v.size()/4 имеет остаток,

// в реальном коде также нужно это обработать.

Зачем это делать? Многие процессоры предоставляют инструкции, которые могут выполнять математические операции наподобие sum += v[i]+v[i+1]+v[i+2]+v[i+3]; всего за один шаг. Сжатие большого количества математических операций в минимальное количество инструкций — наша цель, поскольку это ускоряет программу.

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

Приостанавливаем программу на конкретный промежуток времени