ネタ元 → [勉強会]セッション資料公開
かたっぱしからportしていただきました。ありがとさんすー
本業でJava漬けなもんだから休日はC++、TBBのthreadとtaskで遊ぶよ♪
インテルTBBによる選択ソートの高速化 では tbb::parallel_invoke で
ソート範囲の前半部/後半部を同時並行実行したです。
これを フツーにスレッド使ってやってみる。 つまりこの:
ソートする(こっから, ここまで) {
こっから と ここまで を前半部[こっから..まんなか] と [まんなか..ここまで] に分割する。
スレッド起こして ソートする(こっから, まんなか)
スレッド起こして ソートする(まんなか, ここまで)
スレッドの完了を待つ
}
なんてな。
TBBには parallel_なんとか 関数が提供されてて、大抵の用途にはこいつらで事足ります。
が、parallel_なんとか では済まないケースもございます。TBBにはstd::threadコンパチのthread
があるんで、(この例ではparallel_invokeで書けるんだけども)thread使うとこんなコードになるです。
/*
* 前半部/後半部に分け、それぞれをthreadでsortする
*/
void sort_thread_entry(vector<string>::iterator first, vector<string>::iterator last) {
typedef vector<string>::difference_type difference_type;
difference_type size = distance(first,last);
// 要素数が cutoff 未満なら素直にselection_sort
if ( size < cutoff ) {
selection_sort(first, last);
} // さもなくば
else {
vector<string>::iterator mid = first;
advance(mid, size/2);
// [first,mid) : 小さい要素群 と [mid,last) : 大きい要素群 に振り分けて
nth_element(first, mid, last);
// それぞれをソートするthreadを作り
thread lo(&sort_thread_entry, first, mid);
thread hi(&sort_thread_entry, mid, last);
// 双方の完了を待つ
lo.join();
hi.join();
}
}
...あのね、こんなことやっちゃダメですよ。
いやダメってことはないけど何事も限度てーもんがあって、こんなことしたら山ほどスレッド起こすことになります。
僕の環境では8!(40320)個の要素をソートしようとしたらば 32bit ではリソース枯渇して落ちてしまいました。
加えてこのコード、決して性能よくないんです。std::sortと比べてみたらば:
quick sort ... 0.130405 [sec]
sort_thread ... 0.63766 [sec]
2コア使ってるクセしてstd::sortに負けてます。
たくさんのスレッドを起こすことになり、
スレッドの切り替えにかかるオーバヘッドがバカにならんのでしょう。
実際TBBのマニュアルには:
Threads are heavy weight entities on most systems, and running too many threads on
a system can seriously degrade performance. Consider using a task based solution
instead if practical.
ぶっちゃけthreadは重いしさ、よぉけthread起こすとパフォーマンス低下がシャレならんのよ。
んだから実務ではtask-baseにしとき。悪いこと言わんから。
と明記されちょるです。
parallel_なんとかが使えないなら次善の策はtask使え。万策尽きたらthreadに手を伸ばしてもいい、と。
んじゃそのtask-baseゆーのんを使ってみると、だ。
quick sort ... 0.130405 [sec]
selection_sort ... 39.5528 [sec]
sort_thread ... 0.63766 [sec]
sort_task ... 0.0860738 [sec]
ってことで std::sort に勝つるです。4コア/8コアならもっと速くなるはずっす。
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
#include <cassert>
#include <tbb/tbb.h>
#include <tbb/compat/thread> // std::thread の TBBによる実装
using namespace std;
// 単純選択ソート
template<typename InputIterator>
void selection_sort(InputIterator first, InputIterator last) {
while ( first != last ) {
iter_swap(first, min_element(first,last));
++first;
}
}
static const int cutoff = 30;
/*
* 前半部/後半部に分け、それぞれをthreadでsortする
*/
void sort_thread_entry(vector<string>::iterator first, vector<string>::iterator last) {
typedef vector<string>::difference_type difference_type;
difference_type size = distance(first,last);
// 要素数が cutoff 未満なら素直にselection_sort
if ( size < cutoff ) {
selection_sort(first, last);
} // さもなくば
else {
vector<string>::iterator mid = first;
advance(mid, size/2);
// [first,mid) : 小さい要素群 と [mid,last) : 大きい要素群 に振り分けて
nth_element(first, mid, last);
// それぞれをソートするthreadを作り
thread lo(&sort_thread_entry, first, mid);
thread hi(&sort_thread_entry, mid, last);
// 双方の完了を待つ
lo.join();
hi.join();
}
}
/*
* 前半部/後半部に分け、それぞれをtaskでsortする
*/
class sort_task : public tbb::task {
public:
typedef vector<string>::iterator iterator;
typedef vector<string>::difference_type difference_type;
protected:
iterator first;
iterator last;
public:
sort_task(iterator f, iterator l) : first(f), last(l) {}
task* execute() {
difference_type size = distance(first,last);
// 要素数が cutoff 未満なら素直にselection_sort
if ( size < cutoff ) {
selection_sort(first, last);
} // さもなくば
else {
iterator mid = first;
advance(mid, size/2);
// [first,mid) : 小さい要素群 と [mid,last) : 大きい要素群 に振り分けて
nth_element(first, mid, last);
// それぞれをソートするtaskを作り
task* left_task = new( allocate_child() ) sort_task(first, mid);
task* right_task = new( allocate_child() ) sort_task(mid, last);
// 双方を起動して完了を待つ
set_ref_count(3);
spawn(*left_task);
spawn_and_wait_for_all(*right_task);
}
return 0;
}
};
int main() {
vector<string> source;
{
string value = "ABCDEFGH";
do {
source.push_back(value);
} while ( next_permutation(value.begin(), value.end()) );
assert( is_sorted(source.begin(), source.end()) );
random_shuffle(source.begin(), source.end());
}
{
cout << "quick sort ... " << flush;
vector<string> input = source;
tbb::tick_count t = tbb::tick_count::now();
sort(input.begin(), input.end());
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
{
cout << "selection_sort ... " << flush;
vector<string> input = source;
tbb::tick_count t = tbb::tick_count::now();
selection_sort( input.begin(), input.end());
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
{
cout << "sort_thread ... " << flush;
vector<string> input = source;
tbb::tick_count t = tbb::tick_count::now();
thread sort_th(&sort_thread_entry, input.begin(), input.end());
sort_th.join();
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
{
cout << "sort_task ... " << flush;
vector<string> input = source;
tbb::task* tsk = new(tbb::task::allocate_root()) sort_task(input.begin(), input.end());
tbb::tick_count t = tbb::tick_count::now();
tbb::task::spawn_root_and_wait(*tsk);
cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
assert( is_sorted(input.begin(), input.end()) );
}
}