SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

特集記事

C++11 : スレッド・ライブラリひとめぐり

Visual Studio 2012 RC であそんでみたよ

  • X ポスト
  • このエントリーをはてなブックマークに追加

 C++11が提供するスレッド・ライブラリの使い心地を、Visual Studio 2012 RCでの試運転を兼ねてざっくりと体感してみましょう。

  • X ポスト
  • このエントリーをはてなブックマークに追加

 5月の末、Visual Studio 2012 RCがリリースされました。僕は根っからのC++屋ですから、興味の対象は第一にVisual C++ 2012(以下、VC11)です。現Visual C++ 2010(VC10)にはlambdaなどの国際標準C++11の一部をサポートしていますけど、VC11ではさらにC++のサポート範囲が広がっています。今回はVC++11で新たに追加された標準スレッド・ライブラリのご紹介です。

十万未満の素数はいくつある?

 「1とそれ自身以外の約数を持たない数」が素数です。言い換えれば「2以上n未満のすべての数でnを割り切ることができなければ、nは素数」ですわね。だからnが素数であるか否かを判定する関数はこんなカンジ。

リスト1
// nは素数?
bool is_prime(int n) {
  for ( int i = 2; i < n; ++i ) {
    if ( n % i == 0 ) {
      return false;
    }
  }
  return true;
}

 このis_primeを使って「lo以上hi未満の範囲にある素数の数」を求める関数count_primeは

リスト2
// lo以上hi未満の範囲に素数はいくつある?
int count_prime(int lo, int_hi) {
  int result = 0;
  for ( int i = lo; i < hi; ++i ) {
    if ( is_prime(i) ) {
      ++result;
    }
  }
  return result;
}

 10万未満の素数を勘定してみましょう。

リスト3
/* 
 * M未満の素数はいくつある?
 */
void single(int M) {
  chrono::system_clock::time_point start = chrono::system_clock::now();
  int result = count_prime(2,M);
  chrono::duration<double> sec = chrono::system_clock::now() - start;
  cout << result << ' ' << sec.count() << "[sec]" << endl;
}

int main() {
  const int M = 100000;
  single(M);
}

/* 実行結果:
9592 1.64009[sec]
*/

 10万までの整数には1割弱の素数があるんですねぇ。僕のマシン(i7-2600K、Windows7-64bit)では1.6秒ほどで答えを出してくれました。

0:Windows API

 この計算をマルチスレッドによる高速化を試みます。戦略はいたって単純、素数か否かの判定範囲、[2,M) (2以上M未満,M=100000)をスレッド数で等分します。たとえばスレッドふたつなら [2,M/2) と [M/2,M)に。んでもって各スレッドに分割された範囲での素数の勘定を分担させ、それぞれの結果を全部足し合わせればよかろう、と。

 まずはWindows APIで実装します。範囲[lo,hi)をn等分するクラスdiv_rangeを用意します。

リスト4 div_range.h
#ifndef DIV_RANGE_H_
#define DIV_RANGE_H_

// [lo,hi) を n等分する
template<typename T =int>
class div_range {
private:
  T lo_;
  T hi_;
  T stride_;
  int n_;
public:
  div_range(T lo, T hi, int n) 
    : lo_(lo), hi_(hi), n_(n) { stride_ = (hi-lo)/n; }
  T lo(int n) const { return lo_ + stride_ * n; }
  T hi(int n) const { return (++n < n_) ? lo_ + stride_*n : hi_; }
};
#endif

 分割された範囲ごとにスレッドを起こし、全スレッドが完了したところで積算します。

リスト5
/* Win32 thread のためのwrapper */

// <0>:loi, <1>:hi , <1>:result
typedef tuple<int,int,int> thread_io;

DWORD WINAPI thread_entry(LPVOID argv) {
  thread_io& io = *static_cast<thread_io*>(argv);
  get<2>(io) = count_prime(get<0>(io), get<1>(io));
  return 0;
}

/* 
 * M未満の素数はいくつある?
 */
void multi(int M, int nthr) {
  vector<HANDLE> handle(nthr);
  vector<thread_io> io(nthr);
  div_range<> rng(2,M,nthr);

  for ( int i = 0; i< nthr; ++i ) {
    io[i] = thread_io(rng.lo(i), rng.hi(i), 0);
  }

  chrono::system_clock::time_point start = chrono::system_clock::now();
  for ( int i = 0; i< nthr; ++i ) {
    handle[i] = CreateThread(NULL, 0, &thread_entry, &io[i], 0, NULL);
  }
  WaitForMultipleObjects(nthr, &handle[0], TRUE, INFINITE);
  chrono::duration<double> sec = chrono::system_clock::now() - start;

  int result = 0;
  for ( int i = 0; i < nthr; ++i ) {
    CloseHandle(handle[i]);
    result += get<2>(io[i]);
  }
  cout << result << ' ' << sec.count() << "[sec] : " << nthr << endl;
}

int main() {
  const int M = 100000;
  for ( int i = 1; i < 10; ++i ) multi(M, i);
}

/* 実行結果:
9592 1.6651[sec] : 1
9592 1.21607[sec] : 2
9592 0.970055[sec] : 3
9592 0.752043[sec] : 4
9592 0.631036[sec] : 5
9592 0.52903[sec] : 6
9592 0.549031[sec] : 7
9592 0.497028[sec] : 8
9592 0.470027[sec] : 9
*/

 スレッド数1~9で実行すると、8個の論理コアを持つi7では当然のことながらスレッド8個あたりでスピード頭打ちとなります。3倍ちょっと速くなってますね。Window-APIで実装する場合、スレッドの本体であるcount_primeをスレッドに乗っけるためのwrapper(このサンプルではthread_ioとthread_entry)が必要になります。

会員登録無料すると、続きをお読みいただけます

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

次のページ
1:thread

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
特集記事連載記事一覧

もっと読む

この記事の著者

επιστημη(エピステーメー)

C++に首まで浸かったプログラマ。Microsoft MVP, Visual C++ (2004.01~2018.06) "だった"りわんくま同盟でたまにセッションスピーカやったり中国茶淹れてにわか茶...

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/6639 2012/06/29 14:00

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング