C++1z 並列アルゴリズムライブラリ

C++

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を同時に行います。

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。