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が素数であるか否かを判定する関数はこんなカンジ。
// 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は
// 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万未満の素数を勘定してみましょう。
/*
* 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万までの整数には１割弱の素数があるんですねぇ。僕のマシン（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を用意します。
#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
分割された範囲ごとにスレッドを起こし、全スレッドが完了したところで積算します。
/* 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）が必要になります。
