なぜマルチスレッドが遅いのですか？

Question

私は素数を見つけるプログラムを書こうとしています。このプロジェクトの本当の目的は、マルチスレッドについて学ぶことです。最初に私はシングルスレッドプログラムを書いて、1分で最大13,633,943を見つけました。私のマルチスレッド版は10,025,627にしかなりませんでした。

はここでシングルスレッドプログラム

#include <iostream> 

using namespace std; 

bool isprime(long num) 
{ 
    long lim = num/2; 
    if(num == 1) 
    { 
     return 0; 
    } 
    for(long i = 2; i <= lim; i++) 
    { 
     if (num % i == 0) 
     { 
      return 0; 
     } 
     else{ lim = num/i; } 
    } 
    return 1; 
} 

int main() 
{ 
    long lim; 
    cout << "How many numbers should I test: "; 
    cin >> lim; 
    for(long i = 1; i <= lim || lim == 0; i++) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
} 

ここに私のマルチスレッドプログラムのための私のコードがあるために私のコードです。

extern"C" 
{ 
    #include <pthread.h> 
    #include <unistd.h> 
} 
#include <iostream> 

using namespace std; 

bool isprime(long num); 
void * iter1(void * arg); 
void * iter2(void * arg); 
void * iter3(void * arg); 
void * iter4(void * arg); 


int main() 
{ 
    //long lim; 
    //cout << "How many numbers should I test: "; 
    //cin >> lim; 
    pthread_t t1; 
    char mem1[4096];//To avoid false sharing. Needed anywhere else? 
    pthread_t t2; 
    char mem2[4096];//These helped but did not solve problem. 
    pthread_t t3; 
    pthread_create(&t1, NULL, iter1, NULL); 
    pthread_create(&t2, NULL, iter2, NULL); 
    pthread_create(&t3, NULL, iter3, NULL); 
    iter4(0); 
} 

bool isprime(long num) 
{ 
    long lim = num/2; 
    if(num == 1) 
    { 
     return 0; 
    } 
    for(long i = 2; i <= lim; i++) 
    { 
     if (num % i == 0) 
     { 
      return 0; 
     } 
     else{ lim = num/i; } 
    } 
    return 1; 
} 

void * iter1(void * arg) 
{ 
    for(long i = 1;; i = i + 4) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
return 0; 
} 

void * iter2(void * arg) 
{ 
    for(long i = 2;; i = i + 4) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
return 0; 
} 

void * iter3(void * arg) 
{ 
    for(long i = 3;; i = i + 4) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
return 0; 
} 

void * iter4(void * arg) 
{ 
    for(long i = 4;; i = i + 4) 
    { 
     if(isprime(i)) 
     { 
      cout << i << endl; 
     } 
    } 
return 0; 
} 

特に私を混乱させる何かがシステムモニタは、シングルスレッドとマルチスレッドのための100％の使用率は25％のCPU使用率を報告していることです。それは4倍の計算をしているのではないでしょうか？

Answer 1

確かにcoutは共有リソースとして機能します。実際には各番号を正しく、適切な順序で印刷しても、非常に遅くなります。

私は同様のことをしました（より柔軟で、「次の数字を選ぶ」ために原子操作を使います）。そして、私のクワッドコアマシンではほぼ正確に4倍高速です。しかし、それは私が何も印刷しない場合だけです。コンソールに印刷すると、実際に計算するのではなく、シャッフルするのに多くの時間がかかりますので、処理時間が非常に遅くなります。

cout << i << endl;行をコメントアウトすると、はるかに高速に実行されます。

編集：印刷せずに

Single thread: 15.04s. 
Four threads: 11.25s 

：印刷して、私のテストプログラムを使用して

Single threads: 12.63s. 
Four threads: 3.69s. 

3.69 * 4 =の14.76sが、私のLinuxマシン上でtimeコマンドを示し、総12.792sランタイムなので、明らかに、すべてのスレッドが実行されていない時、または何らかのアカウンティングエラーが発生しています...

Answer 2

これは、コードが取得するCPUの数によって異なりますOSによって実行されるように与えられる。これらのスレッドのそれぞれはCPUバウンドですので、1つのCPUしかない場合は、あるスレッドを実行し、タイムスライスし、次のスレッドなどを実行します。これは遅くなく、遅くなる可能性がありますスレッドスワップのオーバーヘッドそして、ソラリスでは、少なくとも、すべてのスレッドを一度に実行したいと言っている間は、それは価値があります。

他のポスターで提案されているように、出力がシリアライズされている実装には触れていません。通常は、

235 iisi s ppprririimmme 
ee 

のように出力されるため、O/Sで複数のスレッドが割り当てられていない可能性があります。

もう1つの問題は、コンソールへの出力がファイルへの出力と比較して非常に遅いことです。あなたのプログラムからの出力をファイルに送り、その速さがどのように速くなるかを見る価値があるかもしれません。

Answer 3

私はOli Charlesworthがハイパースレッディングの問題で頭に打ったと信じています。ハイパースレッディングは実際には2つのコアを持つようなものだと思った。そうではありません。私は2つのスレッドだけを使用するように変更し、22,227,421に達しました。これは2倍の速度にかなり近くなっています。

Answer 4

@MatsPeterssonは（少なくともPOSIXベースのシステムのために、stdoutが共有リソースである）、彼はここにあなたが起こってからそれらの厄介なロックを排除することができる方法だ、修正その問題への道を提供していないが正しいですが。

POSIX Cはとまったく同じことをするが、ロックなし（驚き）の関数を定義している。putc_unlocked。との競合状態が存在することが、それは完全に可能であることを

void printint_unlocked(FILE *fptr, int i) { 
    static int digits[] = { 
     1, 
     10, 
     100, 
     1000, 
     10000, 
     100000, 
     1000000, 
     10000000, 
     100000000, 
     1000000000, 
    }; 

    if (i < 0) { 
     putc_unlocked('-', fptr); 
     i = -i; 
    } 

    int ndigits = (int) log10(i); 
    while (ndigits >= 0) { 
     int digit = (i/(digits[ndigits])) % 10; 

     putc_unlocked('0' + digit, fptr); 

     --ndigits; 
    } 
} 

注：その使用、そして、我々は、マルチスレッドのシナリオでより速くcoutまたはprintfをロックせずに整数を印刷し、そしてだろう私たち自身の関数を定義することができますこのメソッドは、出力に数値を衝突させます。アルゴリズムで衝突が発生しない場合でも、マルチスレッドコードのパフォーマンスを引き上げる必要があります。

最後の3つ目のオプションは、別のスレッドにイベントキューを作成し、そのスレッドからすべての印刷を行い、競合状態が発生せず、ロックの問題も発生しないようにすることですスレッド。

Answer 5

私は実際にマルチスレッド（素数を見つける）とノイズ（コンソールへの出力を書き込む時間）を埋め込むことができる部分を取っていることが多いと思います。

これにどれくらいの効果があるかを知るために、素数を見つけることから素数を分けて印刷することを少し書き直しました。簡単にタイミングを作るために、私もそれには、これを与えて、対話的にコマンドラインからの制限を取る代わりにしていた：

int main(int argc, char **argv) { 
    if (argc != 2) { 
     std::cerr << "Usage: bad_prime <limit:long>\n"; 
     return 1; 
    } 
    std::vector<unsigned long> primes; 

    unsigned long lim = atol(argv[1]); 

    clock_t start = clock(); 

    for(unsigned long i = 1; i <= lim; i++) 
     if(isprime(i)) 
      primes.push_back(i); 
    clock_t stop = clock(); 

    for (auto a : primes) 
     std::cout << a << "\t"; 

    std::err << "\nTime to find primes: " << double(stop-start)/CLOCKS_PER_SEC << "\n"; 
} 

素数自身の行数千人をスキップ、私はこのような結果が得られます。

Time to find primes: 0.588 


Real 48.206 
User 1.68481 
Sys  3.40082 

So - 素数を見つけるのにおよそ0.5秒、それらを印刷するのに47秒以上。実際に出力をコンソールに書き込むことを意図していると仮定すると、そこでは停止することもできます。マルチスレッドが素数を見つける時間を完全になくすことができたとしても、究極の時間を48.2秒から47.6秒に変更するだけで、価値があるとは思えません。

したがって、実際の目的はファイルのようなものに出力を書き込むことです。コードをマルチスレッド化する作業に行くのは無意味だが、各スレッドでひどく非効率なコードを実行するので、私はシングルスレッドのコードを起動時に最適化（または、少なくとも、デpessimize）すると思ったポイント。

まず、endlを削除し、"\n"に置き換えました。出力をファイルに転送すると、実行時間が0.968秒から0.678秒に短縮されました。つまり、endlは改行の書き込みに加えてバッファをフラッシュし、そのバッファフラッシングはプログラム全体の時間の約3分の1を占めていました。

同じ基準で、私は、少なくとも少し非効率的な何かにあなたのisprimeを書き換えるの自由を取った：これは確かに多くの改善（例えば、エラトステネスのふるい）に開かれている

bool isprime(unsigned long num) { 
    if (num == 2) 
     return true; 

    if(num == 1 || num % 2 == 0) 
     return false; 

    unsigned long lim = sqrt(num); 

    for(unsigned long i = 3; i <= lim; i+=2) 
     if (num % i == 0) 
      return false; 

    return true; 
} 

が、はシンプルで直感的で、約2〜3倍の速さです（上記の時間はあなたのものではなく、isprimeを使用することに基づいています）。

この時点では、プライムの発見をマルチスレッド化することは少なくとも意味を成す可能性があります。プライムの発見では0.6秒のうち約5秒をとりますが、スピードを2倍しかできない場合でも、全体的な時間の違い。

また、出力結果を素数から分離することで、マルチスレッド版のコードを書く上でより良い基盤が得られます。各スレッドがその結果を別のベクトルに書き込むと、coutなどでロックすることなく、意味のある（インタリーブされていない）出力を得ることができます - 各チャンクを別々に計算し、各ベクトルを順番に出力します。そのため

コードは次のようなものになります：

#include <iostream> 
#include <vector> 
#include <time.h> 
#include <math.h> 
#include <thread> 

using namespace std; 

bool isprime(unsigned long num) { 
    // same as above 
} 

typedef unsigned long UL; 

struct params { 
    unsigned long lower_lim; 
    unsigned long upper_lim; 
    std::vector<unsigned long> results; 

    params(UL l, UL u) : lower_lim(l), upper_lim(u) {} 
}; 

long thread_func(params *p) { 
    for (unsigned long i=p->lower_lim; i<p->upper_lim; i++) 
     if (isprime(i)) 
      p->results.push_back(i); 
    return 0; 
} 

int main(int argc, char **argv) { 
    if (argc != 2) { 
     std::cerr << "Usage: bad_prime <limit:long>\n"; 
     return 1; 
    } 

    unsigned long lim = atol(argv[1]); 

    params p[] = { 
     params(1, lim/4), 
     params(lim/4, lim/2), 
     params(lim/2, 3*lim/4), 
     params(3*lim/4, lim) 
    }; 

    std::thread threads[] = { 
     std::thread(thread_func, p), 
     std::thread(thread_func, p+1), 
     std::thread(thread_func, p+2), 
     std::thread(thread_func, p+3) 
    }; 

    for (int i=0; i<4; i++) { 
     threads[i].join(); 
     for (UL p : p[i].results) 
      std::cout << p << "\n"; 
    } 
} 

は以前と同じマシン上でこれを実行する（かなり古いデュアルコアプロセッサ）、私が取得：

Real 0.35 
User 0.639604 
Sys  0 

これはと思われます極端にをスケーリングしています。私たちが得たものがマルチコア計算であれば、素数が2で割り切れることを見いだすことができます（デュアルコアプロセッサでこれを実行しています）、ディスクにデータを書き込む時間は一定のままです（マルチスレッドではハードドライブを高速化することはできません）。それに基づいて、完全スケーリングはは0.59/2 + 0.1 = 0.40秒となるはずです。

私たちがそれを超えて見ているマイナーな改善は、スレッド1,2,3,4がまだ素数を見つけている間にスレッド1からディスクにデータを書き込むことができるという事実に起因する可能性が高い（同様に3と4がまだ計算している間にスレッド2からのデータの書き込みを開始し、スレッド4がまだ計算している間にスレッド3からデータを書き込む）。

私が見ている改善はタイミングが単純なノイズでも十分に小さいと付け加えなければならないと思います。しかし、私はシングルスレッドとマルチスレッドの両方のバージョンを何度も実行しましたが、どちらにもいくつかのバリエーションがありますが、マルチスレッドバージョンは、計算速度の向上が考慮に入れるよりも一貫して高速です。

私はこのことが全体的なスピードのどのくらいの違いがあるかを知るために、元のバージョンが1分で見つかった最大13,633,943までの素数を見つけるのにどれくらいの時間がかかるかを調べました。私はほぼ確実に低速のCPU（7歳のAthlon 64 X2 5200+）を使用していますが、このバージョンのコードは12.7秒で実行します。

最後に、少なくとも間違いなく共有するために挿入した詰め物を除外しました。私が得る時代に基づいて、彼らは必要（または有用）であるようには思われません。