C++
AdventCalendar
並列処理
ソート
C++17
C++Day 16

C++17時代の並列ソート


はじめに

この記事は、C++ Advent Calendar 2017 16日目の記事です。この記事では、C++17時代の並列ソートについて考えます。

2018年7月19日追記

Twitterにて、@yohhyさんが、以下のようにツイートされていました。確かに、Intel C++ Compiler (ICC)及びそのParallelism TSの実装が優秀である可能性は棄却できなかったので、内容を大幅に書き換えました。std::threadについては、良い方法が思いつかなかったのでそのままです…。


並列ソートとは

高速なソートアルゴリズムとしては、例えばクイックソートがよく知られています(他にも、マージソートやヒープソートが、高速なソートのアルゴリズムとして知られています)。クイックソートでは、ソート対象の配列の要素数を$ N $とすると、ソート時間のオーダーは(ランダウの記号を使って)、$ O(N\log N) $と書けます(ただし、最悪の場合は$ O(N^{2}) $になります)。

クイックソートは、十二分に高速なアルゴリズムであり、残念ながら、これ以上高速なソートアルゴリズムの発明はあまり望めそうにもありません(仮に、クイックソート以上に高速なソートアルゴリズムが開発されたとしても、ソート時間のオーダーは$ O(N) $未満にはならないと思います)。

従って、ソートの高速化を行うには、マルチコアを使った、クイックソートのスレッド並列化が有効でしょう。昨今のCPUには、少なくとも2個以上のCPUコアが内蔵されており、これを活用しない手はありません。

なお、クイックソートは不安定ソートであることに注意が必要です。高速な安定ソートが必要な場合は、例えばマージソートをスレッド並列化する必要があるでしょう。マージソートのスレッド並列化については、C++17時代の並列安定ソートという記事にまとめました。


通常のクイックソート

クイックソートのスレッド並列化を考える前に、まず通常のクイックソートの実装について触れておきます。クイックソートの詳細な解説は他に譲りますが(例えば参考サイト[1])、例えばクイックソートの(再帰を使わない)実装は、以下のコードのようになります。再帰を使わないのは、再帰が深くなりすぎて、スタックがオーバーフローすることを避けるためです。なお、以下のコードは、参考サイト[1]および参考サイト[2]に載っているコードを参考にさせて頂きました。

template < class RandomIter >

//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする
\param first 範囲の下限
\param last 範囲の上限
*/

void quick_sort(RandomIter first, RandomIter last)
{
using mypair = std::pair< RandomIter, RandomIter >;

// 範囲の情報を格納するスタック
std::stack< mypair, std::vector< mypair > > stack;

// 範囲の上限と下限をスタックへ積む
stack.push(std::make_pair(first, last - 1));

// スタックが空になるまで繰り返す
while (!stack.empty()) {
// 範囲の情報をスタックから取り出す
// C++17の構造化束縛を使いたいが
// Intel C++ Compiler 18.0は未だに構造化束縛をサポートしていない
RandomIter left, right;
std::tie(left, right) = stack.top();
stack.pop();

auto i = left;
auto j = right;
auto const pivot = (*left + *right) / 2;

// 左右から進めてきたiとjがぶつかるまでループ
while (i <= j) {
// 基準値以上の値が見つかるまで右方向へ進めていく
while (*i < pivot) {
++i;
}

// 基準値以下の値が見つかるまで左方向へ進めていく
while (*j > pivot) {
--j;
}

// 左右から進めてきたiとjがぶつかったら
if (i <= j) {
// 基準値位置よりも左側にあり、基準値よりも大きい値と、
// 基準値位置よりも右側にあり、基準値よりも小さい値の
// 位置関係を交換する。
std::iter_swap(i, j);

// 次回に備えて、注目点をずらす
++i;

// 境界チェック
if (j != first) {
// 次回に備えて、注目点をずらす
--j;
}
}
}

// 左右の配列のうち、要素数が少ない方を先に処理する
// 後で処理する側は、その範囲をスタックへ積んでおく
if (left < j) {
// 右側の配列を次のソート処理の対象にする
stack.push(std::make_pair(left, j));
}

if (i < right) {
// 左側の配列を次のソート処理の対象にする
stack.push(std::make_pair(i, right));
}
}
}


並列クイックソートの実装

以下で、このクイックソートのコードのスレッド並列化を、C++11標準のstd::threadを使った場合、OpenMPを使った場合、Intel® Threading Building Blocks (Intel® TBB)を使った場合、Intel® Cilk™ Plusを使った場合のそれぞれについて試してみたいと思います(クイックソートは、再帰処理を別スレッドで実行することで、簡単にスレッド並列化できます)。また、Intel® TBBに含まれるtbb::parallel_sortや、C++17のParallelism TSによるstd::sortにも触れたいと思います。


クイックソートのC++11標準のstd::threadによるスレッド並列化

まず、C++11標準に含まれるstd::threadを使ったスレッド並列化(以下では単にstd::threadと呼びます)を試してみましょう。C++11標準の機能なので、当然ながらC++11に対応しているコンパイラでないとこの方法は使えません。コードは以下のようになります(なおこのコードは、参考サイト[3]に載っているコードを参考にさせて頂きました)。

template < class RandomIter >

//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする(std::threadで並列化)
\param first 範囲の下限
\param last 範囲の上限
*/

inline void quick_sort_thread(RandomIter first, RandomIter last)
{
// 再帰ありの並列クイックソートの関数を呼び出す
quick_sort_thread(first, last, 0);
}

template < class RandomIter >
//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする(std::threadで並列化)
\param first 範囲の下限
\param last 範囲の上限
\param reci 現在の再帰の深さ
*/

void quick_sort_thread(RandomIter first, RandomIter last, std::int32_t reci)
{
// 部分ソートの要素数
auto const num = std::distance(first, last);

if (num <= 1) {
// 部分ソートの要素数が1個以下なら何もすることはない
return;
}

// 再帰の深さ + 1
reci++;

// 部分ソートが小さくなりすぎるとシリアル実行のほうが効率が良くなるため
// 部分ソートの要素数が閾値以上の時だけ再帰させる
// かつ、現在の再帰の深さが物理コア数以下のときだけ再帰させる
if (num >= THRESHOLD && reci <= NUMPHYSICALCORE) {
// 交点まで左右から入れ替えして交点を探す
auto const middle = std::partition(first + 1, last, [first](auto n) { return n < *first; });

// 交点 - 1の位置
auto const mid = middle - 1;

// 交点を移動
std::iter_swap(first, mid);

// 下部をソート(別スレッドで実行)
auto th1 = std::thread([first, mid, reci]() { quick_sort_thread(first, mid, reci); });

// 上部をソート(別スレッドで実行)
auto th2 = std::thread([middle, last, reci]() { quick_sort_thread(middle, last, reci); });

// 二つのスレッドの終了を待機
th1.join();
th2.join();
}
else {
// 再帰なしのクイックソートの関数を呼び出す
quick_sort(first, last);
}
}

上記コードの通り、部分ソートの要素数が閾値(上記コードにおけるTHRESHOLD)以上の時かつ、現在の再帰の深さが物理コア数(上記のコードのNUMPHYSICALCORE)以下の時だけ、別スレッドで自分自身を呼び出して再帰させます(もしそうでなければ、再帰なしの通常のクイックソートの関数を呼び出します)。この閾値については議論の余地があると思うのですが、ここでは深入りせず、500に固定しておきます。また、「現在の再帰の深さが物理コア数以下の時だけ再帰させる」という点には根拠があり、物理コア数(SMTの有無は関係ないようです)が異なる2台のPCで試行錯誤した結果、こうすると最もパフォーマンスが良くなることが分かりました。


クイックソートのOpenMPによるスレッド並列化

次に、OpenMPを使ったスレッド並列化を試してみましょう。OpenMPは、並列コンピューティング用のC/C++(とFortran)の言語拡張であり、gcc、MSVC、Clang、ICC (ICL)と言った主要なコンパイラで広く利用できます。コードは以下のようになりますが、注意すべきは、task指示句とtaskwait指示句を使っている点です。これはOpenMP 3.0で追加されたキーワードであり、従ってOpenMP 2.0までしかサポートしていないMSVCではコンパイルできません(最新のVisual Studio 2017でも同じです)。なおこのコードは、参考サイト[3]および参考文献[1]に載っているコードを参考にさせて頂きました)。

template < class RandomIter >

//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする(OpenMPで並列化)
\param first 範囲の下限
\param last 範囲の上限
*/

inline void quick_sort_openmp(RandomIter first, RandomIter last)
{
#pragma omp parallel // OpenMP並列領域の始まり
#pragma omp single // task句はsingle領域で実行
// 再帰ありの並列クイックソートを呼び出す
quick_sort_openmp(first, last, 0);
}

template < class RandomIter >
//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする(OpenMPで並列化)
\param first 範囲の下限
\param last 範囲の上限
\param reci 現在の再帰の深さ
*/

void quick_sort_openmp(RandomIter first, RandomIter last, std::int32_t reci)
{
// 部分ソートの要素数
auto const num = std::distance(first, last);

if (num <= 1) {
// 部分ソートの要素数が1個以下なら何もすることはない
return;
}

// 再帰の深さ + 1
reci++;

// 部分ソートが小さくなりすぎるとシリアル実行のほうが効率が良くなるため
// 部分ソートの要素数が閾値以上の時だけ再帰させる
// かつ、現在の再帰の深さが物理コア数以下のときだけ再帰させる
if (num >= THRESHOLD && reci <= NUMPHYSICALCORE) {
// 交点まで左右から入れ替えして交点を探す
auto const middle = std::partition(first + 1, last, [first](auto n) { return n < *first; });

// 交点 - 1の位置
auto const mid = middle - 1;

// 交点を移動
std::iter_swap(first, mid);

// 次の関数をタスクとして実行
#pragma omp task
// 下部をソート
quick_sort_openmp(first, mid, reci);

// 次の関数をタスクとして実行
#pragma omp task
// 上部をソート
quick_sort_openmp(middle, last, reci);

// 二つのタスクの終了を待機
#pragma omp taskwait
}
else {
// 再帰なしのクイックソートの関数を呼び出す
quick_sort(first, last);
}
}

上記コードのように、std::threadを使った場合より若干複雑になっていますが、やっていることは全く同じです。注意すべきことは、parallel指示句とsingle指示句を、void quick_sort_openmp(RandomIter first, RandomIter last)関数で記述していることです(void quick_sort_openmp(RandomIter first, RandomIter last, std::int32_t reci)関数内にparallel指示句とsingle指示句を記述すると、タスクのキュー管理のためオーバーヘッドが生じます)。


クイックソートのIntel® TBBによるスレッド並列化

次に、Intel® TBB(以下では単にTBBと呼ぶことにします)を使ったスレッド並列化を試してみましょう。TBBは、Intelが公開しているマルチスレッド対応のC++テンプレートライブラリであり、gcc、MSVC、Clang、ICC (ICL)といった主要なコンパイラで利用できます。ただし、gcc 5.4では、TBBのリンクに必要なlibtbbというライブラリが上手くリンクできないようです(gcc 7.3でも同様です)。コードは以下のようになります(なおこのコードは、参考サイト[3]に載っているコードを参考にさせて頂きました)。

template < class RandomIter >

//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする(TBBで並列化)
\param first 範囲の下限
\param last 範囲の上限
*/

inline void quick_sort_tbb(RandomIter first, RandomIter last)
{
// 再帰ありの並列クイックソートの関数を呼び出す
quick_sort_tbb(first, last, 0);
}

template < class RandomIter >
//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする(TBBで並列化)
\param first 範囲の下限
\param last 範囲の上限
\param reci 現在の再帰の深さ
*/

void quick_sort_tbb(RandomIter first, RandomIter last, std::int32_t reci)
{
// 部分ソートの要素数
auto const num = std::distance(first, last);

if (num <= 1) {
// 部分ソートの要素数が1個以下なら何もすることはない
return;
}

// 再帰の深さ + 1
reci++;

// 部分ソートが小さくなりすぎるとシリアル実行のほうが効率が良くなるため
// 部分ソートの要素数が閾値以上の時だけ再帰させる
// かつ、現在の再帰の深さが物理コア数以下のときだけ再帰させる
if (num >= THRESHOLD && reci <= NUMPHYSICALCORE) {
// 交点まで左右から入れ替えして交点を探す
auto const middle = std::partition(first + 1, last, [first](auto n) { return n < *first; });

// 交点 - 1の位置
auto const mid = middle - 1;

// 交点を移動
std::iter_swap(first, mid);

// 二つのラムダ式を別スレッドで実行
tbb::parallel_invoke(
// 下部をソート
[first, mid, reci]() { quick_sort_tbb(first, mid, reci); },
// 上部をソート
[middle, last, reci]() { quick_sort_tbb(middle, last, reci); });
}
else {
// 再帰なしのクイックソートの関数を呼び出す
quick_sort(first, last);
}
}

上記コードのように、std::threadを使った場合や、OpenMPを使った場合より簡潔に記述できています(やっていることはやはり全く同じです)。なお、tbb/parallel_invokeを使っているので、<tbb/parallel_invoke.h>のインクルードが必要です。


クイックソートのIntel® Cilk™ Plusによるスレッド並列化

次に、Intel® Cilk™ Plus(以下では単にCilkと呼ぶことにします)を使ったスレッド並列化を試してみましょう。Cilkは、Intelによる並列コンピューティング用のC/C++言語拡張であり、gcc 5以降とICC (ICL)で利用できます(MSVCでは利用できません。Clangでも利用できませんが、Cilk Plus/LLVMというプロジェクトがあります)。なお残念ながら、Intel自身によってCilkは非推奨(deprecated)とされてしまったため、将来のICCのバージョンでは、Cilkはサポートが打ち切られることが発表されています(また、gcc 8でもCilkのサポートは打ち切られてしまいました)。コードは以下のようになります(なおこのコードは、参考サイト[4]および参考文献[1]に載っているコードを参考にさせて頂きました)。

template < class RandomIter >

//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする(Cilkで並列化)
\param first 範囲の下限
\param last 範囲の上限
*/

inline void quick_sort_cilk(RandomIter first, RandomIter last)
{
// 再帰ありの並列クイックソートの関数を呼び出す
quick_sort_cilk(first, last, 0);
}

template < class RandomIter >
//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする(Cilkで並列化)
\param first 範囲の下限
\param last 範囲の上限
\param reci 現在の再帰の深さ
*/

void quick_sort_cilk(RandomIter first, RandomIter last, std::int32_t reci)
{
// 部分ソートの要素数
auto const num = std::distance(first, last);

if (num <= 1) {
// 部分ソートの要素数が1個以下なら何もすることはない
return;
}

// 再帰の深さ + 1
reci++;

// 部分ソートが小さくなりすぎるとシリアル実行のほうが効率が良くなるため
// 部分ソートの要素数が閾値以上の時だけ再帰させる
// かつ、現在の再帰の深さが物理コア数以下のときだけ再帰させる
if (num >= THRESHOLD && reci <= NUMPHYSICALCORE) {
// 交点まで左右から入れ替えして交点を探す
auto const middle = std::partition(first + 1, last, [first](auto n) { return n < *first; });

// 交点 - 1の位置
auto const mid = middle - 1;

// 交点を移動
std::iter_swap(first, mid);

// 下部をソート(別スレッドで実行)
cilk_spawn quick_sort_cilk(first, mid, reci);

// 上部をソート(別スレッドで実行)
cilk_spawn quick_sort_cilk(middle, last, reci);

// 二つのスレッドの終了を待機
cilk_sync;
}
else {
// 再帰なしのクイックソートの関数を呼び出す
quick_sort(first, last);
}
}

上記コードのように、TBBを使った場合と同様、簡潔に記述できています(やっていることはやはり全く同じです)。なお、cilk_spawnや、cilk_syncキーワードを利用するためには、<cilk/cilk.h>のインクルードが必要です。


TBBのtbb::parallel_sortを使った並列ソート

TBBには、tbb::parallel_sortという、スレッド並列化されたソート関数が含まれています。関数tbb::parallel_sortは、<tbb/parallel_sort.h>で、以下のように宣言されています(従って、tbb::parallel_sortを使用するには、<tbb/parallel_sort.h>のインクルードが必要です)。


  1. void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)

  2. void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp)

  3. void parallel_sort(Range& rng)

  4. void parallel_sort(const Range& rng)

  5. void parallel_sort(Range& rng, const Compare& comp)

  6. void parallel_sort(const Range& rng, const Compare& comp)

1個目および2個目のオーバーロードは、C++標準のSTLのstd::sort関数と全く同じ引数を取るので、それと同様に使用することができます。3個目から6個目のオーバーロードは、Boost.Range Algorithmsのboost::sort関数と同様であり、引数にコンテナを直接渡すことができます。なお、tbb::parallel_sortは、内部でクイックソートを用いているため、不安定ソートであることに注意が必要です。


C++17のParallelism TSによるstd::sortを使った並列化ソート

C++17から、並列アルゴリズムライブラリ(Parallelism TS)がC++標準のSTLに実装され、並列STLが利用可能になりました。Parallelism TSの解説は他に譲りますが(例えば参考サイト[5])、例えばstd::sortをスレッド並列化して実行するには、以下のコードのように記述します。

std::vector<int> v(1000000);

// std::sortをスレッド並列化して実行する
std::sort(std::execution::par, v.begin(), v.end());

2018年7月19日現在、Parallelism TSをサポートしているコンパイラは、Intel C++ Compiler 18.0と、Microsoft Visual C++ (MSVC) 14.14 (Visual Studio 2017 version 15.7.3)のみです(ただし、Intel C++ Compiler 18.0では、Parallelism TSの利用に、<pstl/algorithm><pstl/execution>という、非標準のヘッダファイルをインクルードする必要があります。同様にMSVC 14.14でも、Parallelism TSの利用には、<execution>という、非標準のヘッダファイルのインクルードが必要です)。しかし、実はIntel C++ Compiler 18.0におけるParallelism TSの実装は、Parallel STLという名称でGitHubにてオープンソースで公開されている(ライセンスはApache License 2.0)ので、任意のコンパイラでParallelism TSを試すことができます。


並列ソートのパフォーマンス測定

それでは、以上のスレッド並列化されたソート関数のパフォーマンス(ソート時間)を、std::sortおよび並列化なしのクイックソートと比較してみましょう。またあわせて、tbb::parallel_sortとParallelism TSによるstd::sortのソート時間も確認していきます。パフォーマンスを測定した環境は、


  • CPU: Intel Core i7-7820X (Skylake-X, Hyper Threading ON (物理8コア論理16コア), SpeedStep OFF, Turbo Boost OFF)

  • メモリ: DDR4-2666 32GB (8GB×4)

であり、WindowsとLinuxでかなり挙動が異なるため、それぞれ別個に測定し、さらに、両方の環境において、それぞれ二つのコンパイラで測定しました。ここで、配列の要素を500個から1億個まで変化させ、ソートにかかった時間を測定しました。ただし、測定回数は10回とし、その平均を結果としました。Windowsの測定環境は、


  • OS: Microsoft Windows 10 Enterprise (64bit)

であり、次の二つのコンパイラで測定しました。


  • Microsoft Visual C++ (MSVC) 14.14 (Visual Studio 2017 version 15.7.3) x64ビルド

  • Intel Parallel Studio XE 2018 Update 3 (Intel C++ Compiler 18.0 Update 3) on Visual Studio 2017 x64ビルド

また、Linuxの測定環境は


  • OS: Linux Mint 18.3 Sylvia (x64)

であり、次の二つのコンパイラで測定しました。


  • Clang 6.0.1 (llvm 6.0.0)(コンパイル最適化オプション: -O3 -mtune=native -march=native)

  • Intel Parallel Studio XE 2018 Update 3 (Intel C++ Compiler 18.0 Update 3)(コンパイル最適化オプション: -O3 -xHOST -ipo)

また、Windows及びLinuxの両方において、使用しているTBBとParallel STLのバージョンは以下です。


  • TBB: Threading Building Blocks 2018 Update 4

  • Parallel STL: Parallel STL 20180529 release


Windows - Microsoft Visual C++ (MSVC) 14.14 (Visual Studio 2017 version 15.7.3) の場合

まず、OSがWindowsで、コンパイラがMSVC 14.14 (Visual Studio 2017 version 15.7.3)の場合について述べたいと思います。


完全にシャッフルされたデータをソートする場合

まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。ここで言う「完全にシャッフルされたデータが詰められた配列」とは、例えば、

std::vector<int> vec(1000000);

std::iota(vec.begin(), vec.end(), 1);
std::random_device rnd;
std::shuffle(vec.begin(), vec.end(), std::mt19937(rnd()));

上記のコードのvecのような配列のことです。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
TBB
tbb::parallel_sort
std::sort (MSVC内蔵のParallelism TS)
std::sort (Parallel STLのParallelism TS)

500
0.0000105
0.0000206
0.0007854
0.0001106
0.0000118
0.0000488
0.0000103

1000
0.0000307
0.0000458
0.0017938
0.0000417
0.0000193
0.0000615
0.0000314

5000
0.0002282
0.0002706
0.0056983
0.0001117
0.0000755
0.0001665
0.0000541

10000
0.0004913
0.0005856
0.0085671
0.0001706
0.0001263
0.0002249
0.0000892

50000
0.0029769
0.0033045
0.0193815
0.0009211
0.0005671
0.0006856
0.0003189

100000
0.0063660
0.0069406
0.0251998
0.0015111
0.0011198
0.0013137
0.0006927

500000
0.0371493
0.0390146
0.0266544
0.0111206
0.0058191
0.0066502
0.0036882

1000000
0.0776207
0.0803658
0.0450936
0.0190282
0.0113178
0.0135686
0.0083812

5000000
0.4346670
0.4429705
0.1116999
0.0772312
0.0598766
0.0680693
0.0412007

10000000
0.9163644
0.9171497
0.2934905
0.2847365
0.1186347
0.1397822
0.0871509

50000000
5.0630314
4.9998463
1.4515623
1.4487035
0.6638043
0.7369049
0.4785176

100000000
10.619285
10.357525
2.6112381
2.6693424
1.3470694
1.5490454
0.9843640

これをグラフにすると、以下の図のようになります(両対数グラフであることに注意してください)。

完全にシャッフルされたデータのグラフ_MSVC_on_Windows.png

TBBは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります(配列の要素数が500~1000個の場合は、TBBはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートより遅くなっています)。原因は分かりませんが、std::threadはパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::sortや並列化なしのクイックソートよりも高速になります。

また、TBBとstd::threadは、配列の要素数が1000万個以上になると概ね同じような傾向を示します。std::threadとTBBは、配列の要素数が1000万個以上では、std::sortよりも3倍強~4倍強程度高速で、並列化なしのクイックソートよりも3倍強~4倍弱程度高速であることが分かります。

tbb:parallel_sortは、配列の要素数が500個の場合を除いてstd::sortより高速であり、配列の要素数によらず並列化なしのクイックソートより高速です。配列の要素数が5万個以上の場合、std::sortより5倍強~8倍弱程度高速で、並列化なしのクイックソートよりも、6倍弱~8倍弱程度高速です。

MSVC内蔵のParallelism TSのstd::sortは、配列の要素数が5000個以上で、通常のstd::sortや並列化なしのクイックソートより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりよりも4倍強~7倍弱程度高速で、並列化なしのクイックソートよりよりも5倍弱~7倍弱程度高速です。しかし、MSVC内蔵のParallelism TSのstd::sortをtbb:parallel_sortと比較すると、配列の要素数によらず、前者は後者より低速です。配列の要素数が5万個以上では、前者は後者より10%~20%弱程度パフォーマンスが劣ります。

Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortより高速であり、配列の要素数によらず並列化なしのクイックソートより高速です。配列の要素数が5万個以上の場合は、通常のstd::sortよりも9倍強~11倍弱程度高速であり、並列化なしのクイックソートと比べても、9.5倍~10.5倍前後高速です。また、Parallel STLのParallelism TSのstd::sortは、tbb::parallel_sortと比較しても、配列の要素数が1000個の場合を除いて明らかに速く、配列の要素数が5000個以上の場合、前者は後者に比べて35%~80%弱程度高速です。


あらかじめソートされたデータをソートする場合

極端な場合として、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。ここで言う「あらかじめソートされたデータが詰められた配列」とは、例えば、

std::vector<int> vec(1000000);

std::iota(vec.begin(), vec.end(), 1);

上記のコードのvecのような配列のことです。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
TBB
tbb::parallel_sort
std::sort (MSVC内蔵のParallelism TS)
std::sort (Parallel STLのParallelism TS)

500
0.0000022
0.0000044
0.0006129
0.0000077
0.0000123
0.0000088
0.0000022

1000
0.0000048
0.0000080
0.0047579
0.0000227
0.0000140
0.0000174
0.0000089

5000
0.0000332
0.0000451
0.0045788
0.0000771
0.0000158
0.0000453
0.0000213

10000
0.0000710
0.0000921
0.0046490
0.0001623
0.0000157
0.0000664
0.0000332

50000
0.0004049
0.0004956
0.0052971
0.0007838
0.0000242
0.0001726
0.0000888

100000
0.0008649
0.0010173
0.0062134
0.0014990
0.0000345
0.0002921
0.0001802

500000
0.0048160
0.0048431
0.0111454
0.0065952
0.0001063
0.0011728
0.0009167

1000000
0.0102507
0.0100107
0.0181422
0.0130628
0.0001778
0.0023222
0.0017393

5000000
0.0651592
0.0611962
0.0898387
0.0819424
0.0007313
0.0140111
0.0102733

10000000
0.1357622
0.1279987
0.1796392
0.1684790
0.0013920
0.0282092
0.0221214

50000000
0.7438876
0.7182626
0.9452092
0.9320811
0.0065915
0.1444874
0.1310186

100000000
1.5588848
1.4604970
1.9148640
1.8876132
0.0130660
0.2972128
0.2600567

これをグラフにすると、以下の図のようになります。

あらかじめソートされたデータのグラフ_MSVC_on_Windows.png

std::thread、TBBは、配列の要素数によらず、std::sortおよび並列化なしのクイックソートよりも遅くなっています(これは再帰と深い関係にあるようで、配列のデータがすでにソートされている場合は再帰させない(=並列化していない)クイックソートが高速になるようです)。std::threadは相変わらずなぜかパフォーマンスが悪いのですが、配列の要素数が500万個以上では、TBBとよく似た傾向を示すようになります。

tbb::parallel_sortについては興味深い結果が得られています。tbb::parallel_sortは、配列の要素数が1000個以下の場合こそstd::sortや並列化なしのクイックソートの後塵を拝しますが、要素数5000個で追い抜き、要素数5万個以上になると、std::sortと比べて文字通り桁違いに高速となります。配列の要素数が1億個の場合、tbb::parallel_sortはstd::sortと比べて約120倍、並列化なしのクイックソートと比べても、約110倍の速度を叩きだしています。

MSVC内蔵のParallelism TSのstd::sortは、配列の要素数が1万個以上で、通常のstd::sortや並列化なしのクイックソートより高速ですが、一方で配列の要素数が大きい場合にはtbb::parallel_sortほどの速度は出ていません。配列の要素数が5万個以上の場合、MSVC内蔵のParallelism TSのstd::sortは、通常のstd::sortと比べて2倍強~5倍強程度高速であり、並列化なしのクイックソートと比べて3倍弱~5倍弱程度高速です。なお、MSVC内蔵のParallelism TSのstd::sortと、tbb::parallel_sortを比較した場合、配列の要素数5万個以上で、後者の方が前者より7倍強~23倍弱程度高速です。

Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortと同じかより高速であり、配列の要素数が1000個の場合を除いて並列化なしのクイックソートより高速です。しかし一方で、MSVC内蔵のParallelism TSのstd::sortと同様、配列の要素数が大きい場合にtbb::parallel_sortほどの速度は出ていません。配列の要素数が5万個以上の場合、Parallel STLのParallelism TSのstd::sortは、通常のstd::sortよりも4.5倍強~6倍弱程度高速であり、並列化なしのクイックソートよりも5.5~6倍前後高速です。なお、Parallel STLのParallelism TSのstd::sortと、tbb::parallel_sortを比較した場合、配列の要素数5万個以上で、後者の方が前者より4倍弱~20倍弱程度高速です。


最初の1/4だけソートされたデータをソートする場合

最後に、最初の1/4だけソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。ここで言う「最初の1/4だけソートされたデータが詰められた配列」とは、例えば、

std::vector<int> vec(1000000);

std::iota(vec.begin(), vec.end(), 1);
std::random_device rnd;
std::shuffle(vec.begin() + vec.size() / 4, vec.end(), std::mt19937(rnd()));

上記のコードのvecのような配列のことです。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
TBB
tbb::parallel_sort
std::sort (MSVC内蔵のParallelism TS)
std::sort (Parallel STLのParallelism TS)

500
0.0000077
0.0000155
0.0006790
0.0000258
0.0000239
0.0000190
0.0000067

1000
0.0000217
0.0000353
0.0046376
0.0000684
0.0000296
0.0000369
0.0000296

5000
0.0001720
0.0002136
0.0047161
0.0002475
0.0000796
0.0000890
0.0000544

10000
0.0003776
0.0004529
0.0051054
0.0005376
0.0001177
0.0001537
0.0000992

50000
0.0022752
0.0025642
0.0075665
0.0028267
0.0004799
0.0005591
0.0002598

100000
0.0048283
0.0052955
0.0103339
0.0059098
0.0008953
0.0010035
0.0005199

500000
0.0280530
0.0304428
0.0363402
0.0321648
0.0044743
0.0051084
0.0030352

1000000
0.0591813
0.0613432
0.0701248
0.0645308
0.0087039
0.0101671
0.0059988

5000000
0.3400867
0.3401270
0.3667609
0.3607571
0.0464018
0.0558637
0.0326124

10000000
0.7158605
0.7192092
0.7553036
0.7495500
0.0963697
0.1061310
0.0684678

50000000
3.9531315
3.8887368
4.1261271
4.0954510
0.4935916
0.5956207
0.3806331

100000000
8.1931949
7.9252468
8.3920237
8.3893786
1.0313685
1.1540692
0.7773747

これをグラフにすると、以下の図のようになります。

最初の1_4だけソートされたデータのグラフ_MSVC_on_Windows.png

std::threadおよびTBBは、配列の要素数によらず、並列化なしのクイックソートよりも遅くなっています(理由はやはり再帰にあると考えています)。std::threadは相変わらずなぜかパフォーマンスが悪いのですが、配列の要素数が100万個以上では、TBBとよく似た傾向を示すようになります。

tbb:parallel_sortは、配列の要素数が5000個未満の場合を除いてstd::sortより高速であり、配列の要素数が500個の場合を除いて並列化なしのクイックソートより高速です。配列の要素数が5万個以上の場合、std::sortよりも5倍弱~8倍程度高速であり、並列化なしのクイックソートよりも5倍強~8倍弱程度高速です。

MSVC内蔵のParallelism TSのstd::sortは、配列の要素数が5000個以上で、通常のstd::sortや並列化なしのクイックソートより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortより約4倍~7倍程度高速であり、並列化なしのクイックソートよりも4.5倍~7倍弱程度高速です。しかし、MSVC内蔵のParallelism TSのstd::sortをtbb:parallel_sortと比較すると、配列の要素数によらず、前者は後者より低速です。配列の要素数が5万個以上では、前者は後者より10%~20%弱程度パフォーマンスが劣ります。

Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて、通常のstd::sortより高速であり、配列の要素数によらず並列化なしのクイックソートより高速です。配列の要素数が5万個以上の場合は、通常のstd::sortより9倍弱~10.5倍程度高速で、並列化なしのクイックソートよりも10倍~10.5倍程度高速です。また、Parallel STLのParallelism TSのstd::sortは、tbb::parallel_sortと比較しても、配列の要素数によらず常に高速であり、配列の要素数が5万個以上の場合、前者は後者に比べて30%~80%程度高速です。


Windows - Intel C++ Compiler 18.0 Update 3 (on Visual Studio 2017)の場合

次に、OSがWindowsで、コンパイラがIntel C++ Compiler 18.0 Update 3 (on Visual Studio 2017)の場合について述べたいと思います。


完全にシャッフルされたデータをソートする場合

まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します(MSVCの場合と同様ですので、コードは省略します)。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
OpenMP
TBB
Cilk
tbb::parallel_sort
std::sort (Parallel STLのParallelism TS)

500
0.0000112
0.0000164
0.0007436
0.0006165
0.0004290
0.0006597
0.0000160
0.0000128

1000
0.0000385
0.0000420
0.0019905
0.0000526
0.0000364
0.0000517
0.0000219
0.0000311

5000
0.0002925
0.0002809
0.0067707
0.0001042
0.0001108
0.0002143
0.0000860
0.0000744

10000
0.0006159
0.0006126
0.0105863
0.0001783
0.0001770
0.0002441
0.0001477
0.0001108

50000
0.0037654
0.0035009
0.0212561
0.0009066
0.0009384
0.0010285
0.0006311
0.0003845

100000
0.0081020
0.0072381
0.0272721
0.0018079
0.0015905
0.0016453
0.0012977
0.0009076

500000
0.0411484
0.0365986
0.0268489
0.0117485
0.0111043
0.0114088
0.0058300
0.0038435

1000000
0.0840850
0.0766921
0.0441507
0.0203404
0.0199599
0.0207461
0.0115498
0.0078943

5000000
0.4760080
0.4235053
0.1097566
0.0818633
0.0769053
0.0767336
0.0631194
0.0435588

10000000
0.9974043
0.8825915
0.2854968
0.3022849
0.2732951
0.2796027
0.1210720
0.0893373

50000000
5.5457645
4.8240598
1.4252771
1.5601663
1.4344915
1.4282759
0.6983091
0.4781524

100000000
11.542163
9.9299251
2.5361999
2.8605935
2.6061240
2.5401996
1.4267306
0.9885334

これをグラフにすると、以下の図のようになります。

完全にシャッフルされたデータのグラフ_ICC_on_Windows.png

TBBは配列の要素数が1000個以上で、またOpenMP、Cilkは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります(配列の要素数が500個、あるいは1000個の場合は、これらはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートより同じか遅くなっています)。原因は分かりませんが、std::threadはパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::sortや並列化なしのクイックソートよりも高速になります。

また、OpenMP、TBBは、配列の要素数が5000個以上で概ね同じような傾向を示し、配列の要素数が10万個以上では、これにCilkが加わります。加えて、配列の要素数が1000万個以上では、さらにこれにstd::threadが加わります。std::thread、OpenMP、TBB、Cilkは、配列の要素数が1000万個以上では、std::sortより3.5倍弱~4.5倍弱程度高速で、並列化なしのクイックソートよりも3倍弱~4倍弱程度高速であることが分かります。

tbb:parallel_sortは、配列の要素数が500個の場合を除いてstd::sortより高速で、配列の要素数に関わらず、並列化なしのクイックソートより高速です。配列の要素数が50万個以上の場合、std::sortと比べて、7倍~8倍程度高速であり、並列化なしのクイックソートよりも6倍強~7倍強程度高速です。

Parallelism TSのstd::sortは、配列の要素数が500個の場合を除いてstd::sortより高速で、配列の要素数に関わらず、並列化なしのクイックソートより高速です。配列の要素数が5万個以上の場合は、通常のstd::sortと比べて、9倍弱~12倍弱程度高速であり、並列化なしのクイックソートより8倍弱~10倍程度高速です。また、Parallelism TSのstd::sortはtbb::parallel_sortと比較しても明らかに速く、配列の要素数が5万個以上の場合、前者は後者に比べておよそ35%~65%高速です。


あらかじめソートされたデータをソートする場合

次に、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します(MSVCの場合と同様ですので、コードは省略します)。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
OpenMP
TBB
Cilk
tbb::parallel_sort
std::sort (Parallel STLのParallelism TS)

500
0.0000027
0.0000029
0.0006413
0.0000263
0.0000056
0.0000080
0.0000127
0.0000044

1000
0.0000095
0.0000066
0.0059114
0.0000371
0.0000188
0.0000159
0.0000139
0.0000096

5000
0.0000680
0.0000353
0.0051308
0.0000898
0.0000732
0.0000705
0.0000167
0.0000290

10000
0.0001460
0.0000745
0.0051399
0.0001532
0.0001367
0.0001354
0.0000207
0.0000409

50000
0.0008523
0.0004131
0.0059481
0.0007127
0.0006883
0.0006611
0.0000360
0.0001048

100000
0.0018375
0.0008384
0.0065833
0.0014420
0.0014218
0.0013477
0.0000470
0.0001925

500000
0.0103541
0.0034851
0.0094455
0.0069455
0.0068525
0.0069824
0.0001189
0.0010449

1000000
0.0130985
0.0069574
0.0151293
0.0143057
0.0139627
0.0123884
0.0001910
0.0017862

5000000
0.0796871
0.0436289
0.0709000
0.0834809
0.0678125
0.0654350
0.0008728
0.0106855

10000000
0.1674286
0.0913427
0.1412512
0.1737078
0.1372828
0.1371062
0.0015763
0.0243696

50000000
0.9144676
0.5113665
0.7255208
0.9484902
0.7217126
0.7356642
0.0074194
0.1261906

100000000
1.9076368
1.0650431
1.4900302
1.9383843
1.4831862
1.5115661
0.0144612
0.2537880

これをグラフにすると、以下の図のようになります。

あらかじめソートされたデータのグラフ_ICC_on_Windows.png

std::thread、OpenMP、TBB、Cilkは、配列の要素数によらず、並列化なしのクイックソートよりも遅くなっています(これは再帰と深い関係にあるようで、配列のデータがすでにソートされている場合は再帰させない(=並列化していない)クイックソートが高速になるようです)。std::sortと比較すると、std::threadは相変わらずなぜかパフォーマンスが悪く、std::sortより高速となっているのは配列の要素数が500万個以上の場合のみです(ただ、配列の要素数が1億個の場合、std::threadはstd::sortより30%弱ほど高速になっています)。OpenMP、TBBおよびCilkについては、配列の要素数が1万個以上でよく似た傾向を示し、配列の要素数が5万個以上では、std::sortよりも最大で50%程度高速になっています。ただ、OpenMPは配列の要素数500万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。

tbb::parallel_sortについては興味深い結果が得られています。tbb::parallel_sortは、配列の要素数が5000個未満の場合こそ、std::sortや並列化なしのクイックソートの後塵を拝しますが、要素数5000個で追い抜き、要素数5万個以上になると、std::sortや並列化なしのクイックソートと比べて文字通り桁違いに高速となります。配列の要素数が1億個の場合、tbb::parallel_sortはstd::sortと比べて約132倍、並列化なしのクイックソートと比べて約74倍の速度を叩きだしています。

Parallel STLのParallelism TSのstd::sortは、tbb::parallel_sortと同様に、配列の要素数5000個以上でstd::sortや並列化なしのクイックソートより高速ですが、一方で配列の要素数が大きい場合にtbb::parallel_sortほどの速度は出ていません。配列の要素数が5万個以上の場合、Parallel STLのParallelism TSのstd::sortは、通常のstd::sortと比べて、7倍強~10倍弱程度高速であり、並列化なしのクイックソートより3倍強~4倍強前後高速です。なお、Parallel STLのParallelism TSのstd::sortとtbb::parallel_sortを比較した場合、配列の要素数5万個以上の場合、後者の方が前者より3倍弱~17.5倍程度高速です。


最初の1/4だけソートされたデータをソートする場合

最後に、最初の1/4だけソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します(MSVCの場合と同様ですので、コードは省略します)。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
OpenMP
TBB
tbb::parallel_sort
std::sort (Parallelism TS)

500
0.0000083
0.0000117
0.0006612
0.0000281
0.0000144
0.0000164
0.0000267

1000
0.0000277
0.0000282
0.0053156
0.0000687
0.0000367
0.0000438
0.0000339

5000
0.0002233
0.0002179
0.0056870
0.0002779
0.0002645
0.0002533
0.0000920

10000
0.0004964
0.0004635
0.0055099
0.0005340
0.0005445
0.0005217
0.0001267

50000
0.0029371
0.0026732
0.0079784
0.0029162
0.0028928
0.0028872
0.0005083

100000
0.0062987
0.0053871
0.0101536
0.0060433
0.0061069
0.0059785
0.0009695

500000
0.0313180
0.0281566
0.0346996
0.0344818
0.0323094
0.0300344
0.0046931

1000000
0.0650140
0.0578785
0.0667329
0.0709481
0.0646521
0.0620647
0.0088882

5000000
0.3753888
0.3213315
0.3491990
0.3885325
0.3461711
0.3494958
0.0501326

10000000
0.7755058
0.6740220
0.7193811
0.8073721
0.7197736
0.7201322
0.0975946

50000000
4.3590371
3.7176883
3.9487141
4.4289383
3.9589728
4.0048623
0.5239695

100000000
9.0020265
7.5980535
8.0375931
9.0428873
8.0102797
8.1078513
1.0722374

これをグラフにすると、以下の図のようになります。

最初の1_4だけソートされたデータのグラフ_ICC_on_Windows.png

std::thread、OpenMP、TBB、Cilkは、配列の要素数によらず、並列化なしのクイックソートよりも遅くなっています。std::sortと比較すると、std::threadは相変わらずなぜかパフォーマンスが悪く、std::sortより高速となっているのは配列の要素数が500万個以上の場合のみです(配列の要素数が1億個の場合には、std::threadはstd::sortより12%ほど高速になっています)。OpenMP、TBBおよびCilkについては、配列の要素数が1万個以上でよく似た傾向を示し、配列の要素数が5万個以上では、std::sortよりも最大で約12%高速になっています。ただ、OpenMPは配列の要素数100万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。

tbb:parallel_sortは、配列の要素数が5000個未満の場合を除いて、std::sort及び並列化なしのクイックソートより高速です。配列の要素数が50万個以上の場合、std::sortと比べて、7.5倍~8.5倍弱程度高速であり、並列化なしのクイックソートよりも6.5倍~7倍強程度高速です。

Parallelism TSのstd::sortは、配列の要素数が5000個未満の場合を除いてstd::sortより高速で、配列の要素数が1000個の場合を除いて並列化なしのクイックソートより高速です。配列の要素数が5万個以上の場合は、通常のstd::sortと比べて、9倍強~11.5倍程度高速であり、並列化なしのクイックソートより8倍強~10倍弱程度高速です。また、Parallelism TSのstd::sortはtbb::parallel_sortと比較しても明らかに速く、配列の要素数が5万個以上の場合、前者は後者に比べておよそ40%弱~65%程度高速です。


Linux - Clang 6.0.1 (llvm 6.0.0)の場合

次に、OSがLinuxで、コンパイラがClang 6.0.1 (llvm 6.0.0)の場合について述べたいと思います。


完全にシャッフルされたデータをソートする場合

まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
OpenMP
TBB
tbb::parallel_sort
std::sort (Parallel STLのParallelism TS)

500
0.0000082
0.0000176
0.0000452
0.0012356
0.0000697
0.0000108
0.0000095

1000
0.0000270
0.0000432
0.0008947
0.0000403
0.0000410
0.0000281
0.0000284

5000
0.0002055
0.0002725
0.0025421
0.0000969
0.0002940
0.0008250
0.0020838

10000
0.0004574
0.0007737
0.0035038
0.0001719
0.0006230
0.0067376
0.0035836

50000
0.0037939
0.0033443
0.0079702
0.0009191
0.0070720
0.0097454
0.0162332

100000
0.0057554
0.0066024
0.0038643
0.0016838
0.0146290
0.0116198
0.0024709

500000
0.0305660
0.0365841
0.0122286
0.0116593
0.0297616
0.0063712
0.0031959

1000000
0.0636356
0.0762420
0.0218816
0.0201896
0.0354132
0.0124700
0.0066840

5000000
0.3541420
0.4180345
0.0781733
0.0836665
0.0955434
0.0599293
0.0383507

10000000
0.7393443
0.8686349
0.2739279
0.2962601
0.2982571
0.1217534
0.0822734

50000000
4.0685265
4.7451769
1.3936217
1.5330745
1.4061053
0.6486228
0.4484733

100000000
8.4711877
9.8086634
2.5069266
2.8265746
2.5259248
1.3069129
0.9327233

これをグラフにすると、以下の図のようになります。

完全にシャッフルされたデータのグラフ_Clang_on_Linux.png

Windowsの場合と比べて、ややばらついた結果となっています。

OpenMPは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります(配列の要素数が500~1000個の場合は、これらはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートとほぼ同じか遅くなっています)。std::threadについては、Windowsの場合と異なり、パフォーマンスはそれほど悪くありません。実際、std::threadは、配列の要素数が10万個以上で、std::sortや並列化なしのクイックソートよりも高速になります。TBBは、いくつか例外はあるものの、配列の要素数が50万個でstd::sortや並列化なしのクイックソートより若干高速となり、配列の要素数100万個以上では、std::sortや並列化なしのクイックソートよりも明らかに高速になっています。また、OpenMPは配列の要素数1億個のパフォーマンスがぱっとせず、std::threadおよびTBBに逆転されています。

また、std::threadとOpenMPは、配列の要素数が50万個以上になると概ね同じような傾向を示し、配列の要素数が500万個以上では、これにTBBが加わります。std::thread、OpenMP、TBBは、配列の要素数が1000万個以上では、std::sortよりも2.5~3倍強程度高速で、並列化なしのクイックソートよりも3倍弱~4倍弱程度高速であることが分かります。

tbb:parallel_sortは、配列の要素数が50万個以上でstd::sortおよび並列化なしのクイックソートより高速になります(ただし、配列の要素数が500~1000個の場合、tbb:parallel_sortは並列化なしのクイックソートよりも高速になっています)。配列の要素数が50万個以上では、tbb:parallel_sortはstd::sortよりも5倍弱~6.5倍程度高速であり、並列化なしのクイックソートより6倍弱~7.5倍程度高速です。

Parallel STLのParallelism TSのstd::sortは、配列の要素数が10万個以上で、通常のstd::sortおよび並列化なしのクイックソートより高速になります(ただし、配列の要素数が500~1000個の場合、Parallel STLのParallelism TSのstd::sortは並列化なしのクイックソートよりも高速になっています)。Parallel STLのParallelism TSのstd::sortは、配列の要素数が50万個以上で、通常のstd::sortよりも9倍強~9.5倍程度高速であり、並列化なしのクイックソートより10.5倍~11.5倍程度高速です。

また、Parallel STLのParallelism TSのstd::sortとtbb::parallel_sortを比較すると、配列の要素数が50万個以上の場合、前者は後者に比べておよそ1.5倍弱~2倍弱程度高速です(配列の要素数が10万個の場合は、前者は後者に比べて4.7倍ほど高速になっています)。


あらかじめソートされたデータをソートする場合

次に、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
OpenMP
TBB
Cilk
tbb::parallel_sort
std::sort (Parallel STLのParallelism TS)

500
0.0000039
0.0000036
0.0000293
0.0011182
0.0000190
0.0000787
0.0000033

1000
0.0000071
0.0000088
0.0007118
0.0000374
0.0000182
0.0000393
0.0000073

5000
0.0000483
0.0000538
0.0015674
0.0001045
0.0000909
0.0000445
0.0000433

10000
0.0001047
0.0001119
0.0004463
0.0001898
0.0001850
0.0000498
0.0000889

50000
0.0006514
0.0006585
0.0011631
0.0009409
0.0023101
0.0072143
0.0003620

100000
0.0014324
0.0022156
0.0021136
0.0019272
0.0033720
0.0102214
0.0074801

500000
0.0076411
0.0066656
0.0072039
0.0094773
0.0115869
0.0115223
0.0007200

1000000
0.0084903
0.0096681
0.0135786
0.0191987
0.0242018
0.0013136
0.0011146

5000000
0.0531632
0.0577156
0.0779753
0.1112065
0.1015973
0.0005733
0.0071112

10000000
0.1127137
0.1202401
0.1626628
0.2306885
0.2032101
0.0010204
0.0175606

50000000
0.6398618
0.6757863
0.8924792
1.2693008
0.9598112
0.0045571
0.0970528

100000000
1.3435503
1.3915084
1.8296449
2.6020277
1.9420743
0.0089462
0.2036036

これをグラフにすると、以下の図のようになります。

あらかじめソートされたデータのグラフ_Clang_on_Linux.png

これもWindowsの場合と比べると、結果がばらついています。

std::thread、OpenMP、TBB、Cilkは、配列の要素数によらず、std::sortおよび並列化なしのクイックソートよりも遅くなっています。

tbb::parallel_sortは、std::sortおよび並列化なしのクイックソートと比べて速かったり遅かったりと、結果が安定しません。しかし、配列の要素数500万個以上では、std::sortおよび並列化なしのクイックソートと比べて桁違いに高速となります。配列の要素数が1億個の場合、tbb::parallel_sortはstd::sortと比べて約150倍、並列化なしのクイックソートと比べて約156倍の速度を叩きだしています。

Parallel STLのParallelism TSのstd::sortは、std::sortおよび並列化なしのクイックソートと比べ、配列の要素数が1000個および10万個の場合を除いて高速です。特に、配列の要素数50万個以上では、std::sortや並列化なしのクイックソートと比べて速度で優位に立ちます。配列の要素数が50万個以上の場合、Parallel STLのParallelism TSのstd::sortは、std::sortと比べて、6倍強~10倍強程度高速であり、並列化なしのクイックソートと比べて7倍弱~9倍強高速となっています。なお、tbb::parallel_sortとParallel STLのParallelism TSのstd::sortを比較した場合、配列の要素数500万個以上で、前者の方が後者より12倍強~23倍弱程度高速です。


最初の1/4だけソートされたデータをソートする場合

次に、最初の1/4だけソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
OpenMP
TBB
tbb::parallel_sort
std::sort (Parallel STLのParallelism TS)

500
0.0000057
0.0000124
0.0000499
0.0000318
0.0000106
0.0000150
0.0000065

1000
0.0000184
0.0000321
0.0019767
0.0000664
0.0000379
0.0000317
0.0000199

5000
0.0010089
0.0002181
0.0005501
0.0002711
0.0002543
0.0001953
0.0058662

10000
0.0003625
0.0004642
0.0013484
0.0011022
0.0014804
0.0052794
0.0004146

50000
0.0021589
0.0033035
0.0031971
0.0029864
0.0041919
0.0097452
0.0057634

100000
0.0051278
0.0054304
0.0059275
0.0062049
0.0072869
0.0139083
0.0058345

500000
0.0231042
0.0285078
0.0308658
0.0351382
0.0380815
0.0047281
0.0024596

1000000
0.0487949
0.0583199
0.0626893
0.0715997
0.0792592
0.0092865
0.0052220

5000000
0.2758546
0.3208566
0.3421503
0.3889630
0.3597205
0.0483009
0.0296392

10000000
0.5679869
0.6739331
0.7115292
0.8050502
0.7370682
0.1029519
0.0642536

50000000
3.1428122
3.6859859
3.9115053
4.4406249
3.9799025
0.5014625
0.3498908

100000000
6.6013517
7.5374835
7.9889059
8.9916836
8.1118474
1.0711941
0.7272231

これをグラフにすると、以下の図のようになります。

最初の1_4だけソートされたデータのグラフ_Clang_on_Linux.png

これもWindowsの場合と比べると、結果がばらついています。

std::thread、OpenMP、TBB、Cilkは、配列の要素数500個や5000個の場合など、一部の例外を除き、std::sortおよび並列化なしのクイックソートよりも遅くなっています。

tbb:parallel_sortは、配列の要素数が50万個以上の場合、std::sortよりも5倍弱~6倍強程度高速であり、並列化なしのクイックソートより6倍~7倍強程度高速です。

Parallel STLのParallelism TSのstd::sortは、配列の要素数が50万個以上の場合は、std::sortよりも9倍~9倍強程度高速であり、並列化なしのクイックソートより10.5倍~11.5倍程度高速です。また、Parallel STLのParallelism TSのstd::sortは、tbb::parallel_sortと比較しても速く、前者は後者に比べて、1.5倍強~2.5倍弱程度高速です(配列の要素数が5000個~10000個の場合は例外です)。


Linux - Intel C++ Compiler 18.0 Update 3の場合

次に、OSがLinuxで、コンパイラがIntel C++ Compiler 18.0 Update 3の場合について述べたいと思います。


完全にシャッフルされたデータをソートする場合

まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
OpenMP
TBB
Cilk
tbb::parallel_sort
std::sort (Parallel STLのParallelism TS)

500
0.0000079
0.0000169
0.0000656
0.0002873
0.0001826
0.0000580
0.0000122
0.0000102

1000
0.0000285
0.0000433
0.0022957
0.0000424
0.0000421
0.0000382
0.0000310
0.0000315

5000
0.0002369
0.0005216
0.0012250
0.0000906
0.0002992
0.0007747
0.0050822
0.0032201

10000
0.0005206
0.0007270
0.0023432
0.0001627
0.0018862
0.0011383
0.0076266
0.0057093

50000
0.0029666
0.0031581
0.0024698
0.0009580
0.0035261
0.0079922
0.0032476
0.0040136

100000
0.0058588
0.0066358
0.0039022
0.0016618
0.0124593
0.0108226
0.0011418
0.0005878

500000
0.0334523
0.0368511
0.0118027
0.0115971
0.0251962
0.0114504
0.0058005
0.0031158

1000000
0.0697113
0.0768750
0.0222053
0.0198716
0.0335708
0.0206454
0.0116032
0.0065228

5000000
0.3888895
0.4216885
0.0796598
0.0804012
0.0874932
0.0754879
0.0588387
0.0368285

10000000
0.8107796
0.8841288
0.2707159
0.2934763
0.2827644
0.2833793
0.1189601
0.0797275

50000000
4.4521744
4.8020990
1.3869705
1.5479343
1.4344521
1.4200178
0.6446718
0.4296836

100000000
9.2714236
9.9260969
2.4890098
2.7989879
2.5465062
2.5166192
1.2975257
0.8914330

これをグラフにすると、以下の図のようになります。

完全にシャッフルされたデータのグラフ_ICC_on_Linux.png

Windowsの場合と比べて、ややばらついた結果となっています。

OpenMPは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります(配列の要素数が500~1000個の場合は、これらはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートとほぼ同じか遅くなっています)。std::threadについては、Windowsの場合と異なり、パフォーマンスはそれほど悪くありません。実際、std::threadは、配列の要素数が5万個以上で、std::sortや並列化なしのクイックソートよりも高速になります。TBBは、いくつか例外はあるものの、配列の要素数50万個でstd::sortや並列化なしのクイックソートより若干高速となり、配列の要素数100万個以上では、std::sortや並列化なしのクイックソートよりも明らかに高速になっています。また、OpenMPは配列の要素数1億個のパフォーマンスがぱっとせず、std::threadおよびTBBに逆転されています。

また、std::thread、OpenMP、Cilkは、配列の要素数が50万個以上になると概ね同じような傾向を示し、配列の要素数が500万個以上では、これにTBBが加わります。std::thread、OpenMP、TBB、Cilkは、配列の要素数が1000万個以上では、std::sortよりも3倍弱~4倍弱程度高速で、並列化なしのクイックソートよりも約3倍~4倍弱程度高速であることが分かります。

tbb:parallel_sortは、配列の要素数が10万個以上でstd::sortおよび並列化なしのクイックソートより高速になります(ただし、配列の要素数が500~1000個の場合、tbb:parallel_sortは並列化なしのクイックソートよりも高速になっています)。配列の要素数が10万個以上では、tbb:parallel_sortはstd::sortよりも5倍強~7倍強程度高速であり、並列化なしのクイックソートより6倍弱~7.5倍強程度高速です。

Parallel STLのParallelism TSのstd::sortは、配列の要素数が10万個以上で、std::sortおよび並列化なしのクイックソートより高速になります(ただし、配列の要素数が500~1000個の場合、Parallel STLのParallelism TSのstd::sortは並列化なしのクイックソートよりも高速になっています)。Parallel STLのParallelism TSのstd::sortは、配列の要素数が50万個以上で、std::sortよりも10倍弱~11倍弱程度高速であり、並列化なしのクイックソートより10.5倍強~11.5倍弱程度高速です。

また、Parallelism TSのstd::sortとtbb::parallel_sortを比較すると、配列の要素数が50万個以上の場合、前者は後者に比べて20%弱~95%程度高速です(配列の要素数1000個および5万個の場合は例外で、前者より後者の方が高速になっています)。


あらかじめソートされたデータをソートする場合

次に、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
OpenMP
TBB
Cilk
tbb::parallel_sort
std::sort (Parallel STLのParallelism TS)

500
0.0000026
0.0000026
0.0000369
0.0001380
0.0000052
0.0006642
0.0000163
0.0000037

1000
0.0000068
0.0000062
0.0072218
0.0000345
0.0000131
0.0000128
0.0000363
0.0000075

5000
0.0000443
0.0000351
0.0003587
0.0000937
0.0000603
0.0000605
0.0000439
0.0000451

10000
0.0000934
0.0003099
0.0004234
0.0002161
0.0001211
0.0001202
0.0000523
0.0015565

50000
0.0005219
0.0004055
0.0009297
0.0008275
0.0020503
0.0007468
0.0082608
0.0004393

100000
0.0011039
0.0008914
0.0016211
0.0016405
0.0027035
0.0018278
0.0104018
0.0010793

500000
0.0050646
0.0033673
0.0053721
0.0080153
0.0076922
0.0170043
0.0001027
0.0006184

1000000
0.0103374
0.0071789
0.0103518
0.0162369
0.0149029
0.0175721
0.0002005
0.0011787

5000000
0.0625444
0.0412962
0.0594933
0.0904649
0.0685754
0.0613799
0.0007665
0.0078358

10000000
0.1328956
0.0882254
0.1261637
0.1860686
0.1382423
0.1263006
0.0014222
0.0201517

50000000
0.7393112
0.4989446
0.6946891
1.0110856
0.6989670
0.6960567
0.0065344
0.1153308

100000000
1.5508091
1.0383078
1.4342138
2.0776689
1.4325198
1.4353252
0.0128495
0.2426006

これをグラフにすると、以下の図のようになります。

あらかじめソートされたデータのグラフ_ICC_on_Linux.png

これもWindowsの場合と比べると、結果がばらついています。

std::thread、OpenMP、TBB、Cilkは、配列の要素数1000個の場合を例外とすれば、配列の要素数によらず、std::sortおよび並列化なしのクイックソートよりも遅くなっています。

tbb::parallel_sortは、std::sortおよび並列化なしのクイックソートと比べて速かったり遅かったりと、結果が安定しません。しかし、配列の要素数50万個以上では、std::sortと比べて桁違いに高速となります。配列の要素数が1億個の場合、tbb::parallel_sortはstd::sortと比べて約121倍、並列化なしのクイックソートと比べて約81倍の速度を叩きだしています。

Parallel STLのParallelism TSのstd::sortも、std::sortおよび並列化なしのクイックソートと比べて速かったり遅かったりと、結果が安定しません。しかし、配列の要素数50万個以上では、std::sortや並列化なしのクイックソートと比べて速度で優位に立ちます。配列の要素数が50万個以上の場合、Parallel STLのParallelism TSのstd::sortは、std::sortと比べて、6倍強~9倍弱程度高速であり、並列化なしのクイックソートと比べて4倍強~6倍強高速となっています。なお、tbb::parallel_sortとParallel STLのParallelism TSのstd::sortを比較した場合、配列の要素数50万個以上で、前者の方が後者より6倍弱~19倍弱程度高速です。


最初の1/4だけソートされたデータをソートする場合

最後に、最初の1/4だけソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を下の表にまとめました(単位は秒)。

配列の要素数
std::sort
クイックソート
std::thread
OpenMP
TBB
Cilk
tbb::parallel_sort
std::sort (Parallel STLのParallelism TS)

500
0.0000066
0.0000112
0.0000397
0.0000244
0.0000081
0.0011024
0.0000152
0.0000077

1000
0.0000197
0.0000301
0.0003606
0.0000661
0.0000334
0.0000285
0.0000313
0.0000230

5000
0.0001834
0.0002204
0.0008094
0.0002744
0.0002435
0.0008250
0.0057004
0.0001950

10000
0.0005186
0.0004692
0.0008333
0.0006225
0.0017368
0.0011144
0.0100914
0.0040570

50000
0.0022899
0.0024196
0.0029931
0.0030086
0.0038364
0.0149534
0.0014355
0.0002433

100000
0.0044776
0.0050154
0.0058148
0.0062692
0.0070468
0.0184688
0.0009401
0.0004650

500000
0.0254857
0.0283639
0.0304127
0.0351050
0.0368216
0.0302117
0.0044463
0.0024176

1000000
0.0536863
0.0581303
0.0619942
0.0721038
0.0697867
0.0611784
0.0087449
0.0050485

5000000
0.3034731
0.3197910
0.3412261
0.3942688
0.3508038
0.3398884
0.0455606
0.0287233

10000000
0.6240229
0.6740692
0.7082419
0.8167529
0.7195047
0.7077292
0.0954421
0.0625269

50000000
3.4533059
3.6878910
3.9124451
4.4901726
3.9031185
3.9100438
0.4825368
0.3402518

100000000
7.2506206
7.5568997
8.0023207
9.1349992
7.9543822
7.9711716
1.0085749
0.7051521

これをグラフにすると、以下の図のようになります。

最初の1_4だけソートされたデータのグラフ_ICC_on_Linux.png

これもWindowsの場合と比べると、結果がばらついています。

std::thread、OpenMP、TBB、Cilkは、配列の要素数500個や5000個の場合など、一部の例外を除き、std::sortおよび並列化なしのクイックソートよりも遅くなっています。

tbb:parallel_sortは、配列の要素数が10万個以上の場合、std::sortよりも5倍弱~7倍強程度高速であり、並列化なしのクイックソートより5倍強~7.5倍強程度高速です。

Parallel STLのParallelism TSのstd::sortは、配列の要素数が5万個以上の場合は、std::sortよりも9.5倍弱~10.5倍強程度高速であり、並列化なしのクイックソートより10倍弱~12倍弱程度高速です。また、Parallel STLのParallelism TSのstd::sortは、tbb::parallel_sortと比較しても高速であり、前者は後者に比べて、1.5倍弱~2.5倍弱程度高速です(配列の要素数が5000個および50000個の場合は例外で、後者より前者が圧倒的に高速になっています)。


まとめ

クイックソートを、C++11標準のstd::thread、OpenMP、TBB、Cilkでそれぞれスレッド並列化し、std::sort、TBBのtbb::parallel_sort、C++17のParallelism TSによるstd::sortと速度を比較しました。その結果、C++11標準のstd::thread、OpenMP、TBB、Cilkでスレッド並列化したクイックソートは、特にソート対象の配列の要素数が多い場合に、概ねstd::sortより良好なパフォーマンスを発揮するものの、TBBのtbb::parallel_sortやC++17のParallelism TSによるstd::sortの速度には劣ることがわかりました。また、クイックソートのスレッド並列化によって、むしろパフォーマンスが低下する場合があることも確かめられました。そして、TBBのtbb::parallel_sortとC++17のParallelism TSによるstd::sortの速度を比較すると、概ね後者の方が良好なパフォーマンスを示すことが分かりました。さらに、コンパイラがMSVCの場合、C++17のParallelism TSによるstd::sortについては、MSVC内蔵の実装よりも、Parallel STLの実装の方が、良好なパフォーマンスを発揮することが分かりました(前者については、TBBのtbb::parallel_sortよりも、若干ながらパフォーマンスの点で劣ることも確かめられました)。

従って、要素数が大きい配列を高速にソートしたい場合、Parallel STLが利用できる環境では、TBBのtbb::parallel_sortよりも、Parallel STLのParallelism TSによるstd::sortを積極的に利用するべきだと考えられます。Parallel STLが利用できない環境では、TBBのtbb::parallel_sortの利用が第一選択肢となるでしょう(コンパイラがMSVCの場合には、MSVC内蔵のParallelism TSによるstd::sortを利用するのも良いでしょう)。C++17のParallelism TSが、早期に各コンパイラに実装されることを期待します。


サンプルコードへのリンク

以上のコードのサンプルは、以下のGitHubリポジトリにアップロードしてあります。二条項BSDライセンスですので、どうぞご自由にご利用ください。

https://github.com/dc1394/parallelquicksort


参考サイト

[1] アルゴリズムとデータ構造編【整列】 第6章 クイックソート

[2] きままにブログ 【C++ちゃんは】クイックソートの非再帰版【かわいい】

[3] 分割統治

[4] C/C++ プログラムの変換

[5] Faith and Brave - C++で遊ぼう C++1z 並列アルゴリズムライブラリ


参考文献

[1] 菅原清文 『Cilkがやってきた-C/C++プログラマーのための並列プログラミング言語』 カットシステム(2011)