再帰的なタスク実行
ソート対象を前半と後半の2つに分割し、それぞれをソートすることで高速化できました。ならば前半/後半をソートする際、それぞれをさらに2分割すればもっと速くなるでしょうね。これを繰り返せば少ない要素群をソートする多数のタスクが作られることになりますが、論理スレッド数が増えるわけではないのでスレッドの切り替えに要するオーバヘッドは気にしなくて済みそうです。parallel_invokeを再帰的に使いましょう。
class extremely_sort : public sort_base {
public:
typedef std::vector<std::string>::difference_type difference_type;
extremely_sort(iterator first, iterator last) : sort_base(first,last) {}
protected:
static difference_type cutoff_;
virtual void do_sort() const {
difference_type size = std::distance(first_,last_);
// そこそこ小さくなったら選択ソートに切り替え
if ( size < cutoff_ ) {
selection_sort(first_, last_);
} else {
iterator mid = first_;
std::advance(mid, size/2);
nth_element(first_, mid, last_);
tbb::parallel_invoke(extremely_sort(first_,mid), extremely_sort(mid,last_));
}
}
};
extremely_sort::difference_type extremely_sort::cutoff_ = 30;
筆者の環境でのここまでの各ソートの処理時間は以下のようになりました。
normal_sort ....... 26.0291 [sec] ultra_sort ........ 13.303 [sec] super_sort ........ 6.77076 [sec] extremely_sort .... 0.0596765 [sec]
再帰版 extremely_sort のスピードは normal_sort の実に436倍。2-coreでの測定結果ですから、4-core/8-core機であればさらに良い結果が得られることでしょう。
……実は2分割を再帰的に行った時点で選択ソートがクイックソートになっちゃってます。クイックソートの時間計算量は N・logN なので速いのはアッタリマエなのです。
再帰を使わない実装
インテルTBBでのプログラミングに慣れるべくチュートリアルドキュメントを読んでいて、parallel_do という一風変わった並列アルゴリズムを見つけました。さきほどの再帰parallel_invokeとは異なる実装を紹介しましょう。
parallel_invokeは複数の関数オブジェクトに同時に着火してそれらの完了を待つのに対し、parallel_doで着火される関数オブジェクトは1つだけ。1つの関数オブジェクトを（引数を取換えながら）何度も呼び出します。
parallel_doに与える引数は処理に与える要素列を示すための2つ（先頭と末尾）一組のイテレータ、そしてそれらイテレータが指す要素を引数として処理を行う関数オブジェクトです。
簡単な例を考えました。kitchen（中華料理屋の厨房）です。kitchenはお客から受けた注文に従って調理を行います。注文伝票の中には「○○定食」がいくつか混じっています。kitchenではたとえば「ギョーザ定食」という注文に対してはギョーザの調理にあわせて「白飯」と「スープ」の注文伝票を自分自身に追加発行することで「○○定食」を処理します。「○○定食」の処理 = ○○の調理 + 「白飯」と「スープ」の追加注文 ってことです。
#include <iostream>
#include <string>
#include <vector>
#include <tbb/tbb.h>
using namespace std;
// とある中華料理屋の厨房(キッチン)
class kitchen {
mutable tbb::mutex mutex_;
public:
void operator()(const string& order, tbb::parallel_do_feeder<string>& feeder) const {
string dish;
string::size_type pos = order.find("定食");
if ( pos != string::npos ) {
// ××定食だったら"白飯"と"スープ"を注文に加える
dish = order.substr(0,pos);
feeder.add("白飯(" + dish + ")");
feeder.add("スープ(" + dish + ")");
} else {
// 単品だったら調理開始
dish = order;
}
// 出力が乱れないようlockする
tbb::mutex::scoped_lock lock(mutex_);
cout << dish << endl;
}
};
int main() {
// オバちゃんが注文を取る
vector<string> orders;
orders.push_back("ラーメン");
orders.push_back("ギョーザ定食");
orders.push_back("ビール");
orders.push_back("レバニラ炒め定食");
// parallel_doを用い、厨房が注文をさばく
tbb::parallel_do( orders.begin(), orders.end(), kitchen());
}
レバニラ炒め ビール スープ(レバニラ炒め) ギョーザ 白飯(レバニラ炒め) スープ(ギョーザ) ラーメン 白飯(ギョーザ)
関数オブジェクトのoperator()の第2引数 parallel_do_feeder がキモ。こいつに新たな注文をaddすることでkitchen自らに対し追加注文できるわけです。
具体的にソートに適用したサンプルとして、記事添付ファイルに「selection_sort.cpp」を収録したので、実際に確めてみてください。
まとめ
インテルTBB、文句なく面白いです。Win32-threadやpthreadなどとは異なり、スレッドを意識せずにスケーラブルなマルチスレッド・アプリケーションが書けるのが魅力的です。インテルTBBによるマルチスレッドで遊んでみませんか?
