Каковы ограничения для пользователя, использующего параллельные алгоритмы STL?

На встрече в Джексонвилле предложение P0024r2 эффективно использует спецификации Parallelism TS был принят в С++ 17 (черновик). Это предложение добавляет перегрузки для многих алгоритмов, принимающих аргумент политики выполнения, чтобы указать, какой тип parallelism следует учитывать. В <execution> (20.19.2 [исполнение]) определены три политики выполнения:

std::execution::sequenced_policy (20.19.4 [execpol.seq]) с объектом constexpr std::execution::seq (20.19.7 [parallel.execpol.objects]), чтобы указать последовательное выполнение, подобное вызову алгоритмов без политики выполнения.
std::execution::parallel_policy (20.19.5 [execpol.par]) с объектом constexpr std::execution::par (20.19.7 [parallel.execpol.objects]), чтобы указать выполнение алгоритмов, потенциально использующих несколько потоков.
std::execution::parallel_unsequenced_policy (20.19.6 [execpol.vec]) с объектом constexpr std::execution::par_unseq (20.19.7 [parallel.execpol.objects]), чтобы указать выполнение алгоритмов, потенциально использующих векторное выполнение и/или множественные потоки.

Алгоритмы STL обычно принимают определяемые пользователем объекты (итераторы, объекты функций) в качестве аргументов. Каковы ограничения на пользовательские объекты, чтобы сделать их пригодными для использования с параллельными алгоритмами с использованием стандартных политик выполнения?

Например, при использовании алгоритма, как в приведенном ниже примере, каковы последствия для FwdIt и Predicate?

template <typename FwdIt, typename Predicate>
FwdIt call_remove_if(FwdIt begin, FwdIt end, Predicate predicate) {
    return std::remove_if(std::execution::par, begin, end, predicate);
}

Ответ 1

Короткий ответ заключается в том, что функции доступа к элементу (по существу, операции, требуемые алгоритмами для различных аргументов, см. ниже для подробностей), используемые с алгоритмами с использованием политики выполнения std::execution::parallel, не допускаются к сбоям данных или к ошибкам, замки. Функции доступа к элементу, используемые с алгоритмами с использованием политики выполнения std::execution::parallel_unsequenced_policy дополнительно, не могут использовать блокирующую синхронизацию.

Подробности

Описание основано на бюллетене N4604. Я не проверял, были ли изменены некоторые положения в ответ на замечания национальных органов (беглый тест, похоже, подразумевает, что до сих пор не было изменений).

Раздел 25.2 [algorithmms.parallel] указывает семантику параллельных алгоритмов. Существует несколько ограничений, которые не применяются к алгоритмам, не принимающим политику выполнения, разбитым на несколько разделов:

В 25.2.2 [algorithmms.parallel.user] сдерживает то, что предикатные функции могут выполнять с их аргументами:

Объекты функций, переданные в параллельные алгоритмы, как объекты типа Predicate, BinaryPredicate, Compare и BinaryOperation не должны прямо или косвенно изменять объекты через свои аргументы.

Как написано предложение, сами объекты могут быть изменены до тех пор, пока выполняются другие ограничения (см. ниже). Обратите внимание, что это ограничение не зависит от политики выполнения и, таким образом, применяется даже при использовании std::execution::sequenced_policy. Полный ответ более сложный, чем это, и кажется, что спецификация в настоящее время непреднамеренно ограничена (см. Последний абзац ниже).
В 25.2.3 [algorithmms.parallel.exec] добавляются ограничения на функции доступа к элементу (см. ниже), которые относятся к различным политикам выполнения:
- При использовании std::execution::sequenced_policy функции доступа к элементу вызывается из одного потока, то есть выполнение не чередуется в любой форме.
- При использовании std::execution::parallel_policy разные потоки могут одновременно ссылаться на функции доступа к элементу из разных потоков. Вызов функций доступа к элементу из разных потоков не позволяет вызывать расы данных или вызывать блокировки. Однако вызовы доступа к элементу из одного потока являются [неопределенно] последовательностью, то есть нет перемеженных вызовов функции доступа к элементу из того же потока. Например, если Predicate, используемый с std::execution::par, подсчитывает, как часто он вызывается, соответствующий счет должен быть соответствующим образом синхронизирован.
- При использовании std::execution::parallel_unsequenced_policy вызов функций доступа к элементу может чередоваться как между различными потоками, так и внутри одного потока выполнения. То есть использование примитива синхронизации блокировки (например, std::mutex) может привести к блокировке блокировки, поскольку один и тот же поток может попытаться синхронизировать несколько раз (и, например, попытаться заблокировать один и тот же мьютекс несколько раз). При использовании стандартных библиотечных функций для функций доступа к элементу ограничение в стандарте (25.2.3 [algorithms.parallel.exec], пункт 4):
  
  Стандартная функция библиотеки является векторизации-небезопасной, если она задана для синхронизации с другим вызовом функции или для вызова другой функции для синхронизации с ней и если она не является функцией выделения или освобождения памяти. Нестандартные библиотечные функции, связанные с вложением, не могут быть вызваны кодом пользователя, вызванным из execution::parallel_unsequenced_policy алгоритмов.
- Что происходит при использовании политик выполнения, определенных при реализации, неудивительно, что реализация определена.
В 25.2.4 [algorithm.parallel.exception] использование исключений, выведенных из функций доступа к элементу, является определенным ограничением: когда функция доступа к элементу генерирует исключение, вызывается std::terminate(). То есть, законно исключать исключение, но маловероятно, чтобы результат был желательным. Обратите внимание, что std::terminate() будет вызываться даже при использовании std::execution::sequenced_policy.

Функции доступа к элементу

В приведенных выше ограничениях используется функция доступа к элементу term. Этот термин определен в параграфе 25.2.1 [algorithm.parallel.defns]. Существует четыре группы функций, классифицированных как функции доступа к элементу:

Все операции категорий итераторов, с которыми был создан алгоритм.

Операции над теми элементами последовательности, которые требуются по его спецификации.

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

Операции над этими функциональными объектами, требуемыми спецификацией.

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

Проблема

Немного о том, что, похоже, нет никакой гарантии, что объекты, к которым применяются функции доступа к элементу [mutating], различаются между разными потоками. В частности, я не вижу никакой гарантии, что операции итератора, примененные к объекту итератора, не могут быть применены к одному и тому же объекту итератора из двух разных потоков! Импликация заключается в том, что, например, operator++() для объекта итератора необходимо каким-то образом синхронизировать его состояние. Я не вижу, как, например, operator==() может сделать что-то полезное, если объект изменен в другом потоке. Кажется непреднамеренным, что операции на одном и том же объекте должны быть синхронизированы, так как не имеет никакого смысла применять [mutating] функции доступа к элементу одновременно с объектом. Тем не менее, я не вижу никакого текста, говорящего о том, что используются разные объекты (я думаю, мне нужно поднять дефект для этого).