Shoeisha Technology Media

CodeZine(コードジン)

特集ページ一覧

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

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

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2012/06/29 14:00

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

目次

 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)が必要になります。


  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

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

    C++に首まで浸かったプログラマ。 Microsoft MVP, Visual C++ (2004.01~2018.06) "だった"り わんくま同盟でたまにセッションスピーカやったり 中国茶淹れてにわか茶人を気取ってたり、 あと Facebook とか。 著書: - STL標準...

All contents copyright © 2005-2019 Shoeisha Co., Ltd. All rights reserved. ver.1.5