データの分割による高速化
……ちっとも速くありませんね。僕の環境では8!=40320個のstringをソートするのに26秒ほどかかりました。この実装に改良を加え、インテルTBBによる並列化も使ってどれほど速くできるか試してみることにします。
選択ソートは単純なだけのことはあって、大量のデータをソートするにはまったく不向きです。時間計算量は要素数の2乗に比例するので要素数が2倍になれば処理時間は4倍になります。が、裏を返せば要素数を1/2にすれば処理時間は1/4になるわけですよね。ならば、要素数Nのデータを半分ずつに分け、それぞれを選択ソートすれば1/4の処理時間で2つソートするのだから、全体の処理時間を約半分にできるはずです。
問題となるのは要素数Nの元データを昇順に並べたときの上位N/2個と残りN/2個に分割することなのですが、STLにはちょうどおあつらえ向きのアルゴリズム nth_element が用意されています。
nth_element は引数にイテレータを3つ与えます。 nth_element(first, mid, last) によって、[first,mid)内の任意の要素は[mid,last)内のどの要素よりも大きくないよう、[first,last)内の要素を並び替えてくれます。これを使うと……
class ultra_sort : public sort_base {
public:
ultra_sort(iterator first, iterator last) : sort_base(first,last) {}
protected:
virtual void do_sort() const {
iterator mid = first_;
// mid は firstとlastの中間点
advance(mid, distance(first_,last_)/2);
nth_element(first_, mid, last_);
selection_sort(first_, mid);
selection_sort(mid, last_);
}
};
normal_sortの約2倍のスピードでソートしてくれます。
マルチスレッドでさらに2倍に
ultra_sortではソート対象であるvector<string>を前半部と後半部に分割し、それぞれを選択ソートしているわけですが、nth_elementによって前半部には上位N/2個、後半部には残りN/2個が振り分けられています。したがってソートの過程において前半部と後半部のそれぞれの要素が交換されることはありません。つまり、前半部/後半部のソートは完全に独立しており、マルチスレッドによる同時実行の際に排他制御を必要とせず、一方が他方を気にせずフルスピードで動けます。やってみましょう。
class super_sort : public sort_base {
public:
super_sort(iterator first, iterator last) : sort_base(first,last) {}
protected:
virtual void do_sort() const {
iterator mid = first_;
advance(mid, distance(first_,last_)/2);
nth_element(first_, mid, last_);
tbb::parallel_invoke(normal_sort(first_,mid), normal_sort(mid,last_));
}
};
インテルTBBが提供する並列アルゴリズムのひとつ parallel_invoke を使って2つの関数オブジェクトを同時に動かしています。これで元の normal_sort の約4倍のスピードになっています。パフォーマンス・メータを立ち上げておくと2つのコアがフル稼働している様子が観察できるでしょう。
インテルTBBでのタスク実行
Windows-APIやpthreadではスレッドを生成することができますが、これらが生成するのは論理スレッド（logical thread）です。これに対し、CPUが持ち合わせているスレッドが物理スレッド（physical thread）。物理スレッドの数だけ同時に実行可能です。
論理スレッドが物理スレッドより多い場合、論理スレッドの行う処理はぶつ切りにされ、ちょっと動いては別の論理スレッドに切り替えが行われます。論理スレッドの切り替えにはオーバヘッドを伴うため、多くの論理スレッドを起こすことはパフォーマンス的には得策ではありません。理想的には物理スレッド数と（動作可能な/休眠していない）論理スレッド数が同数であることが望まれます。
しかしそうなると論理スレッドの管理が難しくなります。スケーラビリティを狙うなら論理スレッド数をアプリケーション内で固定することはできません。いまやdual-core/quad-coreがアタリマエのご時世ですから、コア数に応じて論理スレッド数を適切に調整しないとCPU取り替えたのにちっとも速くならない!ことになってしまいます。
そこでインテルTBBは論理スレッドをプログラマに意識させないアプローチを採りました。生成される論理スレッドはライブラリ内部で管理され、プログラマは論理スレッド内で実行される小さな処理の断片「タスク」をタスクスケジューラーに与えます。タスクスケジューラーは与えられたタスクを論理スレッドに適切に割り当て実行します。
super_sortで用いたparallel_invokeは引数に与えられた関数オブジェクトそれぞれがタスクとして実行されます。parallel_invokeは最大10個の関数オブジェクトを与えることができますが、与えられた関数オブジェクトと同数の論理スレッドが生成されるわけではありません。論理スレッド数はシステムで使用可能な物理スレッド数に応じてインテルTBBが決定します。
