C++11の標準ライブラリ<thread>を使った並列化
大量のデータを分割し、複数のスレッドに分担させて処理時間を稼ぐことを考えます。スレッドに関わるAPIは、WindowsならCreateThreadやWaitForNltipleObjectなど、Linuxならpthread_xxxxと、OSによって異なるのですが、C++11では標準ライブラリ<thread>がOSごとの差異を吸収してくれているのが嬉しいところ。大量のデータを詰め込んだvectorを2つのスレッドでソートしてみます。
list01 sort_thread.cpp
#include <iostream> // cout, endl
#include <thread> // thread
#include <algorithm> // inplace_merge, etc.
#include <chrono> // clock, time_point, duration
#include <iterator> // advecnce, distance
#include <vector> // vector
#include <numeric> // iota
#include <cassert> // assert
using namespace std;
template<typename Iterator>
void faster_sort(Iterator first, Iterator last) {
// mid : first と last の中間地点
Iterator mid = first;
advance(mid, distance(first, last)/2);
// シーケンスの前半(first～mid)を子スレッドでsort
thread thr(&sort<Iterator>, first, mid);
// 後半(mid～last)は自スレッドでsort
sort(mid, last);
// 子スレッドの完了を待って
thr.join();
// 前半と後半をマージする
inplace_merge(first, mid, last);
}
// 関数fの実行時間を計測する
template<typename Function>
void measure(Function f) {
using namespace std::chrono;
auto start = high_resolution_clock::now();
f();
auto stop = high_resolution_clock::now();
std::cout << duration_cast<microseconds>(stop - start).count() << std::endl;
}
int main() {
const int N = 4000000;
vector<int> data(N);
iota(begin(data), end(data), 0);
reverse(begin(data), end(data));
cout << "std::sort ";
measure([&]() { sort(begin(data), end(data)); });
assert( is_sorted(begin(data), end(data)) );
reverse(begin(data), end(data));
cout << "faster_sort ";
measure([&]() { faster_sort(begin(data), end(data)); });
assert( is_sorted(begin(data), end(data)) );
}
データの半分を子スレッドに任せたところ処理スピードは数割増し、まずまずの結果です。しかしながら、このやり方には少々不満が残ります。
第一にはスケーラビリティに欠けること。データを親子2つのスレッドに分担させていて、同時に処理しているスレッド数は2に固定されていますから、リッチなマシンに乗せ換えてもCPUのコア数に応じて速くなってはくれんのです。
スケーラブルなマルチスレッド・ライブラリの利用
スケーラブルなマルチスレッド・ライブラリには、例えばIntel TBB（Treading Building Blocks）、あるいはVisual C++に付属するPPL（Parallel Pattern Library）などがあります。PPLのソート関数:parallel_sortを使ってみると：
list02 sort_PPL.cpp
#include <ppl.h> // parallel_sort
#include <iostream> // cout, endl
#include <chrono> // clock, time_point, duration
#include <vector> // vector
#include <array> // array;
#include <numeric> // iota
using namespace std;
// 関数fの実行時間を計測する
template<typename Function>
void measure(Function f) { /* 省略 */ }
int main() {
const int N = 4000000;
vector<int> data(N);
iota(begin(data), end(data), 0);
reverse(begin(data), end(data));
cout << "std::sort: ";
measure([&]() { sort(begin(data), end(data)); });
reverse(begin(data), end(data));
cout << "parallel_sort: ";
measure([&]() { concurrency::parallel_sort(begin(data), end(data)); });
}
論理コア8つとなると流石に速いですね。
それじゃ現コードをPPLで再実装して、めでたしめでたしかというとさにあらず、PPLが用意してくれている並列アルゴリズムは：
- parallel_for
- parallel_for_each
- parallel_invoke
- parallel_transform
- parallel_reduce
- parallel_sort
- parallel_buffered_sort
- parallel_radixsort
……10個にも満たない。STL <algorithm>のアルゴリズム群に比べれるとおハナシにならんくらいに少ないので、PPLは再実装の手間がバカにならんのです。