C++1zでは、並列アルゴリズムのライブラリが導入されることになりました。このライブラリは、<algorithm>
, <numeric>
, <memory>
で定義されるアルゴリズムのオーバーロードという形で提供されます。
using namespace std::execution; // 実行ポリシーの名前空間 std::vector<int> v = … std::sort(v.begin(), v.end()); // これまで通りの順序実行 std::sort(seq, v.begin(), v.end()); // 明示的に順序実行を指定 std::sort(par, v.begin(), v.end()); // 並列実行を許可 std::sort(par_unseq, v.begin(), v.end()); // 並列and/orベクトル実行を許可
このライブラリの設計は、Thrustが元になっています。
実行ポリシー
並列アルゴリズムには、実行ポリシー (execution policy) を指定して使用します。実行ポリシーには、以下の種類があります:
実行ポリシー | 型 | ポリシー値 |
---|---|---|
順序実行 (これまで通りのシングルスレッド実行) |
sequential_execution_policy |
seq |
並列実行 | parallel_policy |
par |
並列実行および/もしくはベクトル実行 | parallel_unsequenced_policy |
par_unseq |
注意としては、実行ポリシーとして並列実行を指定した場合、規格上は「並列実行を許可する」というリクエストの意味になるということです。コンパイラやその他環境条件によっては、シングルスレッドで実行されるかもしれません。
実行ポリシーの定義は、新設される<execution>
ヘッダで行われます。
実行ポリシーごとに型が付けられ、それらの型でオーバーロードができます。並列アルゴリズムの宣言としては、以下のようになります:
template <class ExecutionPolicy, class InputIterator, class Function> void for_each(ExecutionPolicy&& exec, InputIterator first, InputIterator last, Function f);
並列アルゴリズムに対応するアルゴリズム
並列アルゴリズムは、<algorithm>
, <numeric>
, <memory>
の全てが対象にはなりません。2016年9月段階では、以下のアルゴリズムが対象となります。
<algorithm>
adjacent_find
all_of
any_of
copy
copy_if
copy_n
count
count_if
equal
fill
fill_n
find
find_end
find_first_of
find_if
find_if_not
for_each
for_each_n
(new)generate
generate_n
includes
inplace_merge
is_heap
is_heap_until
is_partitioned
is_sorted
is_sorted_until
lexicographical_compare
max_element
merge
min_element
minmax_element
mismatch
move
none_of
nth_element
partial_sort
partial_sort_copy
partition
partition_copy
remove
remove_copy
remove_copy_if
remove_if
replace
replace_copy
replace_copy_if
replace_if
reverse
reverse_copy
rotate
rotate_copy
search
search_n
set_difference
set_intersection
set_symmetric_difference
set_union
sort
stable_partition
stable_sort
swap_ranges
transform
unique
unique_copy
<numeric>
adjacent_difference
exclusive_scan
(new)inclusive_scan
(new)inner_product
reduce
(new)transform_exclusive_scan
(new)transform_inclusive_scan
(new)transform_reduce
(new)
<memory>
uninitialized_copy
uninitialized_copy_n
uninitialized_fill
uninitialized_fill_n
<numeric>
については、並列アルゴリズムのほとんどが新たに作られることになります。
exclusive_scan()
とinclusive_scan()
は、partial_sum()
の亜種です。inclusive_scan()
はpartial_sum()
と同様に、先頭要素が出力に含まれます。exclusive_scan()
の出力に先頭要素は含まれません。
reduce()
はaccumulate()
の亜種で、実行順序が非決定的になります。
transform_exclusive_scan()
とtransform_inclusive_scan()
は、1引数をとる変換関数で要素を変換した結果を、2引数をとる集計関数に渡します。transform + scanを同時に行います。transform_reduce()
も同様に、transform + reduceを同時に行います。
参照
- N3408 Parallelizing the Standard Algorithms Library
- N3429 A C++ Library Solution to Parallelism
- N3554 A Parallel Algorithms Library
- P0024R2 The Parallelism TS Should be Standardized
- P0394R4
terminate()
for Parallel Algorithms Exception Handling - P0336R1 Better Names for Parallel Execution Policies in C++17
お断り
この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。