More than 3 years have passed since last update.

C++の並列ソート

Last updated at 2020-05-06Posted at 2020-05-06

https://qiita.com/dc1394/items/d2b8de600a304664cdb5 を読んで、 __gnu_parallel::sort が無いなと思って記事を書くことにした。

整列の仕方

整列アルゴリズムにはいろいろあるけど、ライブラリ提供者が普通これが速いんじゃないの、と思うものが、不安定ソートとしては std::sort という形で、安定ソートとしては std::stable_sort という形で提供されている。

でもそれは並列計算ができない場合の話。
並列計算ができる場合は、それを活かせばもっと速くなる。かもしれない。そして、今どきのコンピュータはだいたい並列計算できるようなハードウェアになっている。

並列計算を使った整列を実現する方法はいくつかあるんだけど、手軽なのは、 gcc 4.6.0 のころから存在していたらしい __gnu_parallel::sort 。というか、これしか知らなかった。

で。
この記事を書こうと調べていたら、C++17 で並列計算が標準でサポートされるようになったことを知った。

c++17

std::sort(first, last, comp);

などを、 #include <execution> とした上で、

c++17

std::sort(std::execution::par, first, last, comp);

などとすると並列計算になるらしい。すばらしい。 par の部分は下表の通り4通り。

ポリシー	マルチスレッド	ベクトル化	C++
`seq`	禁止	禁止	C++17以降
`par`	許可	禁止	C++17以降
`par_unseq`	許可	許可	C++17以降
`unseq`	禁止	許可	C++20以降

上記以外も処理系の気持ち次第で増えるかもしれないらしい。

処理時間を短くしたいならとりあえず par_unseq を指定しておけばいいかなという感じ。

とはいえ。手元の環境ではただ単に上記のように書けばいいわけではなく

$ brew install tbb

を実行しておく必要がある。リンクするライブラリとかも設定が必要。
TBB は、 Intel Threading Building Blocks のことらしい。

安定ソート、不安定ソートのそれぞれについて。
以下の5つの方法で、4種類のデータを整列した。データの件数は $2^{10}$〜$2^{20}$ とした。

※ unseq は C++20 以降のハズなんだけど、 -std=c++17 でも使えた。

名前	意味
random_uint32	$2^{32}$種類の値を持つ、ランダムな `std::uint32_t`
few_uint32<8>	8種類の値しか取れない、ランダムな `std::uint32_t`
random_string<1024>	すべての文字がランダムな英小文字の `std::string` 。長さは 1024文字。
few_strings<8, 1024>	8種類の値しか取れない、ランダムな `std::string` 。長さは 1024文字。

整列済みとかほぼ整列済みとか逆順とかいろいろ試そうかとも思ったけど、控えめにしてみた。

軸にラベル付け忘れた。
縦軸はミリ秒。整列1回に要する時間。
横軸はデータの件数。

マシンは MacBook Pro (Retina, 15-inch, Mid 2015)。クアッドコアIntel Core i7。

コンパイラは g++-9 (Homebrew GCC 9.3.0) 9.3.0。
コンパイルオプションは -march=native -O2 にした。

意外と gnu_parallel がふるわない。
uint32_t で件数が多いと gnu_parallel がやや速い。
それ以外では gnu_parallel は意外に遅い。特に、 uint32_t で件数が少ないと顕著。

std(par) と std(par_unseq) が速い。同じかなとも思う。
std(unseq) は std と同じかな。

件数が少ないと並列計算のメリットは少ない。特に gnu_parallel はかえって遅い。

不安定ソートと傾向は同じ。

ソースコードなどを https://github.com/nabetani/parallelsort においている。