並列処理のためのC++ライブラリ拡張
～C++17: 並列STLの概要

　STLを多用したアプリケーションを可能な限り速く動作させる必要に迫られました。実験実装ではまずまずのスピードを叩き出してくれてたのですが、本番の稼働では思いのほか多量のデータを扱うことになりそうで、当初の想定より数割増し速くないとマズいことが判明しちゃいました。今以上に速くできるかコードを眺めてみたけれど、データ構造とアルゴリズムにはこれ以上の改善の余地がなさそうなんです。幸いなことに4coreのCPUを積んだマシンを使うとのことで、マルチスレッドによる高速化に望みを託すことになりました。

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は再実装の手間がバカにならんのです。