はじめに
この記事は、C++ Advent Calendar 2017 16日目の記事です。この記事では、C++17時代の並列ソートについて考えます。
2018年7月19日追記
Twitterにて、@yohhyさんが、以下のようにツイートされていました。確かに、Intel C++ Compiler (ICC)及びそのParallelism TSの実装が優秀である可能性は棄却できなかったので、内容を大幅に書き換えました。std::threadについては、良い方法が思いつかなかったのでそのままです…。
C++17時代の並列安定ソート https://t.co/KCw80gW01N ICC(+lib実装)が強いというお話のような あと`std::thread`版無駄にスレッドforkしすぎなのでペナルティ大きいね
— yoh (@yohhoy) 2018年2月11日
2021年2月23日追記
PCの構成変更（CPUがCore i7-7820XからCore i9-10980XEに変わりました）に伴い、記事を大幅に書き換えました。
並列ソートとは
高速なソートアルゴリズムとしては、例えばクイックソートがよく知られています（他にも、マージソートやヒープソートが、高速なソートのアルゴリズムとして知られています）。クイックソートでは、ソート対象の配列の要素数を$ 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® oneAPI Threading Building Blocks (oneTBB）を使った場合、Intel® Cilk™ Plusを使った場合（Intel® Cilk™ PlusはIntel自身によって非推奨(deprecated)とされたため、当該記事でも解説を削除しました）のそれぞれについて試してみたいと思います（クイックソートは、再帰処理を別スレッドで実行することで、簡単にスレッド並列化できます）。また、Microsoft 並列パターンライブラリ (PPL)に含まれるconcurrency::parallel_sortとconcurrency::parallel_buffered_sort、gcc 4.6.0以降のgccに含まれる__gnu_parallel::sort、Intel® oneTBBに含まれる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++;
// 部分ソートが小さくなりすぎるとシリアル実行のほうが効率が良くなるため
// 部分ソートの要素数が閾値以上の時だけ再帰させる
// かつ、現在の再帰の深さがSTDTHREADRECMAX( = 7)以下のときだけ再帰させる
if (num >= THRESHOLD && reci <= STDTHREADRECMAX) {
// 交点まで左右から入れ替えして交点を探す
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）以上の時かつ、現在の再帰の深さが7（上記のコードのSTDTHREADRECMAX）以下の時だけ、別スレッドで自分自身を呼び出して再帰させます（もしそうでなければ、再帰なしの通常のクイックソートの関数を呼び出します）。この閾値については議論の余地があると思うのですが、ここでは深入りせず、500に固定しておきます。また、「現在の再帰の深さが7以下の時だけ再帰させる」という点には根拠があり、物理コア数（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 2019でも同じです）。なおこのコードは、参考サイト[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を使った場合より若干複雑になっていますが、やっていることはほとんど同じです。std::threadの場合と異なるのは、現在の再帰の深さが物理コア数（上記のコードのNUMPHYSICALCORE）以下の時だけ、別スレッドで自分自身を呼び出して再帰させているところです。この、「現在の再帰の深さが物理コア数以下の時だけ再帰させる」という点には根拠があり、物理コア数（SMTの有無は関係ないようです）が異なる2台のPCで試行錯誤した結果、こうすると最もパフォーマンスが良くなることが分かりました。
また注意すべきことは、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® oneTBBによるスレッド並列化
次に、Intel® oneAPI Threading Building Blocks（以下では単にoneTBBと呼ぶことにします）を使ったスレッド並列化を試してみましょう。oneTBBは、Intelが公開しているマルチスレッド対応のC++テンプレートライブラリであり、gcc、MSVC、Clang、ICC (ICL)といった主要なコンパイラで利用できます。コードは以下のようになります（なおこのコードは、参考サイト[3]に載っているコードを参考にさせて頂きました）。
template < class RandomIter >
//! A template function.
/*!
指定された範囲の要素をクイックソートでソートする（oneTBBで並列化）
\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.
/*!
指定された範囲の要素をクイックソートでソートする（oneTBBで並列化）
\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>のインクルードが必要です。
Microsoft 並列パターンライブラリ (PPL)のparallel_sortとparallel_buffered_sortを使った並列ソート
Microsoft Visual C++ (MSVC)には、並列パターンライブラリ (PPL)という並列アルゴリズムライブラリが内蔵されており、それにはconcurrency::parallel_sortとconcurrency::parallel_buffered_sortという二つのスレッド並列化されたソート関数が含まれています。concurrency::parallel_sortとconcurrency::parallel_buffered_sortの違いは、公式ドキュメントに、以下のように記述されています。
parallel_sortアルゴリズムと parallel_buffered_sort アルゴリズムは両方とも比較ベースのアルゴリズムです。 つまり、要素を値で比較します。 parallel_sortアルゴリズムには追加のメモリ要件はなく、汎用的な並べ替えに適しています。 アルゴリズムのパフォーマンスは parallel_buffered_sort よりも優れ parallel_sort ていますが、O (N) 空間が必要です。
concurrency::parallel_sort及びconcurrency::parallel_buffered_sortは、以下のように、C++標準のSTLのstd::sort関数と同様に使用できます。
std::vector<int> v(1000000);
// concurrency::parallel_sort関数を用いて配列をソートする
concurrency::parallel_sort(v.begin(), v.end());
// concurrency::parallel_buffered_sort関数を用いて配列をソートする
concurrency::parallel_buffered_sort(v.begin(), v.end());
なお、concurrency::parallel_sort及びconcurrency::parallel_buffered_sortを使用するには、<ppl.h>のインクルードが必要です（従って、<ppl.h>のないgcc等のコンパイラでは、concurrency::parallel_sort及びconcurrency::parallel_buffered_sortは利用できません）。また、concurrency::parallel_sort及びconcurrency::parallel_buffered_sortは、不安定ソートであることに注意が必要です。
gccの__gnu_parallel::sortを使った並列ソート
gcc 4.6.0以降のgcc（及びICC (ICL)）では、Parallel Modeを標準でサポートしており、__gnu_parallel::sortというスレッド並列化されたソート関数が使用できるようです。__gnu_parallel::sortは、以下のように、C++標準のSTLのstd::sort関数と同様に使用できます。
std::vector<int> v(1000000);
// __gnu_parallel::sort関数を用いて配列をソートする
__gnu_parallel::sort(v.begin(), v.end());
なお、__gnu_parallel::sortを使用するには、<parallel/algorithm>のインクルードが必要です（従って、<parallel/algorithm>のないMSVC等のコンパイラでは、__gnu_parallel::sortは利用できません）。__gnu_parallel::sortについては、@Nabetaniさまの記事を参考にさせて頂きました。
oneTBBのtbb::parallel_sortを使った並列ソート
oneTBBには、tbb::parallel_sortという、スレッド並列化されたソート関数が含まれています。関数tbb::parallel_sortは、<tbb/parallel_sort.h>で、以下のように宣言されています（従って、tbb::parallel_sortを使用するには、<tbb/parallel_sort.h>のインクルードが必要です）。
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp)void parallel_sort(Range& rng)void parallel_sort(const Range& rng)void parallel_sort(Range& rng, const Compare& comp)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]や@yohhoyさまの記事
）、例えばstd::sortをスレッド並列化して実行するには、以下のコードのように記述します（なお、Parallelism TSによるstd::sortを使用するためには、<algorithm>ヘッダのインクルードの他に、<execution>ヘッダのインクルードが必要です）
。
std::vector<int> v(1000000);
// std::sortをスレッド並列化して実行する
std::sort(std::execution::par, v.begin(), v.end());
2021年2月23日現在、Parallelism TSをサポートしているコンパイラは、gcc 9以降とIntel C++ Compiler 18.0以降、それにMicrosoft Visual C++ (MSVC) 14.14 (Visual Studio 2017 version 15.7.3)以降のみです（参考）。しかし、実はIntel C++ CompilerにおけるParallelism TSの実装は、Parallel STLという名称でoneTBBに含まれているので、任意のコンパイラでParallelism TSを試すことができます。
並列ソートのパフォーマンス測定
それでは、以上のスレッド並列化されたソート関数のパフォーマンス（ソート時間）を、std::sortおよび並列化なしのクイックソートと比較してみましょう。またあわせて、concurrency::parallel_sort、concurrency::parallel_buffered_sort、__gnu_parallel::sort、tbb::parallel_sort及びParallelism TSによるstd::sortのソート時間も確認していきます。パフォーマンスを測定した環境は、
- CPU: Intel Core i9-10980XE (Cascade Lake-X, Hyper Threading ON (物理18コア論理36コア), Enhanced Intel SpeedStep Technology OFF, Turbo Mode OFF)
- メモリ: DDR4-3200 32GB (8GB×4)
であり、WindowsとLinuxでかなり挙動が異なるため、それぞれ別個に測定し、さらに、両方の環境において、それぞれ二つのコンパイラで測定しました。ここで、配列の要素を500個から1億個まで変化させ、ソートにかかった時間を測定しました。ただし、測定回数は10回とし、その平均を結果としました。Windowsの測定環境は、
- OS: Microsoft Windows 10 Pro (64bit) バージョン20H2
であり、次の二つのコンパイラで測定しました。
- Microsoft Visual C++ (MSVC) 14.28 (Visual Studio 2019 version 16.8.3) x64ビルド
- Intel oneAPI Base/HPC Toolkit (Intel C++ Compiler Classic 2021.1) on Visual Studio 2019 x64ビルド
また、Linuxの測定環境は
- OS: Linux Mint 19.3 Tricia (x64)
であり、次の二つのコンパイラで測定しました。
- gcc 10.1.0（コンパイル最適化オプション:
-O3 -mtune=native -march=native） - Intel oneAPI Base/HPC Toolkit (Intel C++ Compiler 2021.1 Beta 20201112)（コンパイル最適化オプション:
-O3 -xHOST -ipo）
また、Windows及びLinuxの両方において、使用しているTBB（とParallel STL）のバージョンは以下です。
- TBB (Parallel STL): Threading Building Blocks 2020 Update 3
Windows - Microsoft Visual C++ (MSVC) 14.28 (Visual Studio 2019 version 16.8.3) の場合
まず、OSがWindowsで、コンパイラがMSVC 14.28 (Visual Studio 2019 version 16.8.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 |
oneTBB | concurrency::parallel_sort |
concurrency::parallel_buffered_sort |
tbb::parallel_sort |
std::sort (MSVC内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.00001318 | 0.00002175 | 0.00071239 | 0.00009777 | 0.00020433 | 0.00001242 | 0.00001469 | 0.00005013 | 0.00001238 |
| 1000 | 0.00004092 | 0.00005288 | 0.00234455 | 0.00005051 | 0.00005516 | 0.00003662 | 0.00002719 | 0.00009678 | 0.00004281 |
| 5000 | 0.00029469 | 0.00034065 | 0.00682222 | 0.00015619 | 0.00036306 | 0.00057069 | 0.00010307 | 0.00020730 | 0.00006971 |
| 10000 | 0.00063568 | 0.00074123 | 0.00994159 | 0.00020565 | 0.00020590 | 0.00014363 | 0.00018543 | 0.00030369 | 0.00011526 |
| 50000 | 0.00379203 | 0.00420105 | 0.01790370 | 0.00085281 | 0.00082406 | 0.00027255 | 0.00074684 | 0.00081345 | 0.00030384 |
| 100000 | 0.00820191 | 0.00886423 | 0.02300214 | 0.00141718 | 0.00150773 | 0.00066354 | 0.00135290 | 0.00148473 | 0.00046142 |
| 500000 | 0.04879853 | 0.04919661 | 0.02220858 | 0.00826516 | 0.00751330 | 0.00272491 | 0.00747549 | 0.00813083 | 0.00240088 |
| 1000000 | 0.09861446 | 0.10215904 | 0.05498570 | 0.01623164 | 0.01468974 | 0.00518232 | 0.01491149 | 0.01616905 | 0.00508844 |
| 5000000 | 0.55152807 | 0.55601273 | 0.11392602 | 0.06911196 | 0.06559674 | 0.02390144 | 0.06816831 | 0.07287494 | 0.02511052 |
| 10000000 | 1.15359341 | 1.15858015 | 0.33491951 | 0.16353433 | 0.13691570 | 0.04880460 | 0.14039580 | 0.14862607 | 0.05339469 |
| 50000000 | 6.38480442 | 6.31654193 | 2.44405702 | 0.99286015 | 0.65662398 | 0.25902873 | 0.66838142 | 0.73324514 | 0.29168028 |
| 100000000 | 13.3694481 | 13.0421209 | 3.02522845 | 1.84632420 | 1.33672755 | 0.53118687 | 1.34774516 | 1.42626564 | 0.58486628 |
これをグラフにすると、以下の図のようになります（両対数グラフであることに注意してください）。
oneTBBは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります（配列の要素数が500～1000個の場合は、oneTBBはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートより遅くなっています）。原因は分かりませんが、std::threadはパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::sortや並列化なしのクイックソートよりも高速になります。
std::threadは、配列の要素数が50万個以上では、std::sortよりも2倍強～5倍弱程度高速で、並列化なしのクイックソートよりも2倍強～5倍弱程度高速であることが分かります。
また、oneTBBは、配列の要素数が5万個以上では、std::sortよりも4.5倍弱～8倍弱程度高速で、並列化なしのクイックソートよりも5倍弱～8倍程度高速であることが分かります。
concurrency::parallel_sortは配列の要素数が1万個以上でstd::sortよりも高速になり、配列の要素数が5万個以上では、std::sortより5倍弱～10倍程度高速です。
concurrency::parallel_buffered_sortは、配列の要素数が5000個の場合を除いてstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより12倍強～25倍強程度高速です。また、concurrency::parallel_sortとconcurrency::parallel_buffered_sortを比較すると、配列の要素数5万個以上で後者の方が2倍強～3倍強程度高速です。
tbb:parallel_sortは、配列の要素数が500個の場合を除いてstd::sortより高速で、配列の要素数が5万個以上の場合、std::sortより5倍強～10倍弱程度高速です。
MSVC内蔵のParallelism TSのstd::sortは、配列の要素数が5000個以上で、通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも4.5倍強～9.5倍弱程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも12.5倍弱～23倍弱程度高速です。また、Parallel STLのParallelism TSのstd::sortは、MSVC内蔵のParallelism TSのstd::sortと比較しても明らかに速く、配列の要素数1000個以上で前者は後者に比べて2.5倍弱～3.5倍弱程度高速です。
なお、concurrency::parallel_sortとtbb:parallel_sort、およびMSVC内蔵のParallelism TSのstd::sortは配列の要素数5万個以上で、またconcurrency::parallel_buffered_sortとParallel STLのParallelism TSのstd::sortは配列の要素数100万個以上で、それぞれ同じような傾向を示しているのが興味深いところです。
ここで重要なのは、concurrency::parallel_buffered_sortとParallel STLのParallelism TSのstd::sort以外は、物理18コア論理36コアの性能を十分に引き出せていないという点です。
あらかじめソートされたデータをソートする場合
極端な場合として、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。ここで言う「あらかじめソートされたデータが詰められた配列」とは、例えば、
std::vector<int> vec(1000000);
std::iota(vec.begin(), vec.end(), 1);
上記のコードのvecのような配列のことです。測定結果を以下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | concurrency::parallel_sort |
concurrency::parallel_buffered_sort |
tbb::parallel_sort |
std::sort (MSVC内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.00000307 | 0.00000509 | 0.00058254 | 0.00000774 | 0.00000314 | 0.00000295 | 0.00001627 | 0.00001761 | 0.00000302 |
| 1000 | 0.00000677 | 0.00000935 | 0.00375568 | 0.00004595 | 0.00000688 | 0.00000668 | 0.00001637 | 0.00002458 | 0.00001168 |
| 5000 | 0.00004766 | 0.00005406 | 0.00371235 | 0.00013484 | 0.00002574 | 0.00005671 | 0.00002247 | 0.00007484 | 0.00001769 |
| 10000 | 0.00010340 | 0.00011041 | 0.00388106 | 0.00023057 | 0.00004074 | 0.00008090 | 0.00002301 | 0.00010404 | 0.00001758 |
| 50000 | 0.00059292 | 0.00060295 | 0.00453021 | 0.00113469 | 0.00010556 | 0.00012897 | 0.00003130 | 0.00026633 | 0.00003590 |
| 100000 | 0.00126776 | 0.00124144 | 0.00547354 | 0.00226327 | 0.00022825 | 0.00018820 | 0.00005536 | 0.00046900 | 0.00006476 |
| 500000 | 0.00714573 | 0.00586650 | 0.01115249 | 0.00990226 | 0.00099048 | 0.00139635 | 0.00011507 | 0.00145383 | 0.00021975 |
| 1000000 | 0.01504460 | 0.01205253 | 0.01895176 | 0.01937848 | 0.00177589 | 0.00225820 | 0.00015723 | 0.00265732 | 0.00038652 |
| 5000000 | 0.08988829 | 0.07029580 | 0.08982978 | 0.10854766 | 0.00874033 | 0.00756397 | 0.00060665 | 0.01312235 | 0.00170440 |
| 10000000 | 0.18917622 | 0.14581794 | 0.18400168 | 0.23360370 | 0.01835980 | 0.01641386 | 0.00119227 | 0.02671932 | 0.00330901 |
| 50000000 | 1.03441588 | 0.81162785 | 0.99562288 | 1.27427845 | 0.09790289 | 0.08829596 | 0.00543397 | 0.13836282 | 0.01587578 |
| 100000000 | 2.15884035 | 1.66992758 | 2.04458313 | 2.59834304 | 0.20187728 | 0.18093735 | 0.01072578 | 0.28149567 | 0.03158325 |
これをグラフにすると、以下の図のようになります。
std::thread、oneTBBは、配列の要素数によらず、std::sortや並列化なしのクイックソートよりも遅くなっています（これは再帰と深い関係にあるようで、配列のデータがすでにソートされている場合は再帰させない（=並列化していない）クイックソートが高速になるようです）。std::threadは相変わらずなぜかパフォーマンスが悪いのですが、配列の要素数が50万個以上では、oneTBBとよく似た傾向を示すようになります。
concurrency::parallel_sortは配列の要素数が5000個以上でstd::sortよりも高速になり、配列の要素数が5万個以上では、std::sortより5.5倍強～10.5倍強程度高速です。
concurrency::parallel_buffered_sortは、配列の要素数が5000個の場合を除いてstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより5倍強～12倍弱程度高速です。また、concurrency::parallel_sortとconcurrency::parallel_buffered_sortを比較すると、結果がばらついていますが、配列の要素数500万個以上では、後者は前者に比べて10％～15％程度高速です。
tbb::parallel_sortについては興味深い結果が得られています。tbb::parallel_sortは、配列の要素数が1000個以下の場合こそstd::sortの後塵を拝しますが、要素数5000個で追い抜き、要素数500万個以上になると、std::sortと比べて文字通り桁違いに高速となります。配列の要素数が1億個の場合、tbb::parallel_sortはstd::sortと比べて約200倍の速度を叩きだしています。
MSVC内蔵のParallelism TSのstd::sortは、配列の要素数5万個未満では通常のstd::sortより低速ですが、配列の要素数5万個以上では、通常のstd::sortと比べて2倍強～7.5倍強程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortとほぼ同じかより高速です。配列の要素数が5万個以上の場合、Parallel STLのParallelism TSのstd::sortは、通常のstd::sortよりも16.5倍～68.5倍弱程度高速です。また、Parallel STLのParallelism TSのstd::sortは、MSVC内蔵のParallelism TSのstd::sortと比較しても明らかに速く、前者は後者に比べて2倍強～9倍弱程度高速です。
最初の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 |
oneTBB | concurrency::parallel_sort |
concurrency::parallel_buffered_sort |
tbb::parallel_sort |
std::sort (MSVC内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.00000958 | 0.00001576 | 0.00060568 | 0.00002472 | 0.00001133 | 0.00000632 | 0.00002424 | 0.00002842 | 0.00000890 |
| 1000 | 0.00002836 | 0.00003821 | 0.00395867 | 0.00008044 | 0.00002818 | 0.00002224 | 0.00003229 | 0.00004057 | 0.00003940 |
| 5000 | 0.00022075 | 0.00026673 | 0.00411038 | 0.00035019 | 0.00013249 | 0.00011577 | 0.00010594 | 0.00012008 | 0.00007370 |
| 10000 | 0.00048478 | 0.00056866 | 0.00449729 | 0.00069546 | 0.00017416 | 0.00014191 | 0.00015405 | 0.00019941 | 0.00011000 |
| 50000 | 0.00290343 | 0.00324571 | 0.00726639 | 0.00380127 | 0.00070767 | 0.00023259 | 0.00064964 | 0.00071237 | 0.00023584 |
| 100000 | 0.00622118 | 0.00670704 | 0.01093653 | 0.00784102 | 0.00120936 | 0.00041034 | 0.00114554 | 0.00120489 | 0.00037107 |
| 500000 | 0.03598171 | 0.03785570 | 0.04360556 | 0.04186674 | 0.00530704 | 0.00214819 | 0.00501100 | 0.00559972 | 0.00203525 |
| 1000000 | 0.07548933 | 0.07752350 | 0.08604809 | 0.08565530 | 0.01004125 | 0.00405515 | 0.01010880 | 0.01164502 | 0.00424175 |
| 5000000 | 0.43164224 | 0.42525635 | 0.45365901 | 0.47183879 | 0.05055948 | 0.01993187 | 0.05176170 | 0.05529853 | 0.02066321 |
| 10000000 | 0.89734139 | 0.89366528 | 0.93205479 | 0.98700895 | 0.10630381 | 0.03973773 | 0.10795078 | 0.11570737 | 0.04237652 |
| 50000000 | 5.02638007 | 4.88311624 | 5.12261367 | 5.33941850 | 0.51385921 | 0.21113416 | 0.52544114 | 0.57419973 | 0.22971017 |
| 100000000 | 10.4160926 | 9.97292378 | 10.4665373 | 10.9405047 | 1.06755931 | 0.43189203 | 1.10917960 | 1.22419790 | 0.46267870 |
これをグラフにすると、以下の図のようになります。
std::threadおよびoneTBBは、配列の要素数によらず、std::sortや並列化なしのクイックソートよりも遅くなっています（理由はやはり再帰にあると考えています）。std::threadは相変わらずなぜかパフォーマンスが悪いのですが、配列の要素数が50万個以上では、oneTBBとよく似た傾向を示すようになります。
concurrency::parallel_sortは、配列の要素数が500個の場合を除いてstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより4倍強～10倍弱程度高速です。
concurrency::parallel_buffered_sortは、配列の要素数によらずstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより12.5倍弱～24倍強程度高速です。また、concurrency::parallel_sortとconcurrency::parallel_buffered_sortを比較すると、配列の要素数5万個以上で後者の方が2.5倍弱～3倍強程度高速です。
tbb:parallel_sortは、配列の要素数が5000個以上でstd::sortより高速であり、配列の要素数が5万個以上の場合、std::sortより4.5倍弱～9.5倍強程度高速です。
MSVC内蔵のParallelism TSのstd::sortは、配列の要素数が5000個以上で、通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも4倍強～8.5倍程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも12.5倍弱～22.5倍程度高速です。また、Parallel STLのParallelism TSのstd::sortは、MSVC内蔵のParallelism TSのstd::sortと比較しても明らかに速く、配列の要素数5万個以上では、前者は後者に比べて2.5倍～3倍強程度高速です。
なお、concurrency::parallel_sortとtbb:parallel_sort、およびMSVC内蔵のParallelism TSのstd::sortは配列の要素数5万個以上で、またconcurrency::parallel_buffered_sortとParallel STLのParallelism TSのstd::sortも配列の要素数5万個以上で、それぞれ同じような傾向を示しているのが興味深いところです。
ここで重要なのは、concurrency::parallel_buffered_sortとParallel STLのParallelism TSのstd::sort以外は、物理18コア論理36コアの性能を十分に引き出せていないという点です。
Windows - Intel oneAPI Base/HPC Toolkit (Intel C++ Compiler Classic 2021.1) on Visual Studio 2019の場合
次に、OSがWindowsで、コンパイラがIntel C++ Compiler Classic 2021.1 (on Visual Studio 2019)の場合について述べたいと思います。
完全にシャッフルされたデータをソートする場合
まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します（MSVCの場合と同様ですので、コードは省略します）。測定結果を以下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | OpenMP | concurrency::parallel_sort |
concurrency::parallel_buffered_sort |
tbb::parallel_sort |
std::sort (MSVC内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.00001376 | 0.00002319 | 0.00075448 | 0.00091996 | 0.00014429 | 0.00025329 | 0.00001009 | 0.00001519 | 0.00012040 | 0.00001489 |
| 1000 | 0.00004801 | 0.00006330 | 0.00199088 | 0.00006705 | 0.00006014 | 0.00004995 | 0.00004041 | 0.00002647 | 0.00011463 | 0.00003785 |
| 5000 | 0.00034417 | 0.00042194 | 0.00791024 | 0.00016447 | 0.00014334 | 0.00053951 | 0.00056940 | 0.00010479 | 0.00029024 | 0.00007328 |
| 10000 | 0.00074935 | 0.00091179 | 0.01226892 | 0.00020386 | 0.00020504 | 0.00024142 | 0.00014604 | 0.00018491 | 0.00034090 | 0.00011412 |
| 50000 | 0.00457614 | 0.00513058 | 0.01991940 | 0.00083175 | 0.00084056 | 0.00079895 | 0.00026655 | 0.00075777 | 0.00094865 | 0.00027330 |
| 100000 | 0.00967307 | 0.01000837 | 0.02298702 | 0.00149128 | 0.00150210 | 0.00158364 | 0.00060742 | 0.00139593 | 0.00177028 | 0.00047124 |
| 500000 | 0.04878476 | 0.05258058 | 0.02249064 | 0.00833681 | 0.00820795 | 0.00763784 | 0.00309732 | 0.00703098 | 0.00770791 | 0.00218027 |
| 1000000 | 0.09830624 | 0.10696960 | 0.05358752 | 0.01568389 | 0.01582385 | 0.01454545 | 0.00519543 | 0.01397730 | 0.01567435 | 0.00483531 |
| 5000000 | 0.55332933 | 0.58236233 | 0.11925493 | 0.07206337 | 0.06838258 | 0.06439602 | 0.02498505 | 0.06316460 | 0.07151257 | 0.02256094 |
| 10000000 | 1.15783191 | 1.21634163 | 0.35061374 | 0.16953349 | 0.15793851 | 0.13701909 | 0.05015737 | 0.13251885 | 0.14654169 | 0.04905609 |
| 50000000 | 6.40519192 | 6.62750354 | 2.57209052 | 1.00999356 | 0.95637469 | 0.65481132 | 0.26417917 | 0.63473472 | 0.72172381 | 0.26431756 |
| 100000000 | 13.3606047 | 13.6746953 | 3.12231203 | 1.85096402 | 1.78456249 | 1.33324236 | 0.54365859 | 1.29467813 | 1.40676798 | 0.52945495 |
これをグラフにすると、以下の図のようになります。
oneTBB、OpenMPは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります（配列の要素数が500個および1000個の場合は、これらはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートより同じか遅くなっています）。原因は分かりませんが、std::threadはパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::sortや並列化なしのクイックソートよりも高速になります。また、OpenMP、oneTBBは、配列の要素数が5000個以上では概ね同じような傾向を示します。
std::threadは、配列の要素数が50万個以上では、std::sortよりも2倍弱～4.5倍強程度高速で、並列化なしのクイックソートよりも2倍強～5倍弱程度高速であることが分かります。
また、OpenMPは、配列の要素数が5万個以上では、std::sortよりも5.5倍～7.5倍強程度高速で、並列化なしのクイックソートよりも6倍強～8倍強程度高速であることが分かります。
また、oneTBBは、配列の要素数が5万個以上では、std::sortよりも5.5倍弱～8倍強程度高速で、並列化なしのクイックソートよりも6倍強～8.5倍程度高速であることが分かります。
concurrency::parallel_sortは、配列の要素数が1万個以上でstd::sortよりも高速になり、配列の要素数が5万個以上では、std::sortより5.5倍強～10倍程度高速です。
concurrency::parallel_buffered_sortは、配列の要素数が5000個の場合を除いてstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより16倍弱～24.5倍程度高速です。また、concurrency::parallel_sortとconcurrency::parallel_buffered_sortを比較すると、配列の要素数5万個以上で後者の方が2.5倍弱～3倍程度高速です。
tbb:parallel_sortは、配列の要素数が500個の場合を除いてstd::sortより高速で、配列の要素数が5万個以上の場合、std::sortより6倍～10.5倍弱程度高速です。
MSVC内蔵のParallelism TSのstd::sortは、配列の要素数が5000個以上で通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも5倍弱～9.5倍程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも16.5倍強～25倍強程度高速です。また、Parallel STLのParallelism TSのstd::sortは、MSVC内蔵のParallelism TSのstd::sortと比較しても明らかに速く、配列の要素数1000個以上では前者は後者に比べて2.5倍強～4倍弱程度高速です。
なお、concurrency::parallel_sortとtbb:parallel_sort、およびMSVC内蔵のParallelism TSのstd::sortは配列の要素数10万個以上で、またconcurrency::parallel_buffered_sortとParallel STLのParallelism TSのstd::sortは配列の要素数100万個以上で、それぞれ同じような傾向を示しているのが興味深いところです。
ここで重要なのは、concurrency::parallel_buffered_sortとParallel STLのParallelism TSのstd::sort以外は、物理18コア論理36コアの性能を十分に引き出せていないという点です。
あらかじめソートされたデータをソートする場合
次に、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します（MSVCの場合と同様ですので、コードは省略します）。測定結果を以下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | OpenMP | concurrency::parallel_sort |
concurrency::parallel_buffered_sort |
tbb::parallel_sort |
std::sort (MSVC内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.00000243 | 0.00000543 | 0.00058295 | 0.00002037 | 0.00001030 | 0.00000314 | 0.00000337 | 0.00001557 | 0.00002022 | 0.00000392 |
| 1000 | 0.00000808 | 0.00001319 | 0.00507136 | 0.00010359 | 0.00003258 | 0.00000745 | 0.00000729 | 0.00001670 | 0.00002911 | 0.00000722 |
| 5000 | 0.00005100 | 0.00006919 | 0.00528803 | 0.00017821 | 0.00014990 | 0.00002701 | 0.00005623 | 0.00002059 | 0.00006647 | 0.00001654 |
| 10000 | 0.00010665 | 0.00014153 | 0.00541873 | 0.00029849 | 0.00026583 | 0.00003693 | 0.00007889 | 0.00002117 | 0.00009678 | 0.00001815 |
| 50000 | 0.00057038 | 0.00081340 | 0.00651844 | 0.00134948 | 0.00131397 | 0.00009224 | 0.00014404 | 0.00003103 | 0.00026158 | 0.00003536 |
| 100000 | 0.00121033 | 0.00165696 | 0.00774262 | 0.00262686 | 0.00269860 | 0.00017181 | 0.00020874 | 0.00007126 | 0.00038643 | 0.00006152 |
| 500000 | 0.00455161 | 0.00600548 | 0.01269809 | 0.01243083 | 0.01243973 | 0.00080360 | 0.00137501 | 0.00010976 | 0.00130741 | 0.00021262 |
| 1000000 | 0.00965032 | 0.01248743 | 0.02158985 | 0.02464762 | 0.02389541 | 0.00142899 | 0.00212752 | 0.00016079 | 0.00202372 | 0.00028009 |
| 5000000 | 0.05876914 | 0.07254024 | 0.10162260 | 0.13515928 | 0.11439422 | 0.00644856 | 0.00690560 | 0.00054498 | 0.00945224 | 0.00123732 |
| 10000000 | 0.12173203 | 0.14941631 | 0.20737148 | 0.28566565 | 0.24051275 | 0.01362648 | 0.01474545 | 0.00105223 | 0.01905843 | 0.00240027 |
| 50000000 | 0.66856151 | 0.83818637 | 1.10693973 | 1.56141043 | 1.30178672 | 0.07473856 | 0.07948929 | 0.00493228 | 0.09557752 | 0.01151581 |
| 100000000 | 1.39901499 | 1.72926592 | 2.26971785 | 3.17833700 | 2.64292160 | 0.15213353 | 0.16316708 | 0.00961945 | 0.19347500 | 0.02289565 |
これをグラフにすると、以下の図のようになります。
std::thread、OpenMP、oneTBBは、配列の要素数によらず、std::sortおよび並列化なしのクイックソートよりも遅くなっています（これは再帰と深い関係にあるようで、配列のデータがすでにソートされている場合は再帰させない（=並列化していない）クイックソートが高速になるようです）。OpenMPおよびoneTBBについては、配列の要素数が5万個以上でよく似た傾向を示し、配列の要素数が50万個以上では、これにstd::threadが加わります。
concurrency::parallel_sortは、配列の要素数が500個の場合を除いてstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより5.5倍強～9倍強程度高速です。
concurrency::parallel_buffered_sortは、配列の要素数が500個および5000個の場合を除いてstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより3.5倍弱～8.5倍強程度高速です。また、concurrency::parallel_sortとconcurrency::parallel_buffered_sortを比較すると、興味深いことにMSVCの場合とは逆に、配列の要素数5万個以上で前者の方が6％～70％程度高速です。
tbb::parallel_sortについては興味深い結果が得られています。tbb::parallel_sortは、配列の要素数が1000個以下の場合こそstd::sortの後塵を拝しますが、要素数5000個で追い抜き、要素数500万個以上になると、std::sortと比べて文字通り桁違いに高速となります。配列の要素数が1億個の場合、tbb::parallel_sortはstd::sortと比べて約145倍の速度を叩きだしています。
MSVC内蔵のParallelism TSのstd::sortは、配列の要素数5万個未満では通常のstd::sortより低速ですが、配列の要素数5万個以上では、通常のstd::sortと比べて2倍強～7倍強程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortとほぼ同じかより高速です。配列の要素数が5万個以上の場合、Parallel STLのParallelism TSのstd::sortは、通常のstd::sortよりも16倍～61倍程度高速です。また、Parallel STLのParallelism TSのstd::sortは、MSVC内蔵のParallelism TSのstd::sortと比較しても明らかに速く、前者は後者に比べて4倍～8.5倍弱程度高速です。
最初の1/4だけソートされたデータをソートする場合
最後に、最初の1/4だけソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します（MSVCの場合と同様ですので、コードは省略します）。測定結果を以下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | OpenMP | concurrency::parallel_sort |
concurrency::parallel_buffered_sort |
tbb::parallel_sort |
std::sort (MSVC内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.00000972 | 0.00001609 | 0.00062351 | 0.00004767 | 0.00002217 | 0.00001282 | 0.00000827 | 0.00002619 | 0.00003765 | 0.00001819 |
| 1000 | 0.00003072 | 0.00004261 | 0.00529197 | 0.00013830 | 0.00008985 | 0.00003225 | 0.00002671 | 0.00003202 | 0.00005213 | 0.00003426 |
| 5000 | 0.00021854 | 0.00027852 | 0.00436043 | 0.00043447 | 0.00039765 | 0.00014851 | 0.00012136 | 0.00011494 | 0.00013944 | 0.00007972 |
| 10000 | 0.00062320 | 0.00072783 | 0.00593494 | 0.00083740 | 0.00080893 | 0.00018513 | 0.00015250 | 0.00017398 | 0.00022026 | 0.00010998 |
| 50000 | 0.00350872 | 0.00400621 | 0.00889343 | 0.00433466 | 0.00442436 | 0.00068052 | 0.00027097 | 0.00065008 | 0.00078216 | 0.00024719 |
| 100000 | 0.00745589 | 0.00695898 | 0.01151028 | 0.00902322 | 0.00919287 | 0.00119988 | 0.00052053 | 0.00118092 | 0.00133644 | 0.00040344 |
| 500000 | 0.03533036 | 0.03949567 | 0.04612071 | 0.04992970 | 0.04670485 | 0.00526466 | 0.00220954 | 0.00486710 | 0.00541780 | 0.00191960 |
| 1000000 | 0.07477285 | 0.08124220 | 0.09018366 | 0.10007097 | 0.09102273 | 0.00990956 | 0.00416297 | 0.00986677 | 0.01161180 | 0.00398081 |
| 5000000 | 0.42654531 | 0.44589733 | 0.47697425 | 0.55837376 | 0.49133750 | 0.05023164 | 0.02041120 | 0.05038793 | 0.05258825 | 0.01878973 |
| 10000000 | 0.88206925 | 0.93875969 | 0.97674067 | 1.16613291 | 1.02516354 | 0.10555216 | 0.04087031 | 0.10244951 | 0.11309692 | 0.03890668 |
| 50000000 | 4.91587561 | 5.11136818 | 5.36825519 | 6.29618250 | 5.55686468 | 0.51653972 | 0.21144673 | 0.49799756 | 0.54928895 | 0.20975608 |
| 100000000 | 10.1888631 | 10.4702813 | 10.9950215 | 12.8822863 | 11.4172326 | 1.06891488 | 0.43629046 | 1.05861960 | 1.19604108 | 0.41938319 |
これをグラフにすると、以下の図のようになります。
std::thread、OpenMPおよびoneTBBは、配列の要素数によらず、std::sortや並列化なしのクイックソートよりも遅くなっています（理由はやはり再帰にあると考えています）。OpenMPおよびoneTBBについては、配列の要素数が5万個以上でよく似た傾向を示し、配列の要素数が50万個以上では、これにstd::threadが加わります。
concurrency::parallel_sortは、配列の要素数が5000個以上のときにstd::sortよりも高速となり、配列の要素数が5万個以上では、std::sortより5倍強～9.5倍強程度高速です。
concurrency::parallel_buffered_sortは、配列の要素数によらずstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより13倍弱～23.5倍弱程度高速です。また、concurrency::parallel_sortとconcurrency::parallel_buffered_sortを比較すると、配列の要素数5万個以上では後者の方が2.5倍程度高速です。
tbb:parallel_sortは、配列の要素数が5000個以上でstd::sortより高速であり、配列の要素数が5万個以上の場合、std::sortより4.5倍弱～9.5倍強程度高速です。
MSVC内蔵のParallelism TSのstd::sortは、配列の要素数が5000個以上で、通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも4.5倍弱～9倍弱程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が5000個以上で通常のstd::sortより高速となり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも14倍強～24.5倍弱程度高速です。また、Parallel STLのParallelism TSのstd::sortは、MSVC内蔵のParallelism TSのstd::sortと比較しても明らかに速く、配列の要素数5万個以上では、前者は後者に比べて1.5倍～3.5倍弱程度高速です。
なお、concurrency::parallel_sortとtbb:parallel_sort、およびMSVC内蔵のParallelism TSのstd::sortは配列の要素数5万個以上で、またconcurrency::parallel_buffered_sortとParallel STLのParallelism TSのstd::sortも配列の要素数100万個以上で、それぞれ同じような傾向を示しているのが興味深いところです。
ここで重要なのは、concurrency::parallel_buffered_sortとParallel STLのParallelism TSのstd::sort以外は、物理18コア論理36コアの性能を十分に引き出せていないという点です。
Linux - gcc 10.1.0の場合
次に、OSがLinuxで、コンパイラがgcc 10.1.0の場合について述べたいと思います。
完全にシャッフルされたデータをソートする場合
まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | OpenMP | __gnu_parallel::sort |
tbb::parallel_sort |
std::sort (gcc内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.000024893 | 0.000045355 | 0.000147375 | 0.001303187 | 0.001283187 | 0.000020191 | 0.000021719 | 0.000012287 | 0.000007070 |
| 1000 | 0.000054624 | 0.000068457 | 0.000325976 | 0.000492963 | 0.000058507 | 0.000082524 | 0.000121616 | 0.000142849 | 0.000144507 |
| 5000 | 0.000284512 | 0.000289454 | 0.001049049 | 0.000439895 | 0.000354201 | 0.000110405 | 0.000588531 | 0.000080636 | 0.000073880 |
| 10000 | 0.000543226 | 0.000738104 | 0.001684484 | 0.000986895 | 0.000377292 | 0.000134368 | 0.000575619 | 0.000108722 | 0.000101165 |
| 50000 | 0.003796014 | 0.003964138 | 0.003732939 | 0.002027462 | 0.000838217 | 0.000258801 | 0.000933951 | 0.000244666 | 0.000229165 |
| 100000 | 0.006798136 | 0.007527757 | 0.005068177 | 0.003089555 | 0.001627792 | 0.000440390 | 0.001254653 | 0.000391025 | 0.000387948 |
| 500000 | 0.038368068 | 0.041868540 | 0.026757245 | 0.011499002 | 0.007606144 | 0.002230846 | 0.007342769 | 0.001992615 | 0.001880418 |
| 1000000 | 0.079269949 | 0.087378253 | 0.051152016 | 0.019009074 | 0.015533010 | 0.004195385 | 0.014554233 | 0.004145432 | 0.004047517 |
| 5000000 | 0.436924346 | 0.477954849 | 0.120260896 | 0.081459797 | 0.066547188 | 0.020812601 | 0.063031950 | 0.022211211 | 0.022075295 |
| 10000000 | 0.912132478 | 0.992930092 | 0.343423945 | 0.170977479 | 0.157149966 | 0.043468555 | 0.128640973 | 0.046800964 | 0.046194161 |
| 50000000 | 5.007958709 | 5.428374164 | 2.224191591 | 0.973801939 | 0.899763405 | 0.235642741 | 0.591759997 | 0.254803569 | 0.254855731 |
| 100000000 | 10.42357566 | 11.24008942 | 2.734871324 | 1.745823200 | 1.616119038 | 0.483397075 | 1.197179029 | 0.525707797 | 0.525958844 |
これをグラフにすると、以下の図のようになります。
oneTBBは、配列の要素数が1万個以上で、std::sortや並列化なしのクイックソートよりも高速になります（配列の要素数が500～5000個の場合は、oneTBBはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートとほぼ同じか遅くなっています）。std::threadとOpenMPは、oneTBBよりパフォーマンスが劣りますが、それでも配列の要素数が5万個以上で、std::sortや並列化なしのクイックソートより高速となっています。また、OpenMPとoneTBBは、配列の要素数が1千万個以上では概ね同じような傾向を示します。
std::threadは、配列の要素数が10万個以上では、std::sortよりも1.5倍弱～4倍弱程度高速で、並列化なしのクイックソートよりも1.5倍弱～4倍強程度高速であることが分かります。
また、OpenMPは、配列の要素数が5万個以上では、std::sortよりも2倍弱～6倍弱程度高速で、並列化なしのクイックソートよりも2倍弱～6.5倍弱程度高速であることが分かります。
また、oneTBBは、配列の要素数が5万個以上では、std::sortよりも4倍強～6.5倍強程度高速で、並列化なしのクイックソートよりも4.5倍強～7倍強程度高速であることが分かります。
__gnu_parallel::sortは、配列の要素数が1000個の場合を除いてstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより14.5倍強～21.5倍程度高速です。
tbb:parallel_sortは、配列の要素数が5万個以上でstd::sortより高速となり（配列の要素数500個の場合は例外です）、その場合、std::sortより4倍～8.5倍強程度高速です。また、配列の要素数が50万個～500万個では、著者のoneTBBで並列化したクイックソートの実装と良く似た傾向となることにも注意すべきでしょう。
gcc内蔵のParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも15.5倍～20倍弱程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも16.5倍強～20倍弱程度高速です。ここで、gcc内蔵のParallelism TSのstd::sortと、Parallel STLのParallelism TSのstd::sortを比較すると、配列の要素数が500個の場合を除き、ほとんど差が付いていません。これは、両者とも内部の実装にoneTBBを使っているからだと推測できます。
なお、__gnu_parallel::sortとgcc内蔵のParallelism TSのstd::sortおよびParallel STLのParallelism TSのstd::sortは、配列の要素数10万個以上で、同じような傾向を示しているのが興味深いところです。
ここで重要なのは、__gnu_parallel::sortとgcc内蔵のParallelism TSのstd::sortおよびParallel STLのParallelism TSのstd::sort以外は、物理18コア論理36コアの性能を十分に引き出せていないという点です。
あらかじめソートされたデータをソートする場合
次に、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | OpenMP | __gnu_parallel::sort |
tbb::parallel_sort |
std::sort (gcc内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.000009248 | 0.000008563 | 0.000057445 | 0.000051545 | 0.000008551 | 0.000006545 | 0.000050353 | 0.000006248 | 0.000006076 |
| 1000 | 0.000015091 | 0.000012300 | 0.001060127 | 0.000723860 | 0.000045074 | 0.000041156 | 0.000018246 | 0.000013769 | 0.000012820 |
| 5000 | 0.000075391 | 0.000058525 | 0.000740426 | 0.000339483 | 0.000102383 | 0.000044470 | 0.000080825 | 0.000062184 | 0.000061587 |
| 10000 | 0.000143271 | 0.000111855 | 0.000503061 | 0.000965391 | 0.000368186 | 0.000055209 | 0.000596777 | 0.000039109 | 0.000037501 |
| 50000 | 0.000630431 | 0.000504182 | 0.001743852 | 0.001815277 | 0.001182018 | 0.000095813 | 0.000422797 | 0.000138971 | 0.000096188 |
| 100000 | 0.001232023 | 0.001052275 | 0.003083894 | 0.003038320 | 0.002403256 | 0.000191890 | 0.000034294 | 0.000192291 | 0.000395492 |
| 500000 | 0.007267085 | 0.004927228 | 0.015070412 | 0.013670981 | 0.011443344 | 0.001173022 | 0.000196268 | 0.000579213 | 0.000428750 |
| 1000000 | 0.014598795 | 0.010229718 | 0.027464113 | 0.025529095 | 0.020764645 | 0.001738792 | 0.000167474 | 0.001359536 | 0.001300314 |
| 5000000 | 0.084962880 | 0.059992776 | 0.113234822 | 0.117512855 | 0.103529824 | 0.006092525 | 0.000526145 | 0.005800581 | 0.005451064 |
| 10000000 | 0.177730773 | 0.124715155 | 0.209775473 | 0.262443042 | 0.226390130 | 0.013161516 | 0.000897847 | 0.014032549 | 0.013003222 |
| 50000000 | 0.958579719 | 0.710772054 | 0.963596810 | 1.249448667 | 1.237445806 | 0.071036999 | 0.003984284 | 0.094905743 | 0.094380000 |
| 100000000 | 2.001940774 | 1.469157543 | 1.901582418 | 2.539568733 | 2.523412532 | 0.144788031 | 0.008063921 | 0.202743058 | 0.201624505 |
これをグラフにすると、以下の図のようになります。
std::thread、OpenMP、oneTBBは、配列の要素数によらず、std::sortおよび並列化なしのクイックソートよりも遅くなっています（oneTBBの配列の要素数500個の場合は例外です）。
__gnu_parallel::sortは、配列の要素数が1000個の場合を除いてstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより6倍強～14倍弱程度高速です。
tbb::parallel_sortについては興味深い結果が得られています。tbb::parallel_sortは、配列の要素数が1万個以下の場合こそstd::sortの後塵を拝しますが、要素数5万個で追い抜き、要素数500万個以上になると、std::sortと比べて文字通り桁違いに高速となります。配列の要素数が1億個の場合、tbb::parallel_sortはstd::sortと比べて約248倍の速度を叩きだしています。
gcc内蔵のParallelism TSのstd::sortは、配列の要素数によらず通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも4.5倍～12.5倍強程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数によらず通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも3倍強～17倍弱程度高速です。ここで、gcc内蔵のParallelism TSのstd::sortと、Parallel STLのParallelism TSのstd::sortを比較すると、配列の要素数が5万個～50万個の場合を除き、ほとんど差が付いていません。
最初の1/4だけソートされたデータをソートする場合
次に、最初の1/4だけソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | OpenMP | __gnu_parallel::sort |
tbb::parallel_sort |
std::sort (gcc内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.000007999 | 0.000012527 | 0.000072679 | 0.000573981 | 0.000015400 | 0.000016251 | 0.000028808 | 0.000011755 | 0.000007506 |
| 1000 | 0.000038320 | 0.000051256 | 0.001029965 | 0.000387196 | 0.000047371 | 0.000036706 | 0.000040137 | 0.000029518 | 0.000020574 |
| 5000 | 0.000205600 | 0.000244940 | 0.000714480 | 0.001684520 | 0.000414903 | 0.000058185 | 0.000541605 | 0.000063834 | 0.000064833 |
| 10000 | 0.000448152 | 0.000535407 | 0.001358318 | 0.001207050 | 0.000685498 | 0.000081991 | 0.000573475 | 0.000093102 | 0.000087951 |
| 50000 | 0.002563722 | 0.002781821 | 0.006999927 | 0.004370355 | 0.003866289 | 0.000405421 | 0.001108786 | 0.000196917 | 0.000197414 |
| 100000 | 0.005142907 | 0.005758782 | 0.011975298 | 0.008785228 | 0.009094931 | 0.000943512 | 0.001885065 | 0.000320599 | 0.000319423 |
| 500000 | 0.029549368 | 0.032615256 | 0.049518715 | 0.043799875 | 0.038096904 | 0.002636391 | 0.005171744 | 0.001893438 | 0.001439164 |
| 1000000 | 0.062002932 | 0.066504734 | 0.091540518 | 0.085118637 | 0.077590061 | 0.004491798 | 0.010919085 | 0.003214409 | 0.002968447 |
| 5000000 | 0.345513623 | 0.365909120 | 0.418825904 | 0.426546339 | 0.413612506 | 0.020477521 | 0.053167786 | 0.017788946 | 0.017460829 |
| 10000000 | 0.712287194 | 0.766978920 | 0.848350508 | 0.897527905 | 0.867349943 | 0.045391304 | 0.107509069 | 0.037712142 | 0.036901475 |
| 50000000 | 3.911522626 | 4.204337674 | 4.464761621 | 4.738570329 | 4.731474379 | 0.233796971 | 0.473303429 | 0.204629000 | 0.204489933 |
| 100000000 | 8.224854899 | 8.590978162 | 9.071001326 | 9.671348334 | 9.669968041 | 0.470663525 | 0.992487581 | 0.420992919 | 0.421025682 |
これをグラフにすると、以下の図のようになります。
std::thread、OpenMP、oneTBBは、配列の要素数によらず、std::sortおよび並列化なしのクイックソートよりも遅くなっています（oneTBBの配列の要素数1000個の場合は例外です）。
__gnu_parallel::sortは、配列の要素数が1000個以上のときにstd::sortよりも高速となり、配列の要素数が5万個以上では、std::sortより5.5倍～17.5倍程度高速です。
tbb:parallel_sortは、配列の要素数が5万個以上でstd::sortより高速であり、その場合、std::sortより2.5倍弱～8.5倍弱程度高速です。
gcc内蔵のParallelism TSのstd::sortは、配列の要素数が5000個の場合を除いて通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも2倍～21倍強程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が5000個の場合を除いて通常のstd::sortより高速であり、配列の要素数が10万個以上の場合は、通常のstd::sortよりも5倍弱～21.5倍ｊｙ程度高速です。ここで、gcc内蔵のParallelism TSのstd::sortと、Parallel STLのParallelism TSのstd::sortを比較すると、配列の要素数が500個、1000個および50万個の場合を除いて、ほとんど差が付いていません。
なお、__gnu_parallel::sortとgcc内蔵のParallelism TSのstd::sortおよびParallel STLのParallelism TSのstd::sortは、配列の要素数5000万個以上で、同じような傾向を示しているのが興味深いところです。
ここで重要なのは、__gnu_parallel::sortとgcc内蔵のParallelism TSのstd::sortおよびParallel STLのParallelism TSのstd::sort以外は、物理18コア論理36コアの性能を十分に引き出せていないという点です。
Linux - Intel C++ Compiler 2021.1 Beta 20201112の場合
次に、OSがLinuxで、コンパイラがIntel C++ Compiler 2021.1 Beta 20201112の場合について述べたいと思います。
完全にシャッフルされたデータをソートする場合
まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | OpenMP | __gnu_parallel::sort |
tbb::parallel_sort |
std::sort (gcc内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.000025689 | 0.000058553 | 0.000121540 | 0.002044653 | 0.000107056 | 0.000012771 | 0.000030127 | 0.000012155 | 0.000005980 |
| 1000 | 0.000039999 | 0.000064659 | 0.004807957 | 0.000160972 | 0.000062751 | 0.000161289 | 0.000024299 | 0.000033136 | 0.000033186 |
| 5000 | 0.000316549 | 0.000403684 | 0.015601658 | 0.000176464 | 0.000205556 | 0.000210740 | 0.000546728 | 0.000780904 | 0.000605110 |
| 10000 | 0.000683291 | 0.000873816 | 0.014804904 | 0.000256801 | 0.000319258 | 0.000228502 | 0.000274334 | 0.000276421 | 0.000598442 |
| 50000 | 0.003939438 | 0.004960543 | 0.009439639 | 0.001284400 | 0.002422699 | 0.000511762 | 0.002899292 | 0.001974871 | 0.003686968 |
| 100000 | 0.008167836 | 0.009071857 | 0.004771090 | 0.002203241 | 0.003781088 | 0.000883468 | 0.002061568 | 0.001914937 | 0.001692179 |
| 500000 | 0.042222046 | 0.049906606 | 0.028210675 | 0.012439635 | 0.017703785 | 0.002795401 | 0.010053336 | 0.004527517 | 0.003341903 |
| 1000000 | 0.084323676 | 0.104300800 | 0.056229170 | 0.019668491 | 0.020255413 | 0.009411207 | 0.016724185 | 0.004029627 | 0.004011723 |
| 5000000 | 0.468883588 | 0.572857889 | 0.132602505 | 0.078556040 | 0.076247055 | 0.022528785 | 0.066907700 | 0.022125693 | 0.021926836 |
| 10000000 | 0.976607356 | 1.195733468 | 0.391055555 | 0.188120067 | 0.173950368 | 0.047370247 | 0.136363531 | 0.046609787 | 0.046250940 |
| 50000000 | 5.362249997 | 6.533907828 | 2.608209497 | 1.119087966 | 0.994068929 | 0.256729193 | 0.598654640 | 0.256418853 | 0.256207412 |
| 100000000 | 11.15938168 | 13.51821517 | 3.153370447 | 2.000575511 | 1.798881753 | 0.527765557 | 1.177411647 | 0.525271920 | 0.524588384 |
これをグラフにすると、以下の図のようになります。
oneTBBとOpenMPは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります（配列の要素数が500～1000個の場合は、oneTBBとOpenMPはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートとほぼ同じか遅くなっています）。std::threadは、oneTBBとOpenMPよりパフォーマンスが劣りますが、それでも配列の要素数が10万個以上で、std::sortや並列化なしのクイックソートより高速となっています。また、OpenMPとoneTBBは、配列の要素数が100万個以上では概ね同じような傾向を示します。
std::threadは、配列の要素数が10万個以上では、std::sortよりも1.5倍～3.5倍程度高速で、並列化なしのクイックソートよりも2倍弱～4.5倍弱程度高速であることが分かります。
また、OpenMPは、配列の要素数が5万個以上では、std::sortよりも3倍～5.5倍強程度高速で、並列化なしのクイックソートよりも4倍弱～7.5倍弱程度高速であることが分かります。
また、oneTBBは、配列の要素数が5万個以上では、std::sortよりも1.5倍強～6倍強程度高速で、並列化なしのクイックソートよりも2倍～7.5倍程度高速であることが分かります。
__gnu_parallel::sortは、配列の要素数が1000個の場合を除いてstd::sortよりも高速であり、配列の要素数が5万個以上では、std::sortより7.5倍強～21倍強程度高速です。
tbb:parallel_sortは、配列の要素数500個の場合と5000個の場合を除きstd::sortより高速であり、配列の要素数が5万個以上の場合、std::sortより1.5倍弱～9.5倍弱程度高速です。
gcc内蔵のParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも15.5倍～20倍弱程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりも16.5倍強～20倍弱程度高速です。ここで、gcc内蔵のParallelism TSのstd::sortと、Parallel STLのParallelism TSのstd::sortを比較すると、配列の要素数が500個の場合を除き、ほとんど差が付いていません。
なお、__gnu_parallel::sortとgcc内蔵のParallelism TSのstd::sortおよびParallel STLのParallelism TSのstd::sortは、配列の要素数10万個以上で、同じような傾向を示しているのが興味深いところです。
ここで重要なのは、__gnu_parallel::sortとgcc内蔵のParallelism TSのstd::sortおよびParallel STLのParallelism TSのstd::sort以外は、物理18コア論理36コアの性能を十分に引き出せていないという点です。
あらかじめソートされたデータをソートする場合
次に、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を以下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | OpenMP | __gnu_parallel::sort |
tbb::parallel_sort |
std::sort (gcc内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.000003282 | 0.000003352 | 0.000069174 | 0.000133287 | 0.000007147 | 0.000004766 | 0.000035715 | 0.000004394 | 0.000004335 |
| 1000 | 0.000009629 | 0.000011272 | 0.007042858 | 0.000080021 | 0.000043733 | 0.000041424 | 0.000017686 | 0.000010666 | 0.000012396 |
| 5000 | 0.000064173 | 0.000068299 | 0.000535111 | 0.000199917 | 0.000162961 | 0.000133052 | 0.000030809 | 0.000034360 | 0.000065055 |
| 10000 | 0.000135993 | 0.000143468 | 0.000664121 | 0.001006947 | 0.000328658 | 0.000054175 | 0.001682509 | 0.001148580 | 0.000035217 |
| 50000 | 0.000756845 | 0.000830355 | 0.002160037 | 0.001727517 | 0.001643954 | 0.000101128 | 0.000827913 | 0.001306045 | 0.000750862 |
| 100000 | 0.001568266 | 0.001809853 | 0.002831768 | 0.003446964 | 0.003418316 | 0.000153676 | 0.001259073 | 0.001491672 | 0.000260064 |
| 500000 | 0.008867345 | 0.007211394 | 0.015120081 | 0.017613053 | 0.017291636 | 0.000629511 | 0.001283779 | 0.002522785 | 0.001725311 |
| 1000000 | 0.016085290 | 0.010148077 | 0.030372876 | 0.035374176 | 0.030629912 | 0.001901983 | 0.000218614 | 0.001862381 | 0.001392607 |
| 5000000 | 0.078110732 | 0.057316201 | 0.115281403 | 0.184032865 | 0.124040338 | 0.006580238 | 0.000787029 | 0.005868394 | 0.005358366 |
| 10000000 | 0.159198415 | 0.120340071 | 0.218178625 | 0.383582731 | 0.252717678 | 0.013532550 | 0.002446753 | 0.014788552 | 0.014065383 |
| 50000000 | 0.871642677 | 0.684538380 | 0.974112745 | 2.086925451 | 1.331352057 | 0.075912860 | 0.009615410 | 0.110006732 | 0.109626545 |
| 100000000 | 1.821219244 | 1.418156866 | 1.948518150 | 4.201177520 | 2.725362130 | 0.158235994 | 0.014722463 | 0.237574335 | 0.237342465 |
これをグラフにすると、以下の図のようになります。
std::thread、OpenMP、oneTBBは、配列の要素数によらず、std::sortおよび並列化なしのクイックソートよりも遅くなっています（oneTBBの配列の要素数500個の場合は例外です）。
__gnu_parallel::sortは、配列の要素数が1万個以上でstd::sortよりも高速となり、配列の要素数が5万個以上では、std::sortより7.5倍弱～14倍程度高速です。
tbb::parallel_sortについては興味深い結果が得られています。tbb::parallel_sortは、配列の要素数が5万個以下の場合こそstd::sortの後塵を拝しますが（配列の要素数5000個の場合は例外です）、要素数10万個で追い抜き、要素数1億個になると、std::sortと比べて文字通り桁違いに高速となります。配列の要素数が1億個の場合、tbb::parallel_sortはstd::sortと比べて約123倍の速度を叩きだしています。
gcc内蔵のParallelism TSのstd::sortは、配列の要素数10万個以上で通常のstd::sortより高速となり（配列の要素数5000個の場合は例外です）、配列の要素数が50万個以上の場合は、通常のstd::sortよりも3.5倍～13.5倍弱程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数1万個以上で通常のstd::sortより高速となり、配列の要素数が10万個以上の場合は、通常のstd::sortよりも5倍強～14.5倍強程度高速です。ここで、gcc内蔵のParallelism TSのstd::sortと、Parallel STLのParallelism TSのstd::sortを比較すると、配列の要素数が500万個～1億個の場合、ほとんど差が付いていません。
最初の1/4だけソートされたデータをソートする場合
最後に、最初の1/4だけソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。測定結果を下の表にまとめました（単位は秒）。
| 配列の要素数 | std::sort |
クイックソート | std::thread |
oneTBB | OpenMP | __gnu_parallel::sort |
tbb::parallel_sort |
std::sort (gcc内蔵のParallelism TS) |
std::sort (Parallel STLのParallelism TS) |
|---|---|---|---|---|---|---|---|---|---|
| 500 | 0.000007706 | 0.000015263 | 0.000053213 | 0.000047440 | 0.000017218 | 0.000010766 | 0.000021032 | 0.000008041 | 0.000005274 |
| 1000 | 0.000029306 | 0.000044540 | 0.004245274 | 0.000124808 | 0.000082968 | 0.000046516 | 0.000030350 | 0.000032147 | 0.000031442 |
| 5000 | 0.000244820 | 0.000317467 | 0.001325778 | 0.000449512 | 0.000412214 | 0.000063254 | 0.001363891 | 0.000193053 | 0.000374510 |
| 10000 | 0.000536321 | 0.000747564 | 0.001179986 | 0.001265360 | 0.000920655 | 0.000080334 | 0.001111234 | 0.000564711 | 0.000414447 |
| 50000 | 0.003450923 | 0.003868563 | 0.007395579 | 0.004651474 | 0.004643843 | 0.000496041 | 0.002098822 | 0.001528007 | 0.001383688 |
| 100000 | 0.006440132 | 0.007786735 | 0.013702469 | 0.010447039 | 0.010017910 | 0.000437327 | 0.003019716 | 0.002711944 | 0.000953512 |
| 500000 | 0.032562810 | 0.038483162 | 0.056993222 | 0.054281341 | 0.052323510 | 0.002865946 | 0.004664892 | 0.001639682 | 0.002110837 |
| 1000000 | 0.066206898 | 0.079052754 | 0.106787189 | 0.108613353 | 0.097480725 | 0.004963110 | 0.010552541 | 0.006291424 | 0.003201046 |
| 5000000 | 0.365672464 | 0.435018580 | 0.505818912 | 0.594722824 | 0.506228038 | 0.022780767 | 0.053374002 | 0.017522740 | 0.017360572 |
| 10000000 | 0.751883886 | 0.915703001 | 1.013385013 | 1.230415664 | 1.046327847 | 0.047637249 | 0.110283544 | 0.038032078 | 0.037605291 |
| 50000000 | 4.157433346 | 5.012947601 | 5.311661914 | 6.593458801 | 5.660472799 | 0.251225217 | 0.469074786 | 0.207134030 | 0.207180895 |
| 100000000 | 8.714649411 | 10.29277946 | 10.87330710 | 13.73341049 | 11.58778269 | 0.519999306 | 0.982956244 | 0.424492841 | 0.423804291 |
これをグラフにすると、以下の図のようになります。
std::thread、OpenMP、oneTBBは、配列の要素数によらず、std::sortおよび並列化なしのクイックソートよりも遅くなっています。
__gnu_parallel::sortは、配列の要素数が5000個以上のときにstd::sortよりも高速となり、配列の要素数が5万個以上では、std::sortより7倍弱～14.5倍強程度高速です。
tbb:parallel_sortは、配列の要素数が5万個以上でstd::sortより高速であり、その場合、std::sortより1.5倍強～9倍弱程度高速です。
gcc内蔵のParallelism TSのstd::sortは、配列の要素数が5万個以上で通常のstd::sortより高速となり（配列の要素数5000個の場合は例外です）、その場合、通常のstd::sortよりも2.5倍弱～21倍弱程度高速です。
Parallel STLのParallelism TSのstd::sortは、配列の要素数が1万個以上で、通常のstd::sortより高速となり（配列の要素数500個の場合は例外です）、配列の要素数が5万個以上の場合は、通常のstd::sortよりも2.5倍～21倍程度高速です。ここで、gcc内蔵のParallelism TSのstd::sortと、Parallel STLのParallelism TSのstd::sortを比較すると、配列の要素数が500万個～1億個の場合、ほとんど差が付いていません。
ここで重要なのは、__gnu_parallel::sortとgcc内蔵のParallelism TSのstd::sortおよびParallel STLのParallelism TSのstd::sort以外は、物理18コア論理36コアの性能を十分に引き出せていないという点です。
まとめ
クイックソートを、C++11標準のstd::thread、OpenMP、oneTBBでそれぞれスレッド並列化し、std::sortと速度を比較しました。また、MSVCのconcurrency::parallel_sort、MSVCのconcurrency::parallel_buffered_sort、gccの__gnu_parallel::sort、tbb::parallel_sort、MSVC内蔵のParallelism TSによるstd::sort、gcc内蔵のParallelism TSによるstd::sort、Parallel STLのParallelism TSによるstd::sortと通常のstd::sortの速度を比較しました。その結果、C++11標準のstd::thread、OpenMP、oneTBBでスレッド並列化したクイックソートは、特にソート対象の配列の要素数が多い場合に、概ねstd::sortより良好なパフォーマンスを発揮するものの、物理18コア論理36コアの性能を十分に引き出せないことが分かりました。また、クイックソートのスレッド並列化によって、むしろパフォーマンスが低下する場合があることも確かめられました。
さらに、コンパイラがMSVCの場合、C++17のParallelism TSによるstd::sortについては、MSVC内蔵の実装よりも、Parallel STLの実装の方が良好なパフォーマンスを発揮すること、MSVCのconcurrency::parallel_buffered_sortは、Parallel STLのParallelism TSによるstd::sortと同等のパフォーマンスを発揮することが分かりました。
また、コンパイラがgccの場合、C++17のParallelism TSによるstd::sortについては、gcc内蔵の実装とParallel STLの実装で、特に配列のサイズが大きい場合にパフォーマンスに大差がないこと、gccの__gnu_parallel::sortは、C++17のParallelism TSによるstd::sortとほぼ同等のパフォーマンスを発揮することが分かりました。
従って、要素数が大きい配列を高速にソートしたい場合、MSVCの場合はconcurrency::parallel_buffered_sortを利用するか、Parallel STLのParallelism TSによるstd::sortを利用するべきことが分かりました。また、コンパイラがgccの場合は、gcc内蔵のParallelism TSによるstd::sortをそのまま利用してもいいし、__gnu_parallel::sortを利用すれば良いことが分かりました。
サンプルコードへのリンク
以上のコードのサンプルは、以下のGitHubリポジトリにアップロードしてあります。二条項BSDライセンスですので、どうぞご自由にご利用ください。
https://github.com/dc1394/parallelquicksort
#参考サイト
[1] アルゴリズムとデータ構造編【整列】 第６章 クイックソート
[2] きままにブログ 【C++ちゃんは】クイックソートの非再帰版【かわいい】
[3] 分割統治
[4] C/C++ プログラムの変換
[5] Faith and Brave - C++で遊ぼう C++1z 並列アルゴリズムライブラリ