マルチスレッドでループを最適化してみたが速くない

Question

前提・実現したいこと

2つの同じサイズのvectorの同一性の比較としてthreadを作ったのですが，想定に反して速くありません。何が問題なのかお分かりになる方がいらっしゃれば教えてください。
構造は至って単純です。
・elapsed_time_dblは時間計測用テンプレート関数
・is_eq_ob　スレッド管理クラス ,!=を見つけたときのスレッド中止用フラッグとしてatomicを使用。結果判定返却用として兼用。

該当のソースコード

#include <thread>
#include <chrono>
#include <vector>
using namespace std;
template<class TimePoint>
double elapsed_time_dbl(const std::string& msg, const TimePoint& start) {
    auto end=std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> fp_ms = end-start;
    std::cout << msg <<" : " << fp_ms.count()<<" ms\n";
    return fp_ms.count();
}
class is_eq_ob{
    int size;
    const vector<int>& m_a;
    const vector<int>& m_b;
    atomic<bool> m_loop_end;
public:
    is_eq_ob(const vector<int>&a, const vector<int>&b):
    m_a{a},m_b{b},m_loop_end{false},size{(int)a.size()}{}
 
    void comp_thread(int st, int count ){
        for(int i=0;i < count;i++){
            if(m_loop_end.load())
                return ;
            if( m_a[st+ i] != m_b[st+ i] ){
                m_loop_end.store(true);
                return ;
            }
        }
    }
    bool go(){
        
        vector<thread> th_s;
        int div = 10;
        ///divの数のスレッド生成,sizeをdiv数で分割してブロックごとに処理
        for(int d=0;d < div;d++){
            int start = size * d/div;//スレッドに渡す開始位置
            int end   = (d==div-1) ? size: size*(d+1)/div;//スレッドに渡す終了位置
            thread a(&is_eq_ob::comp_thread,this, start, end - start);
            th_s.push_back( move(a) );
        }
        
       for(auto& th: th_s)
           th.join();
        
        return !m_loop_end.load();
    }
};


int main(){
   
    vector<int> a(1000,0);
    vector<int> b(1000,0);
    //a[100]=1;
    
    auto start=std::chrono::high_resolution_clock::now();
    cout << (a==b)<<'\n';
    elapsed_time_dbl("a==b", start);
    
    is_eq_ob is_eq(a,b);
    start=std::chrono::high_resolution_clock::now();
    cout << is_eq.go() <<'\n';
    elapsed_time_dbl("is_eq_ob", start);
    return 0;
}

試したこと

結果は次のように常にスレッドの方が遅くなります。
1
a==b : 0.064569 ms
1
is_eq_ob : 0.37863 ms

Comments

[tiitoi]

配列の規模が小さすぎるので、スレッド化するコストのほうが上回ってしまっているのでは？

[jbe00214]

オーバーヘッドですよね。たしかにそうなんですが，この例では，そうなりますね。サイズを1000000にすると，
1
a==b : 1.91292 ms
1
is_eq_ob : 0.519138 ms
となります。
mainにコメント行を入れてあり，これを外して100の位置に不整合となる値を入れると，
0
a==b : 0.071875 ms
0
is_eq_ob : 0.333058 ms
となり，少なくともスレッド1は早めに戻ってくると思うのですが，これもオーバーヘッドなんですかね。

[pododezo469]

そっちの方は全スレッド終了待機のオーバーヘッドだと思います。
確認方法としては、以下のようにして不整合判定時に時間を出力すると非マルチスレッド版と同程度になると思います。

スレッド使う開始時間は上の方に別の高域変数として定義しておいて、
using namespace std;
static std::chrono::high_resolution_clock::time_point thread_start;

スレッドの方の開始時間をセットしてから開始、
thread_start = std::chrono::high_resolution_clock::now();
is_eq_ob is_eq(a,b);

あとは不整合判定直後に出力する。
if( m_a[st+ i] != m_b[st+ i] ){
elapsed_time_dbl("is_eq_ob", thread_start);

もちろんこのやり方だと複数回不整合出力されてしまう可能性のあるコードとなりますが、
全スレッド終了待機に時間がかかっていることが分かればあとはやり方次第です。

[jbe00214]

そうなんです。私もやってみました。どうやら，早期に不一致を検出しているにもかかわらず，全部のスレッドの終了まで待機させられているようなんですね。そこまでわかったのですが，これを回避する手段がみつからなくて...。

Answer 1

諸氏のいうとおり，スレッド管理のオーバヘッドの方が大きく，単純な値の比較程度の処理であれば，スレッドを使わずに単純なループで十分のようです。3つ程度のスレッドでもオーバーヘッドは小さくなりませんでした。

Answer 2

スレッドの効果を判断するためには、マルチスレッドの場合とシングルの場合で同じロジックで比較しなければなりません。試しにやってみたら、マルチスレッドの方が速くはなっていますが、やはりvectorの比較演算子は桁が違いますね。vectorの比較演算子の実装が単純なループコンペアでは無いのでしょう。

デバッグ版での結果ですが
vectorサイズ 1億

vector比較演算子 1047.04ms
main関数内でa,bのループコンペア 17159.7ms
go() div=1 23816.6ms
go() div=10 12923ms

Comments

[jbe00214]

vectorは速いですね。試されたのは全要素の比較でしょうか，それとも，不整合となるデータがある場合の検出での結果でしょうか。不整合データをどのあたりに挿入した結果でしょうか。

[Zee]

不整合無しで全要素の比較です。

Answer 3

1000個程度では処理が軽すぎて、10個のスレッド生成のオーバーヘッドの方が大きいのではないかと。
もっと数を増やしてはどうですか。

Comments

[jbe00214]

vectorを1'000'000，スレットを3にして動かしても同様です。なお，mainのコメント部分を外し，不一致を検出させてみます。次のようにスレッド関数内に時間計測を入れて，クラスのprivate部にmutex mを入れて計測してみます。
void comp_thread(int st, int count ){
auto start=std::chrono::high_resolution_clock::now();
for(int i=0;i < count;i++){
if(m_loop_end.load()){
lock_guard<mutex> lock(m);
elapsed_time_dbl("killed ", start);
return ;
}
if( m_a[st+ i] != m_b[st+ i] ){
m_loop_end.store(true);
lock_guard<mutex> lock(m);
elapsed_time_dbl("detected", start);
return ;
}
}
}
結果は，
0
a==b : 0.071853 ms
detected : 0.00295 ms
killed : 0.021594 ms
killed : 0.0563 ms
0
is_eq_ob : 0.241904 ms
のようになります。すなわち，0.00295 msという圧倒的な速度で検出しているのに，他の2つのスレッドの戻りが遅く，しかもその3つのスレッドの合計以上のオーバーヘッドが加わって，単純ループに負けているのがわかります。超高速で検出したスレッドの効用が活かせられません。