C++ - std::vector の配列の一部の参照 (View) を作成したい。

Question

環境

• C++11 (C++14, 17, 20 で実現可能なら他のバージョンでも可)
• Visual Studio 2017

質問内容

std::vector の配列の各要素を関数に渡して、ある処理を行って要素の値を更新するとします。
現在は以下のように順番に各要素に処理を行っていますが、1つの処理の計算量が重く、独立して行える処理のため、マルチスレッドで行いたいと思いました。

for(auto &v: vec)
    some_process(v);

そのため、std::vector の配列をスレッド数分に分割して関数に渡して処理したいと思ったのですが、C++ で Python のように「配列の一部の参照を作成して、関数に渡す」ということはできるのでしょうか。
現在は指定範囲のイテレータを渡すようにしていますが、よりよい方法があれば、ご教示いただけないでしょうか。

#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <thread>
#include <vector>

class SomeClass
{
  public:
    void process(
        std::vector<int>::iterator &begein,
        std::vector<int>::iterator &end,
        int mul) const
    {
        // vec の各要素になにかの処理、以下は例であり、実際は重たい処理になります。
        std::for_each(
            begein, end, [mul](int &v) { v = v * mul; });
    }
};


int main()
{
    SomeClass obj;

    // 初期化
    std::vector<int> vec(50);
    // vec = {1, 2, ..., 50}
    std::iota(vec.begin(), vec.end(), 1);
    std::for_each(
        vec.begin(), vec.end(), [](int &v) { std::cout << v << std::endl; });

    // マルチスレッドで処理
    const int num_threads = 5;  // スレッド数
    std::vector<std::thread> threads;

    // スレッドを作成する。
    for (int i = 0; i < num_threads; ++i) {
        auto begin = vec.begin() + i * 10;
        auto end = begin + 10;

        threads.push_back(std::thread(
            &SomeClass::process, &obj, std::ref(begin), std::ref(end), i));
    }

    // スレッドの終了待機
    for (std::thread &t : threads)
        t.join();

    // vec = {1*0, 2*0, ..., 9*0, 10*1, 11*1, ...}
    std::for_each(
        vec.begin(), vec.end(), [](int &v) { std::cout << v << std::endl; });
}

聞きたいこと

• std::vector の配列の一部の参照を作る方法について。
• 配列の各要素を(同じ要素にアクセスすることはないとはいえ)別々のスレッドから変更することに問題はないかどうか。

※ 上記の配列をスレッド数分分割して、スレッドごとに処理するというのは、とりあえず思いついた方法なので、それ以外の方法で高速化可能なら方法はなんでもいいです。

すみませんが、よろしくおねがいします。

Answer 1

配列の各要素を(同じ要素にアクセスすることはないとはいえ)別々のスレッドから変更することに問題はないかどうか。

はい。「std::vector<T>の異なる要素に対する別々スレッドからの変更操作」の安全性は、C++標準ライブラリ仕様で保証されます。記事「スレッドセーフという幻想と現実」もご参考にください。

std::vector の配列の一部の参照を作る方法について。

C++17現在は「区間の開始／終端位置を表すイテレータ・ペア」として表現するのが妥当かと思います。

C++20からは、std::vectorのような連続メモリ領域に対して部分区間を表す std::spanクラステンプレート が導入されます。本質的にはイテレータペアと等価ですが、“区間”を表す単一オブジェクトとして扱えるメリットはあります。

---

質問中のコード実装では、★箇所でダングリング参照による並行動作バグを引き起こします。変数begin, endは「forループの各反復処理中でのみ有効なイテレータオブジェクト」を指しますが、★では“参照”として別スレッドへと渡しています。つまり新しいスレッドが処理を始めるタイミングでは、既に該当イテレータオブジェクトが破棄されている 可能性 があり、意図しない不定動作やメモリ破壊などの不具合を引き起こします。

for (int i = 0; i < num_threads; ++i) {
  auto begin = vec.begin() + i * 10;
  auto end = begin + 10;

  threads.push_back(std::thread(&SomeClass::process, &obj,
    std::ref(begin), std::ref(end),  // ★
    i));
}

スレッド間をまたいで値（このケースではイテレータオブジェクト）を受け渡す場合、単に値を“コピー”するか、オブジェクトの有効範囲を注意深く制御した上で参照渡しを行なってください。

---

現在は以下のように順番に各要素に処理を行っていますが、1つの処理の計算量が重く、独立して行える処理のため、マルチスレッドで行いたいと思いました。

C++17標準ライブラリ範囲内であれば、並列アルゴリズムが提供されます。ただし、ご利用中の各コンパイラ／ライブラリが対応済みかは別途ご確認ください。

#include <algorithm>
#include <execution>

std::for_each(
  std::execution::par,  // スレッド並列処理を指示
  std::begin(vec), std::begin(end), [&](auto&& e) {
    // 1要素に対する処理
  });

外部OSSライブラリの利用でもよければ、Intel TBBもオススメです。ライセンスもPermissiveです。

Comments

[tiitoi]

ご指摘いただいた通り、イテレータが次のループにいったら有効でなくなってしまうことを見落としてました。実際、本日マルチスレッド化してから不定期に core dump する現象が発生していて、デバッグしていたのですが、原因がつかめていませんでした。それが原因の可能性がかなり高そうなので、明日確認してみます。

> 単に値を“コピー”するか

イテレータ自体、std の関数にわたすか、for 文でしか使ったことがなかったので理解が不十分なのですが、イテレータを値渡しして、渡した先で値の変更を行った場合、元の配列に反映されるのでしょうか？
てっきり参照渡しかポインタ渡ししないと、渡した側に変更が伝わらないと思って参照渡しにしていました。

[yohhoy]

(少々乱暴な説明ですが)vectorコンテナとイテレータの関係は、配列とポインタの関係と同じです。イテレータのコピー／値渡しは、ポインタ値のコピー／値渡しと同等の解釈で問題ありません。

> イテレータを値渡しして、渡した先で値の変更を行った場合、元の配列に反映されるのでしょうか？
以上より、複製されたイテレータ経由の変更であっても期待通り元コンテナに反映されます。

[tiitoi]

なるほど。理解しました。
C++ のイテレータの理解がまだ怪しいので勉強してみます。

また C++20 なので、使える環境がすぐには用意できないですが、ご紹介いただいた std::span が当初やりたかったことに近そうです。

[tiitoi]

イテレータのスコープのバグを発見してくださった yohhoy さんを BA にさせていただきましたが、
t_obara さん、Chironian さん、yohhoy さんの回答は、どれも大変参考になりました。
皆さん、丁寧がご回答ありがとうございます。

[t_obara]

std::spanは知りませんでした、参考になりました。

Answer 2

こんにちは。

std::vector の配列の一部の参照を作る方法について。

現在のSTLの範疇ではご提示されている内容は妥当と思います。
C++11で規定された範囲ベースforと、まだ残念ながら規定されていないrangeを使えば多少見やすくなりますが、本質は変わりません。

配列の各要素を(同じ要素にアクセスすることはないとはいえ)別々のスレッドから変更することに問題はないかどうか。

std::vectorに要素を追加・削除しなければ問題ないです。（異なる領域を別スレッドで変更しても問題は発生しません。）

※ 上記の配列をスレッド数分分割して、スレッドごとに処理するというのは、とりあえず思いついた方法なので、それ以外の方法で高速化可能なら方法はなんでもいいです。

スレッド・プールを実装して処理することが考えられます。
スレッドへの要求キューを作り、std::vector内のデータ１つに対して１つエンキューし、用意した複数のスレッドへ次々とそれらの要求を割り当てていくイメージです。
スレッド・プールの実装方法は様々なものが議論されていると聞きますので、もしかすると使いやすいものがあるかも知れません。

これを使えば個々の処理時間がバラついても、CPU使用率を最大化できると思います。
（ご提示のコードの場合、各10個のセットの内、例えばどれか1つだけ極端に時間がかかってしまうと、他のスレッドが先に終了してしまい、CPUの使用率は落ちます。）

Comments

[tiitoi]

> 現在のSTLの範疇ではご提示されている内容は妥当と思います。

Python をよく使うのでリストの slice のようなやり方を探していたのですが、言われてみれば、stl の関数はほとんど begin, end を引数としてとるようになっているので、今のやり方でも C++ ではよいかもしれませんね。

> スレッド・プールを実装して処理することが考えられます。

スレッドプールという設計は知りませんでした。
ぜひ使ってみたいので、既存のライブラリを探してみます。

ご回答ありがとうございました。

[tiitoi]

ご紹介いただいた std::experimental::ranges::Range が当初やりたかったことに近いかもしれません。
STL の導入予定は今の所ないのですね。。

[yohhoy]

FYI: Range自体はC++20標準ライブラリ導入が決まっていますよ。実際に普及するのはもう少し未来になると思いますけど;P https://en.cppreference.com/w/cpp/ranges/Range おそらくstd::range::subrange が求めるモノになるのではと思います。

[tiitoi]

なるほど。C++11 以降に追加されたまたは追加予定の STL の関数を全然把握できていないので、勉強します。ご紹介ありがとうございます。

Answer 3

マルチコアなシステムであれば、とりあえずマルチスレッド化する効果が期待できると思いますが、まずは測定してから取り組むことをお勧め致します。
各要素を変更するのみであれば、スレッドセーフです。
https://ja.cppreference.com/w/cpp/container

ただ、渡した後の処理が重いのであれば、assignで渡したとしても微々たる影響ではないでしょうか。

Comments

[tiitoi]

> 各要素を変更するのみであれば、スレッドセーフです。
なるほど。スレッドセーフとのことで安心しました。
記載いただいたリンクの「スレッド安全性」についても読んでみます。

丁寧なご回答ありがとうございました。