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

# はじめに
この記事は、[C++17時代の並列ソート](https://qiita.com/dc1394/items/d2b8de600a304664cdb5)（C++ Advent Calendar 2017 16日目）の記事の続きです。この記事では、C++17時代の並列安定ソートについて考えます。

<font color="Red">2018年9月2日追記</font>
Twitterにて、[@yohhy](https://twitter.com/yohhoy)さんが、以下のようにツイートされていました。確かに、Intel C++ Compiler (ICC)及びそのParallelism TSの実装が優秀である可能性は棄却できなかったので、内容を大幅に書き換えました。std::threadについては、良い方法が思いつかなかったのでそのままです…。

<blockquote class="twitter-tweet" data-cards="hidden" data-lang="ja"><p lang="ja" dir="ltr">C++17時代の並列安定ソート <a href="https://t.co/KCw80gW01N">https://t.co/KCw80gW01N</a> ICC(+lib実装)が強いというお話のような あとstd::thread版無駄にスレッドforkしすぎなのでペナルティ大きいね</p>&mdash; yoh (@yohhoy) <a href="https://twitter.com/yohhoy/status/962649801224478721?ref_src=twsrc%5Etfw">2018年2月11日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

# 並列安定ソートとは
高速な安定ソートアルゴリズムとしては、例えばマージソートがよく知られています。マージソートでは、ソート対象の配列の要素数を$ N $とすると、ソート時間のオーダーは（ランダウの記号を使って）、$ O(N\log N) $と書けます。
マージソートは、安定ソートとしては十二分に高速なアルゴリズムであり、残念ながら、これ以上高速な安定ソートアルゴリズムの発明はあまり望めそうにもありません（仮に、マージソート以上に高速な安定ソートアルゴリズムが開発されたとしても、ソート時間のオーダーは$ O(N) $未満にはならないと思います）。
従って、安定ソートの高速化を行うには、マルチコアを使った、マージソートのスレッド並列化が有効でしょう。昨今のCPUには、少なくとも2個以上のCPUコアが内蔵されており、これを活用しない手はありません。

# 通常のマージソート
マージソートのスレッド並列化を考える前に、まず通常のマージソートの実装について触れておきます。マージソートの詳細な解説は他に譲りますが（例えば[参考サイト[1]](http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/sort/007.html "アルゴリズムとデータ構造編【整列】　第７章　マージソート")）、例えばマージソートの実装は、以下のコードのようになります。なお、以下のコードは、[参考サイト[2]](https://qiita.com/rinse_/items/0c29a4d21131c88065ef "C++で様々なソートアルゴリズムを実装する")に載っているコードを参考にさせて頂きました。

```cpp
template < class RandomIter >
//! A template function.
/*!
    指定された範囲の要素をマージソートでソートする
    \param first 範囲の下限
    \param last 範囲の上限
*/
void merge_sort(RandomIter first, RandomIter last)
{
    // 部分ソートの要素数
    auto const len = std::distance(first, last);

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

    auto const middle = first + len / 2;

    // 下部をソート（再帰）
    merge_sort(first, middle);

    // 上部をソート（再帰）
    merge_sort(middle, last);

    // ソートされた下部と上部をマージ
    std::inplace_merge(first, middle, last);
}
```

# 並列安定ソートの実装
以下で、このマージソートのコードのスレッド並列化を、C++11標準のstd::threadを使った場合、OpenMPを使った場合、[Intel® Threading Building Blocks (Intel® TBB）](https://www.threadingbuildingblocks.org/ "https://www.threadingbuildingblocks.org/")を使った場合、[Intel® Cilk™ Plus](https://www.cilkplus.org/ "https://www.cilkplus.org/")を使った場合のそれぞれについて試してみたいと思います（マージソートは、再帰処理を別スレッドで実行することで、簡単にスレッド並列化できます）。また、C++17のParallelism TSによるstd::stable_sortにも触れたいと思います。なお、std::thread、OpenMP、Intel® TBB（以下では単にTBBと呼ぶことにします）、Intel® Cilk™ Plus（以下では単にCilkと呼ぶことにします）については、前回の記事で解説済みなので、この記事ではこれらの解説は行わないことにします。

## 安定ソートのC++11標準のstd::threadによるスレッド並列化
まず、C++11標準に含まれるstd::threadを使ったスレッド並列化（以下では単にstd::threadと呼びます）を試してみましょう。サンプルコードは以下のようになります。なおこのコードは、[参考サイト[3]](https://jp.xlsoft.com/documents/intel/tbb/2017/tbb2017_ugref/tbb_userguide/Design_Patterns/Divide_and_Conquer.html "分割統治")に載っているコードを参考にさせて頂きました。

```cpp
template < class RandomIter >
//! A template function.
/*!
    指定された範囲の要素を安定ソートする（std::threadで並列化）
    \param first 範囲の下限
    \param last 範囲の上限
*/
inline void stable_sort_thread(RandomIter first, RandomIter last)
{
    // 再帰ありの並列安定ソートの関数を呼び出す
    stable_sort_thread(first, last, 0);
}

template < class RandomIter >
//! A template function.
/*!
    指定された範囲の要素を安定ソートする
    \param first 範囲の下限
    \param last 範囲の上限
    \param reci 現在の再帰の深さ
*/
void stable_sort_thread(RandomIter first, RandomIter last, std::int32_t reci)
{
    // 部分ソートの要素数
    auto const len = std::distance(first, last);

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

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

    // 現在の再帰の深さが閾値以下のときだけ並列化させる
    if (reci <= THRESHOLD) {
        auto const middle = first + len / 2;

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

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

        // 二つのスレッドの終了を待機
        th1.join();
        th2.join();

        // ソートされた下部と上部をマージ
        std::inplace_merge(first, middle, last);
    }
    else {
        // C++標準の安定ソートの関数を呼び出す
        std::stable_sort(first, last);
    }
}
```

上記コードの通り、現在の再帰の深さが閾値（上記コードにおける`THRESHOLD`）以下の時だけ、別スレッドで自分自身を呼び出して再帰させ、もしそうでなければ、C++標準の安定ソートの関数を呼び出します（なお、C++標準の安定ソートの関数の実装は、（私が確認した限りでは）単純に再帰を用いたマージソートではないようです）。この閾値については3が良いようです。この値には根拠があり、物理コア数（SMTの有無は関係ないようです）が異なる2台のPCで試行錯誤した結果、こうすると最もパフォーマンスが良くなることが分かりました。

## 安定ソートのOpenMPによるスレッド並列化
次に、OpenMPを使ったスレッド並列化を試してみましょう。サンプルコードは以下のようになります。なおこのコードは、参考サイト[3]および参考文献[1]に載っているコードを参考にさせて頂きました。

```cpp
template < class RandomIter >
//! A template function.
/*!
    指定された範囲の要素を安定ソートする（OpenMPで並列化）
    \param first 範囲の下限
    \param last 範囲の上限
*/
inline void stable_sort_openmp(RandomIter first, RandomIter last)
{
#pragma omp parallel    // OpenMP並列領域の始まり
#pragma omp single      // task句はsingle領域で実行
    // 再帰ありの並列安定ソートの関数を呼び出す
    stable_sort_openmp(first, last, 0);
}

template < class RandomIter >
//! A template function.
/*!
    指定された範囲の要素を安定ソートする（OpenMPで並列化）
    \param first 範囲の下限
    \param last 範囲の上限
    \param reci 現在の再帰の深さ
*/
void stable_sort_openmp(RandomIter first, RandomIter last, std::int32_t reci)
{
    // 部分ソートの要素数
    auto const len = std::distance(first, last);

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

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

    // 現在の再帰の深さが閾値以下のときだけ並列化させる
    if (reci <= THRESHOLD) {
        auto const middle = first + len / 2;

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

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

        // 二つのタスクの終了を待機
#pragma omp taskwait

        // ソートされた下部と上部をマージ
        std::inplace_merge(first, middle, last);
    }
    else {
        // C++標準の安定ソートの関数を呼び出す
        std::stable_sort(first, last);
    }
}
```

## 安定ソートのTBBによるスレッド並列化
次に、TBBを使ったスレッド並列化を試してみましょう。サンプルコードは以下のようになります。なおこのコードは、参考サイト[3]に載っているコードを参考にさせて頂きました。

```cpp
template < class RandomIter >
//! A template function.
/*!
    指定された範囲の要素を安定ソートする（TBBで並列化）
    \param first 範囲の下限
    \param last 範囲の上限
*/
inline void stable_sort_tbb(RandomIter first, RandomIter last)
{
    // 再帰ありの並列安定ソートの関数を呼び出す
    stable_sort_tbb(first, last, 0);
}

template < class RandomIter >
//! A template function.
/*!
    指定された範囲の要素を安定ソートする
    \param first 範囲の下限
    \param last 範囲の上限
    \param reci 現在の再帰の深さ
*/
void stable_sort_tbb(RandomIter first, RandomIter last, std::int32_t reci)
{
    // 部分ソートの要素数
    auto const len = std::distance(first, last);

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

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

    // 現在の再帰の深さが閾値以下のときだけ並列化させる
    if (reci <= THRESHOLD) {
        auto const middle = first + len / 2;

        // 二つのラムダ式を別スレッドで実行
        tbb::parallel_invoke(
            // 下部をソート
            [first, middle, reci]() { stable_sort_tbb(first, middle, reci); },
            // 上部をソート
            [middle, last, reci]() { stable_sort_tbb(middle, last, reci); });

        // ソートされた下部と上部をマージ
        std::inplace_merge(first, middle, last);
    }
    else {
        // C++標準の安定ソートの関数を呼び出す
        std::stable_sort(first, last);
    }
}
```

## 安定ソートのCilkによるスレッド並列化
次に、Cilkを使ったスレッド並列化を試してみましょう。サンプルコードは以下のようになります。なおこのコードは、[参考サイト[4]](https://www.xlsoft.com/jp/products/intel/compilers/manual/cpp_all_os/GUID-CA1C39CC-4742-489F-BFDC-D24688FC845E.htm "C/C++ プログラムの変換")および参考文献[1]に載っているコードを参考にさせて頂きました。

```cpp
template < class RandomIter >
//! A template function.
/*!
    指定された範囲の要素を安定ソートする（Cilkで並列化）
    \param first 範囲の下限
    \param last 範囲の上限
*/
inline void stable_sort_cilk(RandomIter first, RandomIter last)
{
    // 再帰ありの並列安定ソートの関数を呼び出す
    stable_sort_cilk(first, last, 0);
}

template < class RandomIter >
//! A template function.
/*!
    指定された範囲の要素を安定ソートする
    \param first 範囲の下限
    \param last 範囲の上限
    \param reci 現在の再帰の深さ
*/
void stable_sort_cilk(RandomIter first, RandomIter last, std::int32_t reci)
{
    // 部分ソートの要素数
    auto const len = std::distance(first, last);

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

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

    // 現在の再帰の深さが閾値以下のときだけ並列化させる
    if (reci <= THRESHOLD) {
        auto const middle = first + len / 2;

        // 下部をソート（別スレッドで実行）
        cilk_spawn stable_sort_cilk(first, middle, reci);

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

        // 二つのスレッドの終了を待機
        cilk_sync;

        // ソートされた下部と上部をマージ
        std::inplace_merge(first, middle, last);
    }
    else {
        // C++標準の安定ソートの関数を呼び出す
        std::stable_sort(first, last);
    }
}
```

## C++17のParallelism TSによるstd::stable_sortを使った並列化ソート
C++17から、並列アルゴリズムライブラリ（Parallelism TS）がC++標準のSTLに実装され、並列STLが利用可能になりました。Parallelism TSの解説は他に譲りますが（例えば[参考サイト[5]](http://faithandbrave.hateblo.jp/entry/2016/09/27/155500 "Faith and Brave - C++で遊ぼう　C++1z 並列アルゴリズムライブラリ")）、例えばstd::stable_sortをスレッド並列化して実行するには、以下のコードのように記述します。

```cpp
std::vector< std::pair<int, int> > v(1000000);

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

2018年7月31日現在、Parallelism TSをサポートしているコンパイラは、**[Intel C++ Compiler 18.0と、Microsoft Visual C++ (MSVC) 14.14 (Visual Studio 2017 version 15.7.3)](http://en.cppreference.com/w/cpp/compiler_support#cpp17 "http://en.cppreference.com/w/cpp/compiler_support#cpp17")**以降のみです（ただし、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](https://github.com/intel/parallelstl "https://github.com/intel/parallelstl")という名称でGitHubにてオープンソースで公開されている（ライセンスはApache License 2.0）ので、任意のコンパイラでParallelism TSを試すことができます。

# 並列安定ソートのパフォーマンス測定
それでは、以上のスレッド並列化された安定ソート関数のパフォーマンス（ソート時間）を、std::stable_sortと比較してみましょう。またあわせて、Parallelism TSによるstd::stable_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でかなり挙動が異なるため、それぞれ別個に測定し、さらに、両方の環境において、それぞれ二つのコンパイラで測定しました。ここで、配列の要素を100個から1億個まで変化させ、ソートにかかった時間を測定しました。ただし、測定回数は10回とし、その平均を結果としました。Windowsの測定環境は、

* OS: Microsoft Windows 10 Enterprise (64bit)

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

* Microsoft Visual C++ (MSVC) 14.14 (Visual Studio 2017 version 15.7.5) 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.5) の場合
まず、OSがWindowsで、コンパイラがMSVC 14.14 (Visual Studio 2017 version 15.7.5)の場合について述べたいと思います。

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

```cpp
auto const n = 1000000;
std::vector< std::pair<int, int> > vec(n);

std::random_device rnd;
auto randengine = std::mt19937(rnd());
std::uniform_int_distribution<int> distribution(1, n / 10);

for (auto i = 0; i < n; i++) {
    vec[i] = std::make_pair(distribution(randengine), i);
}
```

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

|配列の要素数|std::stable_sort|std::thread|TBB|std::stable_sort (MSVC内蔵のParallelism TS)|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000011 | 0.0026115 | 0.0000671 | 0.0000411 | 0.0000016 |
| 500       | 0.0000052 | 0.0023779 | 0.0000278 | 0.0000293 | 0.0000050 |
| 1000      | 0.0000105 | 0.0021268 | 0.0000212 | 0.0000304 | 0.0000165 |
| 5000      | 0.0000733 | 0.0020665 | 0.0000448 | 0.0000950 | 0.0000397 |
| 10000     | 0.0001511 | 0.0020659 | 0.0000772 | 0.0001351 | 0.0000531 |
| 50000     | 0.0009275 | 0.0024830 | 0.0003096 | 0.0003152 | 0.0001565 |
| 100000    | 0.0019366 | 0.0023855 | 0.0005417 | 0.0005371 | 0.0003142 |
| 500000    | 0.0118314 | 0.0041874 | 0.0029073 | 0.0021368 | 0.0019765 |
| 1000000   | 0.0252828 | 0.0076421 | 0.0063895 | 0.0040965 | 0.0041267 |
| 5000000   | 0.1785216 | 0.0447942 | 0.0432663 | 0.0248951 | 0.0264671 |
| 10000000  | 0.3662624 | 0.0950084 | 0.0953184 | 0.0534481 | 0.0560704 |
| 50000000  | 2.0523977 | 0.5322783 | 0.5254569 | 0.2688943 | 0.3195224 |
| 100000000 | 4.3668062 | 1.0508450 | 1.0545572 | 0.5382259 | 0.6705182 |

これをグラフにすると、以下の図のようになります（両対数グラフであることに注意してください）。
![完全にシャッフルされたデータのグラフ_MSVC_on_Windows.png](https://qiita-image-store.s3.amazonaws.com/0/58457/eab7b2da-43e4-281c-8c2c-beadb4ac1c17.png)

TBBは、配列の要素数が5000個以上でstd::stable_sortよりも高速になります（配列の要素数が100個～1000個の場合は、スレッド生成のコストが高くつくため、std::stable_sortより遅くなっています）。原因は分かりませんが、std::threadはパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::stable_sortよりも高速になります。std::threadは、配列の要素数100個～10万個で、ソート時間がほとんど変化していないのも不思議です（おそらく、スレッド生成のコストのためだと思われます）。
また、std::threadとTBBは、配列の要素数が500万個以上になると概ね同じような傾向を示します。std::threadとTBBは、配列の要素数が500万個以上では、std::stable_sortよりも4倍前後高速であることが分かります。
MSVC内蔵のParallelism TSのstd::stable_sortは、配列の要素数が1万個以上で通常のstd::stable_sortより高速であり、配列の要素数が5万個以上の場合は、通常のstd::stable_sortよりも3倍弱～8倍強程度高速です。
Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が5000個以上で通常のstd::stable_sortより高速であり、配列の要素数が5万個以上の場合は、std::stable_sortよりも6倍前後高速です。
また、MSVC内蔵のParallelism TSのstd::stable_sortと、Parallel STLのParallelism TSのstd::stable_sortとを比較すると、配列の要素数が50万個までは後者の方が高速ですが、それ以上の要素数となると前者が高速になる、という興味深い結果が得られています。配列の要素数が1億個の場合、前者は後者より約25%高速です。

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

```cpp
auto const n = 1000000;
std::vector< std::pair<int, int> > vec(n);

std::random_device rnd;
auto randengine = std::mt19937(rnd());
std::uniform_int_distribution<int> distribution(1, n / 10);

for (auto i = 0; i < n; i++) {
    vec[i] = std::make_pair(distribution(randengine), i);
}

std::stable_sort(vec.begin(), vec.end());
```

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

|配列の要素数|std::stable_sort|std::thread|TBB|std::stable_sort (MSVC内蔵のParallelism TS)|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000008 | 0.0021719 | 0.0000045 | 0.0000063 | 0.0000007 |
| 500       | 0.0000035 | 0.0022665 | 0.0000090 | 0.0000192 | 0.0000035 |
| 1000      | 0.0000074 | 0.0020004 | 0.0000095 | 0.0000179 | 0.0000129 |
| 5000      | 0.0000536 | 0.0020720 | 0.0000262 | 0.0000599 | 0.0000322 |
| 10000     | 0.0001061 | 0.0020184 | 0.0000466 | 0.0000858 | 0.0000437 |
| 50000     | 0.0006275 | 0.0019536 | 0.0001785 | 0.0002226 | 0.0001633 |
| 100000    | 0.0014713 | 0.0021245 | 0.0003727 | 0.0003563 | 0.0003002 |
| 500000    | 0.0088359 | 0.0036245 | 0.0020669 | 0.0014269 | 0.0017316 |
| 1000000   | 0.0195887 | 0.0060088 | 0.0047318 | 0.0028093 | 0.0035194 |
| 5000000   | 0.1440418 | 0.0371351 | 0.0341914 | 0.0189277 | 0.0233815 |
| 10000000  | 0.2926114 | 0.0819667 | 0.0799007 | 0.0381445 | 0.0510962 |
| 50000000  | 1.6508358 | 0.4523384 | 0.4528470 | 0.1958574 | 0.2922036 |
| 100000000 | 3.5459284 | 0.9005250 | 0.8989781 | 0.3969237 | 0.6149898 |

これをグラフにすると、以下の図のようになります。
![あらかじめソートされたデータのグラフ_MSVC_on_Windows.png](https://qiita-image-store.s3.amazonaws.com/0/58457/1c7800c3-392f-3861-b868-322d8383beee.png)

TBBは配列の要素数が5000個以上で、std::stable_sortよりも高速になります（配列の要素数が100個～1000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortより遅くなっています）。std::threadは相変わらずなぜかパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::stable_sortよりも高速になります。std::threadは、配列の要素数100個～10万個で、ソート時間がほとんど変化していないのも相変わらずです。
std::threadとTBBは、配列の要素数が1000万個以上でよく似た傾向を示します。std::threadおよびTBBは、配列の要素数が1000万個以上で、std::stable_sortよりも3.5倍強～4倍弱高速になっています。
MSVC内蔵のParallelism TSのstd::stable_sortは、配列の要素数が1万個以上で通常のstd::stable_sortより高速であり、配列の要素数が50万個以上の場合は、通常のstd::stable_sortよりも6倍強～9倍弱程度高速です。
Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が1000個の場合を除いて、std::stable_sortより高速です。配列の要素数が10万個以上の場合、前者は後者より5倍弱～6倍強程度高速となっています。
また、MSVC内蔵のParallelism TSのstd::stable_sortと、Parallel STLのParallelism TSのstd::stable_sortとを比較すると、配列の要素数が10万個までは後者の方が高速ですが、それ以上の要素数となると前者が高速になる、という興味深い結果が得られています。配列の要素数が1億個の場合、前者は後者より約54%高速です。

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

```cpp
auto const n = 1000000;
std::vector< std::pair<int, int> > vec(n);

std::random_device rnd;
auto randengine = std::mt19937(rnd());
std::uniform_int_distribution<int> distribution(1, n / 10);

for (auto i = 0; i < n; i++) {
    vec[i] = std::make_pair(distribution(randengine), i);
}

std::stable_sort(vec.begin(), vec.begin() + n / 4);
```

上記のコードのvecのような配列のことです。この配列の要素を500個から1億個まで変化させて、ソートにかかった時間を測定し、結果を下の表にまとめました（単位は秒）。ただし測定回数は10回とし、その平均を結果としました。

|配列の要素数|std::stable_sort|std::thread|TBB|std::stable_sort (MSVC内蔵のParallelism TS)|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000010 | 0.0022033 | 0.0000085 | 0.0000121 | 0.0000010 |
| 500       | 0.0000050 | 0.0021576 | 0.0000106 | 0.0000229 | 0.0000054 |
| 1000      | 0.0000097 | 0.0020028 | 0.0000126 | 0.0000264 | 0.0000150 |
| 5000      | 0.0000699 | 0.0019778 | 0.0000409 | 0.0000681 | 0.0000391 |
| 10000     | 0.0001392 | 0.0020157 | 0.0000627 | 0.0000984 | 0.0000500 |
| 50000     | 0.0008206 | 0.0022561 | 0.0002464 | 0.0002711 | 0.0001767 |
| 100000    | 0.0018484 | 0.0022459 | 0.0005558 | 0.0004637 | 0.0003192 |
| 500000    | 0.0112465 | 0.0041846 | 0.0029794 | 0.0019834 | 0.0018932 |
| 1000000   | 0.0239758 | 0.0074982 | 0.0061861 | 0.0038709 | 0.0040501 |
| 5000000   | 0.1724476 | 0.0449774 | 0.0439685 | 0.0245257 | 0.0254787 |
| 10000000  | 0.3529354 | 0.0958476 | 0.0938564 | 0.0508221 | 0.0549481 |
| 50000000  | 1.9788633 | 0.5245452 | 0.5270426 | 0.2613809 | 0.3120799 |
| 100000000 | 4.1497270 | 1.0439199 | 1.0433895 | 0.5293130 | 0.6556512 |

これをグラフにすると、以下の図のようになります。
![最初の1_4だけソートされたデータのグラフ_MSVC_on_Windows.png](https://qiita-image-store.s3.amazonaws.com/0/58457/521dd1c6-4502-6c19-db15-c73f883e8359.png)

TBBは、配列の要素数が5000個以上でstd::stable_sortよりも高速になります（配列の要素数が100個～1000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortより遅くなっています）。std::threadは相変わらずなぜかパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::stable_sortよりも高速になります。std::threadは、配列の要素数100個～10万個で、ソート時間がほとんど変化していないのも相変わらずです。
また、std::threadおよびTBBは、配列の要素数が500万個以上になると概ね同じような傾向を示します。std::threadおよびTBBは、配列の要素数が500万個以上では、std::stable_sortよりも4倍弱程度高速であることが分かります。
MSVC内蔵のParallelism TSのstd::stable_sortは、配列の要素数が5000個以上で通常のstd::stable_sortより高速であり、配列の要素数が100万個以上の場合は、通常のstd::stable_sortよりも6倍強～8倍弱程度高速です。
Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が500個および1000個の場合を除いて、std::stable_sortより高速です。配列の要素数が10万個以上の場合、前者は後者より6倍弱～7倍弱程度高速となっています。
また、MSVC内蔵のParallelism TSのstd::stable_sortと、Parallel STLのParallelism TSのstd::stable_sortとを比較すると、配列の要素数が50万個までは後者の方が高速ですが、それ以上の要素数となると前者が高速になる、という興味深い結果が得られています。配列の要素数が1億個の場合、前者は後者より約24%高速です。

## 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::stable_sort|std::thread|OpenMP|TBB|Cilk|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000028 | 0.0024343 | 0.0007652 | 0.0000786 | 0.0004776 | 0.0000017 |
| 500       | 0.0000081 | 0.0028117 | 0.0000215 | 0.0000190 | 0.0000154 | 0.0000081 |
| 1000      | 0.0000169 | 0.0026439 | 0.0000213 | 0.0000188 | 0.0000266 | 0.0000188 |
| 5000      | 0.0001112 | 0.0026608 | 0.0000469 | 0.0000457 | 0.0000868 | 0.0000387 |
| 10000     | 0.0002342 | 0.0026064 | 0.0000788 | 0.0000793 | 0.0001325 | 0.0000573 |
| 50000     | 0.0014391 | 0.0029143 | 0.0003284 | 0.0003362 | 0.0004038 | 0.0002418 |
| 100000    | 0.0023378 | 0.0023932 | 0.0007431 | 0.0008555 | 0.0007382 | 0.0004942 |
| 500000    | 0.0137053 | 0.0049478 | 0.0039294 | 0.0034219 | 0.0037808 | 0.0019197 |
| 1000000   | 0.0290871 | 0.0082519 | 0.0081154 | 0.0071921 | 0.0085777 | 0.0040678 |
| 5000000   | 0.1966980 | 0.0480671 | 0.0517505 | 0.0467189 | 0.0480708 | 0.0261598 |
| 10000000  | 0.3996020 | 0.1004243 | 0.1136648 | 0.0989834 | 0.1034688 | 0.0560094 |
| 50000000  | 2.2135913 | 0.5457411 | 0.6231291 | 0.5453292 | 0.5525160 | 0.3132208 |
| 100000000 | 4.7689131 | 1.1100551 | 1.2893282 | 1.1116285 | 1.1275548 | 0.6558609 |

これをグラフにすると、以下の図のようになります（両対数グラフであることに注意してください）。
![完全にシャッフルされたデータのグラフ_ICC_on_Windows.png](https://qiita-image-store.s3.amazonaws.com/0/58457/c1ce3e7f-6de5-3fdf-e69d-036b751f355c.png)

OpenMP、TBB、Cilkは配列の要素数が5000個以上で、std::stable_sortよりも高速になります（配列の要素数が100個～1000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortより遅くなっています）。原因は分かりませんが、std::threadはパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::stable_sortよりも高速になります。std::threadは、配列の要素数100個～10万個で、ソート時間がほとんど変化していないのも不思議です（おそらく、スレッド生成のコストのためだと思われます）。
また、OpenMP、TBBは、配列の要素数が5000個以上で概ね同じような傾向を示し、配列の要素数が10万個以上では、これにCilkが加わります。加えて、配列の要素数が1000万個以上では、さらにこれにstd::threadが加わります。std::thread、OpenMP、TBB、Cilkは、配列の要素数が1000万個以上では、std::stable_sortよりも、3.5倍～4倍強程度高速であることが分かります。ただ、OpenMPは配列の要素数5000万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。
Parallelism TSのstd::stable_sortは、配列の要素数が1000個の場合を除いて通常のstd::stable_sortより高速です。特に、配列の要素数が5万個以上の場合、前者は後者よりも5倍弱～7.5倍程度高速です。

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

|配列の要素数|std::stable_sort|std::thread|OpenMP|TBB|Cilk|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000010 | 0.0025278 | 0.0000241 | 0.0000070 | 0.0000040 | 0.0000012 |
| 500       | 0.0000066 | 0.0024098 | 0.0000116 | 0.0000096 | 0.0000112 | 0.0000061 |
| 1000      | 0.0000130 | 0.0024543 | 0.0000214 | 0.0000123 | 0.0000216 | 0.0000162 |
| 5000      | 0.0000892 | 0.0025811 | 0.0000342 | 0.0000378 | 0.0000735 | 0.0000361 |
| 10000     | 0.0001863 | 0.0025043 | 0.0000612 | 0.0000676 | 0.0001009 | 0.0000525 |
| 50000     | 0.0010895 | 0.0023352 | 0.0002439 | 0.0002422 | 0.0003158 | 0.0001738 |
| 100000    | 0.0017058 | 0.0021916 | 0.0005659 | 0.0005653 | 0.0005863 | 0.0003187 |
| 500000    | 0.0104512 | 0.0038888 | 0.0028856 | 0.0023875 | 0.0029704 | 0.0017006 |
| 1000000   | 0.0224070 | 0.0066834 | 0.0061044 | 0.0052853 | 0.0060912 | 0.0034883 |
| 5000000   | 0.1583679 | 0.0384794 | 0.0420551 | 0.0376311 | 0.0379392 | 0.0232153 |
| 10000000  | 0.3253611 | 0.0846750 | 0.0951028 | 0.0834605 | 0.0861120 | 0.0503459 |
| 50000000  | 1.8031218 | 0.4607694 | 0.5266053 | 0.4715529 | 0.4706979 | 0.2814851 |
| 100000000 | 3.8835950 | 0.9299866 | 1.0593142 | 0.9262875 | 0.9366599 | 0.5908954 |

これをグラフにすると、以下の図のようになります。
![あらかじめソートされたデータのグラフ_ICC_on_Windows.png](https://qiita-image-store.s3.amazonaws.com/0/58457/61464b6c-821c-18df-ea86-21e3cd9b8a1e.png)

TBBは配列の要素数が1000個以上で、OpenMPとCilkは配列の要素数が5000個以上で、std::stable_sortよりも高速になります（配列の要素数が100個～500個あるいは1000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortより遅くなっています）。std::threadは相変わらずなぜかパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::stable_sortよりも高速になります。また、std::threadは、配列の要素数100個～10万個で、ソート時間がほとんど変化していないのも相変わらずです。
また、OpenMP、TBBは、配列の要素数が5000個以上で概ね同じような傾向を示し、配列の要素数が10万個以上では、これにCilkが加わります。加えて、配列の要素数が1000万個以上では、さらにこれにstd::threadが加わります。std::thread、OpenMP、TBB、Cilkは、配列の要素数が1000万個以上では、std::stable_sortよりも、3.5倍弱～4倍強程度高速であることが分かります。ただ、OpenMPは配列の要素数5000万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。
Parallelism TSのstd::stable_sortは、配列の要素数が100個および1000個の場合を除いて通常のstd::stable_sortより高速です。特に、配列の要素数が5万個以上の場合、前者は後者よりも5.5倍弱～7倍弱程度高速です。

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

|配列の要素数|std::stable_sort|std::thread|OpenMP|TBB|Cilk|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000013 | 0.0020534 | 0.0000239 | 0.0000066 | 0.0000050 | 0.0000015 |
| 500       | 0.0000079 | 0.0024445 | 0.0000168 | 0.0000115 | 0.0000140 | 0.0000077 |
| 1000      | 0.0000166 | 0.0026528 | 0.0000236 | 0.0000146 | 0.0000242 | 0.0000190 |
| 5000      | 0.0001056 | 0.0024328 | 0.0000403 | 0.0000428 | 0.0000766 | 0.0000400 |
| 10000     | 0.0002247 | 0.0026112 | 0.0000713 | 0.0000747 | 0.0001145 | 0.0000619 |
| 50000     | 0.0013051 | 0.0025520 | 0.0003050 | 0.0003151 | 0.0003658 | 0.0002016 |
| 100000    | 0.0021368 | 0.0024806 | 0.0007443 | 0.0007487 | 0.0007337 | 0.0003216 |
| 500000    | 0.0128706 | 0.0046529 | 0.0036691 | 0.0031970 | 0.0036925 | 0.0019054 |
| 1000000   | 0.0277495 | 0.0083698 | 0.0082237 | 0.0071353 | 0.0083889 | 0.0038582 |
| 5000000   | 0.1879769 | 0.0475730 | 0.0519138 | 0.0464047 | 0.0470317 | 0.0252200 |
| 10000000  | 0.3844914 | 0.1008541 | 0.1138961 | 0.1000084 | 0.1055175 | 0.0544826 |
| 50000000  | 2.1126191 | 0.5393258 | 0.6168799 | 0.5444908 | 0.5504398 | 0.3034701 |
| 100000000 | 4.5543029 | 1.1146969 | 1.2752200 | 1.1067939 | 1.1236864 | 0.6374640 |

これをグラフにすると、以下の図のようになります。
![最初の1_4だけソートされたデータのグラフ_ICC_on_Windows.png](https://qiita-image-store.s3.amazonaws.com/0/58457/75a401be-d6df-bfd5-8936-26d3cb58f4a7.png)

TBBは配列の要素数が1000個以上で、OpenMPとCilkは配列の要素数が5000個以上で、std::stable_sortよりも高速になります（配列の要素数が100個～500個あるいは1000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortより遅くなっています）。std::threadは相変わらずなぜかパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::stable_sortよりも高速になります。また、std::threadは、配列の要素数100個～10万個で、ソート時間がほとんど変化していないのも相変わらずです。
また、OpenMP、TBBは、配列の要素数が5000個以上で概ね同じような傾向を示し、配列の要素数が10万個以上では、これにCilkが加わります。加えて、配列の要素数が1000万個以上では、さらにこれにstd::threadが加わります。std::thread、OpenMP、TBB、Cilkは、配列の要素数が1000万個以上では、std::stable_sortよりも、3.5倍弱～4倍強程度高速であることが分かります。ただ、OpenMPは配列の要素数5000万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。
Parallelism TSのstd::stable_sortは、配列の要素数が100個および1000個の場合を除いて通常のstd::stable_sortより高速です。特に、配列の要素数が5万個以上の場合、前者は後者よりも6.5倍～7.5倍程度高速です。

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

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

|配列の要素数|std::stable_sort|std::thread|OpenMP|TBB|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000042 | 0.0002699 | 0.0002484 | 0.0000098 | 0.0000013 |
| 500       | 0.0000091 | 0.0114416 | 0.0000198 | 0.0000199 | 0.0000081 |
| 1000      | 0.0000185 | 0.0004796 | 0.0000229 | 0.0000222 | 0.0000182 |
| 5000      | 0.0001084 | 0.0041875 | 0.0000600 | 0.0000926 | 0.0009587 |
| 10000     | 0.0002383 | 0.0008501 | 0.0000951 | 0.0020551 | 0.0014596 |
| 50000     | 0.0028868 | 0.0025240 | 0.0004484 | 0.0012936 | 0.0029692 |
| 100000    | 0.0028767 | 0.0034530 | 0.0007961 | 0.0019264 | 0.0023556 |
| 500000    | 0.0171434 | 0.0045218 | 0.0045673 | 0.0066249 | 0.0013887 |
| 1000000   | 0.0326480 | 0.0093069 | 0.0098487 | 0.0089216 | 0.0028205 |
| 5000000   | 0.2178053 | 0.0685428 | 0.0721122 | 0.0672707 | 0.0210134 |
| 10000000  | 0.4522254 | 0.1540057 | 0.1662819 | 0.1533819 | 0.0459579 |
| 50000000  | 2.4523511 | 0.8305380 | 0.9459534 | 0.8279470 | 0.2646077 |
| 100000000 | 5.2052429 | 1.6590719 | 1.9130576 | 1.6582086 | 0.5622037 |

これをグラフにすると、以下の図のようになります。
![完全にシャッフルされたデータのグラフ_Clang_on_Linux.png](https://qiita-image-store.s3.amazonaws.com/0/58457/43f558ac-bb9b-d3b7-0e2c-57e13dd35f57.png)

Windowsの場合と比べて、ばらついた結果となっています。
最も安定して高速なのはOpenMPであり、OpenMPは、配列の要素数が5000個以上で、std::stable_sortよりも高速になります（配列の要素数が100個および1000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortよりも遅くなっています）。またTBBは、配列の要素数が5万個以上でstd::stable_sortより高速となります。そして、std::threadについては、Windowsの場合と同様になぜかパフォーマンスが悪く、配列の要素数が50万個以上で、やっとstd::stable_sortよりも高速になります（配列の要素数が5万個の場合は例外です）。
また、std::threadとOpenMPは、配列の要素数が50万個以上になると概ね同じような傾向を示し、配列の要素数が100万個以上では、これにTBBが加わります。std::thread、OpenMP、TBBは、配列の要素数が100万個以上では、std::stable_sortよりも3倍弱～3.5倍強程度高速であることが分かります。ただ、OpenMPは配列の要素数100万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。
Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数100個～1000個の場合を例外とすると、配列の要素数が50万個以上で、通常のstd::stable_sortより高速になります。そして、Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が50万個以上では、通常のstd::stable_sortよりも9倍強～12倍強程度高速です。

### あらかじめソートされたデータをソートする場合
次に、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定しました（Windowsの場合と同様ですので、コードは省略します）。

|配列の要素数|std::stable_sort|std::thread|OpenMP|TBB|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000030 | 0.0003019 | 0.0002182 | 0.0000050 | 0.0000010 |
| 500       | 0.0000074 | 0.0051950 | 0.0000168 | 0.0000099 | 0.0000067 |
| 1000      | 0.0000151 | 0.0004664 | 0.0000320 | 0.0000185 | 0.0000149 |
| 5000      | 0.0000707 | 0.0048394 | 0.0002182 | 0.0000960 | 0.0000815 |
| 10000     | 0.0001985 | 0.0085996 | 0.0000678 | 0.0008084 | 0.0037916 |
| 50000     | 0.0023106 | 0.0018623 | 0.0002959 | 0.0025833 | 0.0060654 |
| 100000    | 0.0022983 | 0.0034753 | 0.0006066 | 0.0035684 | 0.0073107 |
| 500000    | 0.0127995 | 0.0037070 | 0.0034771 | 0.0049181 | 0.0021441 |
| 1000000   | 0.0270117 | 0.0079515 | 0.0078500 | 0.0074855 | 0.0022344 |
| 5000000   | 0.1896785 | 0.0611827 | 0.0648100 | 0.0602991 | 0.0183753 |
| 10000000  | 0.3928091 | 0.1436042 | 0.1564120 | 0.1415115 | 0.0405805 |
| 50000000  | 2.1148438 | 0.7841555 | 0.8847548 | 0.7866273 | 0.2354345 |
| 100000000 | 4.5191925 | 1.5708433 | 1.7876409 | 1.5692360 | 0.5035276 |

これをグラフにすると、以下の図のようになります。
![あらかじめソートされたデータのグラフ_Clang_on_Linux.png](https://qiita-image-store.s3.amazonaws.com/0/58457/245f795c-1ae2-3889-76f6-f6cf31dfe940.png)

これもWindowsの場合と比べると、結果がばらついています。
最も安定して高速なのはOpenMPであり、OpenMPは、配列の要素数が5000個以上で、std::stable_sortよりも高速になります（配列の要素数が100個および1000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortよりも遅くなっています）。またTBBは、配列の要素数が5万個以上でstd::stable_sortより高速となります（配列の要素数5000個の場合は例外です）。そして、std::threadについては、Windowsの場合と同様になぜかパフォーマンスが悪く、配列の要素数が50万個以上で、やっとstd::stable_sortよりも高速になります（配列の要素数が5万個の場合は例外です）。
また、std::threadとOpenMPは、配列の要素数が50万個以上になると概ね同じような傾向を示し、配列の要素数が100万個以上では、これにTBBが加わります。std::thread、OpenMP、TBBは、配列の要素数が100万個以上では、std::stable_sortよりも2.5倍強～3.5倍強程度高速であることが分かります。ただ、OpenMPは配列の要素数500万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。
Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数100個～1000個の場合を例外とすると、配列の要素数が10万個以上で、通常のstd::stable_sortより高速になります。そして、Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が50万個以上では、通常のstd::stable_sortよりも9倍弱～12倍強程度高速です。

### 最初の1/4だけソートされたデータをソートする場合
最後に、最初の1/4だけソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定しました（Windowsの場合と同様ですので、コードは省略します）。

|配列の要素数|std::stable_sort|std::thread|OpenMP|TBB|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000014 | 0.0002584 | 0.0003095 | 0.0000073 | 0.0000013 |
| 500       | 0.0000089 | 0.0028603 | 0.0000167 | 0.0000124 | 0.0000079 |
| 1000      | 0.0000176 | 0.0006920 | 0.0000194 | 0.0000140 | 0.0000168 |
| 5000      | 0.0001051 | 0.0016110 | 0.0000451 | 0.0000440 | 0.0000779 |
| 10000     | 0.0002295 | 0.0009714 | 0.0000864 | 0.0002801 | 0.0005824 |
| 50000     | 0.0012765 | 0.0018135 | 0.0003643 | 0.0011229 | 0.0021124 |
| 100000    | 0.0027272 | 0.0035000 | 0.0007190 | 0.0017697 | 0.0022651 |
| 500000    | 0.0164990 | 0.0042929 | 0.0040529 | 0.0056731 | 0.0013547 |
| 1000000   | 0.0311844 | 0.0090062 | 0.0090693 | 0.0085631 | 0.0026479 |
| 5000000   | 0.2107174 | 0.0668972 | 0.0701089 | 0.0662209 | 0.0204921 |
| 10000000  | 0.4394317 | 0.1506196 | 0.1659428 | 0.1484146 | 0.0437576 |
| 50000000  | 2.3798534 | 0.8260514 | 0.9395964 | 0.8265195 | 0.2572223 |
| 100000000 | 5.0570558 | 1.6553056 | 1.8786694 | 1.6590271 | 0.5409205 |

これをグラフにすると、以下の図のようになります。
![最初の1_4だけソートされたデータのグラフ_Clang_on_Linux.png](https://qiita-image-store.s3.amazonaws.com/0/58457/2bb4070d-c439-49c5-a037-88bdc023621f.png)

これもWindowsの場合と比べると、結果がばらついています。
最も安定して高速なのはOpenMPであり、OpenMPは、配列の要素数が5000個以上で、std::stable_sortよりも高速になります（配列の要素数が100個および1000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortよりも遅くなっています）。またTBBは、配列の要素数が5万個以上でstd::stable_sortより高速となります（配列の要素数1000個および5000個の場合は例外です）。そして、std::threadについては、Windowsの場合と同様になぜかパフォーマンスが悪く、配列の要素数が50万個以上で、やっとstd::stable_sortよりも高速になります。
また、std::threadとOpenMPは、配列の要素数が50万個以上になると概ね同じような傾向を示し、配列の要素数が100万個以上では、これにTBBが加わります。std::thread、OpenMP、TBBは、配列の要素数が100万個以上では、std::stable_sortよりも2.5倍強～3.5倍強程度高速であることが分かります。ただ、OpenMPは配列の要素数100万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。
Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が1万個および5万個の場合を除いて、通常のstd::stable_sortより高速です。そして、Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が50万個以上では、通常のstd::stable_sortよりも9倍強～12倍強程度高速です。

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

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

|配列の要素数|std::stable_sort|std::thread|OpenMP|TBB|Cilk|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000020 | 0.0002902 | 0.0001342 | 0.0000100 | 0.0000438 | 0.0000018 |
| 500       | 0.0000112 | 0.0080094 | 0.0000179 | 0.0000141 | 0.0000383 | 0.0000125 |
| 1000      | 0.0000243 | 0.0050901 | 0.0000217 | 0.0000188 | 0.0000342 | 0.0000248 |
| 5000      | 0.0001319 | 0.0029801 | 0.0000621 | 0.0000916 | 0.0000951 | 0.0009155 |
| 10000     | 0.0002762 | 0.0014744 | 0.0001365 | 0.0005762 | 0.0001778 | 0.0013228 |
| 50000     | 0.0024027 | 0.0022768 | 0.0009290 | 0.0015045 | 0.0008020 | 0.0031610 |
| 100000    | 0.0032912 | 0.0015548 | 0.0011456 | 0.0015709 | 0.0012082 | 0.0024054 |
| 500000    | 0.0163761 | 0.0062482 | 0.0060270 | 0.0087941 | 0.0063345 | 0.0015730 |
| 1000000   | 0.0346694 | 0.0120389 | 0.0127702 | 0.0120815 | 0.0126348 | 0.0031695 |
| 5000000   | 0.2289409 | 0.0808948 | 0.0867401 | 0.0823682 | 0.0908485 | 0.0233266 |
| 10000000  | 0.4657141 | 0.1821793 | 0.1944595 | 0.1813423 | 0.1901677 | 0.0509413 |
| 50000000  | 2.5260640 | 0.9773687 | 1.0929505 | 0.9770083 | 0.9863234 | 0.2813270 |
| 100000000 | 5.3428762 | 1.9617348 | 2.1972802 | 1.9608014 | 1.9714949 | 0.5906630 |

これをグラフにすると、以下の図のようになります。
![完全にシャッフルされたデータのグラフ_ICC_on_Linux.png](https://qiita-image-store.s3.amazonaws.com/0/58457/48abcc05-9167-a8ca-2679-f5e8425fb6b2.png)

コンパイラがClangの場合と同様に、Windowsの場合と比べて、ややばらついた結果となっています。
最も安定して高速なのはOpenMPであり、OpenMPは、配列の要素数が1000個以上で、std::stable_sortよりも高速になります（配列の要素数が100個および500個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortよりも遅くなっています）。またOpenMPと同様にTBBも、配列の要素数が1000個以上でstd::stable_sortより高速となります（配列の要素数が1万個の場合は例外です）。Cilkについては、配列の要素数が5000個以上でstd::stable_sortより高速となります。そして、std::threadは、配列の要素数が5万個以上で、std::stable_sortよりも高速になります。
また、OpenMPとCilkは、配列の要素数が10万個以上になると概ね同じような傾向を示し、配列の要素数が50万個以上ではこれにstd::threadが加わり、さらに配列の要素数が100万個以上ではこれにTBBが加わります。std::thread、OpenMP、TBB、Cilkは、配列の要素数が100万個以上では、std::stable_sortよりも2.5倍前後高速であることが分かります（配列の要素数が1000万個以上では、OpenMPのパフォーマンスが若干悪くなっています）。
Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が10万個以上で、通常のstd::stable_sortより高速になります（配列の要素数が100個の場合は例外です）。そして、Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が50万個以上で、通常のstd::stable_sortより9倍弱～11倍弱高速です。

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

|配列の要素数|std::stable_sort|std::thread|OpenMP|TBB|Cilk|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000013 | 0.0002983 | 0.0001380 | 0.0000077 | 0.0000063 | 0.0000018 |
| 500       | 0.0000093 | 0.0033725 | 0.0000152 | 0.0000123 | 0.0000177 | 0.0000091 |
| 1000      | 0.0000196 | 0.0035130 | 0.0007426 | 0.0013010 | 0.0004688 | 0.0003224 |
| 5000      | 0.0001092 | 0.0007608 | 0.0001355 | 0.0001354 | 0.0002872 | 0.0000794 |
| 10000     | 0.0002277 | 0.0007284 | 0.0000952 | 0.0014066 | 0.0007640 | 0.0035261 |
| 50000     | 0.0018535 | 0.0022877 | 0.0004407 | 0.0019628 | 0.0013656 | 0.0046165 |
| 100000    | 0.0025024 | 0.0012134 | 0.0009116 | 0.0012206 | 0.0009220 | 0.0024779 |
| 500000    | 0.0129809 | 0.0053708 | 0.0048942 | 0.0078129 | 0.0051413 | 0.0013314 |
| 1000000   | 0.0275331 | 0.0107424 | 0.0105094 | 0.0106823 | 0.0141371 | 0.0025941 |
| 5000000   | 0.1919668 | 0.0749993 | 0.0762208 | 0.0738974 | 0.0798090 | 0.0206319 |
| 10000000  | 0.3903988 | 0.1690604 | 0.1811576 | 0.1699743 | 0.1760434 | 0.0442615 |
| 50000000  | 2.1112987 | 0.9240587 | 1.0261229 | 0.9227150 | 0.9296763 | 0.2511312 |
| 100000000 | 4.4901949 | 1.8494511 | 2.0299710 | 1.8507081 | 1.8566890 | 0.5243624 |

これをグラフにすると、以下の図のようになります。
![あらかじめソートされたデータのグラフ_ICC_on_Linux.png](https://qiita-image-store.s3.amazonaws.com/0/58457/aa5da88f-93c8-6567-5a27-f3b40eff0a10.png)

これもコンパイラがClangの場合と同様に、Windowsの場合と比べて、ややばらついた結果となっています。
最も安定して高速なのはOpenMPであり、OpenMPは配列の要素数が1万個以上で、std::stable_sortよりも高速になります（配列の要素数が100個～5000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortよりも遅くなっています）。またCilkは、配列の要素数が5万個以上でstd::stable_sortより高速となります。std::threadおよびTBBは、配列の要素数が10万個以上で、std::stable_sortよりも高速になります。
また、OpenMPとCilkは、配列の要素数が10万個以上になると概ね同じような傾向を示し（配列の要素数が100万個の場合は例外です）、配列の要素数が50万個以上ではこれにstd::threadが加わり、さらに配列の要素数が100万個以上ではこれにTBBが加わります。std::thread、OpenMP、TBB、Cilkは、配列の要素数が500万個以上では、std::stable_sortよりも2倍強～2.5倍強程度高速であることが分かります（配列の要素数が1000万個以上では、OpenMPのパフォーマンスが若干悪くなっています）。
Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が10万個以上で、通常のstd::stable_sortより高速になります（配列の要素数が500個および5000個の場合は例外です）。そして、Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が50万個以上で、通常のstd::stable_sortより8.5倍弱～10.5倍強高速です。

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

|配列の要素数|std::stable_sort|std::thread|OpenMP|TBB|Cilk|std::stable_sort (Parallel STLのParallelism TS)|
|:----------|:---------:|:---------:|:---------:|:---------:|:---------:|:---------:|
| 100       | 0.0000017 | 0.0002687 | 0.0001380 | 0.0000085 | 0.0000084 | 0.0000021 |
| 500       | 0.0000109 | 0.0072554 | 0.0007863 | 0.0003870 | 0.0005002 | 0.0000107 |
| 1000      | 0.0000230 | 0.0011445 | 0.0000345 | 0.0000314 | 0.0000325 | 0.0000241 |
| 5000      | 0.0001268 | 0.0020716 | 0.0000668 | 0.0001539 | 0.0004197 | 0.0007278 |
| 10000     | 0.0002656 | 0.0007889 | 0.0001059 | 0.0004859 | 0.0007577 | 0.0009305 |
| 50000     | 0.0014957 | 0.0063541 | 0.0005617 | 0.0018787 | 0.0094868 | 0.0037320 |
| 100000    | 0.0026061 | 0.0012845 | 0.0010543 | 0.0010724 | 0.0078940 | 0.0029554 |
| 500000    | 0.0154350 | 0.0059731 | 0.0055994 | 0.0054995 | 0.0124223 | 0.0015082 |
| 1000000   | 0.0325561 | 0.0123378 | 0.0119831 | 0.0118902 | 0.0183067 | 0.0030264 |
| 5000000   | 0.2208511 | 0.0797578 | 0.0834784 | 0.0806177 | 0.0869387 | 0.0222961 |
| 10000000  | 0.4490077 | 0.1787169 | 0.1953096 | 0.1803625 | 0.1867398 | 0.0488319 |
| 50000000  | 2.4361120 | 0.9779750 | 1.0879679 | 0.9769515 | 0.9858323 | 0.2720978 |
| 100000000 | 5.1402342 | 1.9615940 | 2.1906579 | 1.9613580 | 1.9670266 | 0.5692198 |

これをグラフにすると、以下の図のようになります。
![最初の1_4だけソートされたデータのグラフ_ICC_on_Linux.png](https://qiita-image-store.s3.amazonaws.com/0/58457/37ecaf24-5121-728b-8829-fe59a4fafeed.png)

これもコンパイラがClangの場合と同様に、Windowsの場合と比べて、ややばらついた結果となっています。
最も安定して高速なのはOpenMPであり、OpenMPは配列の要素数が5000個以上で、std::stable_sortよりも高速になります（配列の要素数が100個～1000個の場合は、これらはスレッド生成のコストが高くつくため、std::stable_sortよりも遅くなっています）。std::threadおよびTBBは、配列の要素数が10万個以上で、std::stable_sortよりも高速になります。Cilkはなぜかパフォーマンスが悪く、配列の要素数が50万個以上でやっとstd::stable_sortより高速となります。
また、OpenMPとTBBは、配列の要素数が10万個以上になると概ね同じような傾向を示し、配列の要素数が50万個以上ではこれにstd::threadが加わり、さらに配列の要素数が500万個以上ではこれにCilkが加わります。std::thread、OpenMP、TBB、Cilkは、配列の要素数が500万個以上では、std::stable_sortよりも2倍強～3倍弱程度高速であることが分かります。ただ、配列の要素数が1000万個以上では、OpenMPのパフォーマンスが若干悪くなっており、Cilkに逆転されています。
Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が50万個以上で、通常のstd::stable_sortより高速になります（配列の要素数が500個の場合は例外です）。そして、Parallel STLのParallelism TSのstd::stable_sortは、配列の要素数が50万個以上で、通常のstd::stable_sortより9倍弱～11倍弱程度高速です。

# まとめ
安定ソートを、C++11標準のstd::thread、OpenMP、TBB、Cilkでそれぞれスレッド並列化し、std::stable_sort、C++17のParallelism TSによるstd::stable_sortと速度を比較しました。その結果、C++11標準のstd::thread、OpenMP、TBB、Cilkでスレッド並列化した安定ソートは、特にソート対象の配列の要素数が多い場合に、概ねstd::stable_sortより良好なパフォーマンスを発揮するものの、Parallel STLのParallelism TSによるstd::stable_sortの速度には劣ることがわかりました。そして、Parallel STLのParallelism TSによるstd::stable_sortは、特にソート対象の配列の要素数がある程度多い場合、非常に良好なパフォーマンスを示すことが分かりました。さらに、コンパイラがMSVCの場合、Parallelism TSによるstd::stable_sortについては、Parallel STLの実装と、MSVC内蔵の実装とを比べると、配列の要素数が少ない場合は前者が高速だが、要素数がある閾値を超えると後者の方が高速であることが確かめられました。
従って、要素数が大きい配列を高速にソートしたい場合、Parallel STLが利用できる環境では、Parallel STLのParallelism TSによるstd::stable_sortを積極的に利用するべきだと考えられます。MSVCでは、自身に内蔵のParallelism TSによるstd::stable_sortを利用するのも良いでしょう。C++17のParallelism TSが、早期に各コンパイラに実装されることを期待します。

# サンプルコードへのリンク
以上のコードのサンプルは、以下のGitHubリポジトリにアップロードしてあります。二条項BSDライセンスですので、どうぞご自由にご利用ください。
[https://github.com/dc1394/parallelstablesort](https://github.com/dc1394/parallelstablesort "https://github.com/dc1394/parallelstablesort")

#参考サイト
[1] [アルゴリズムとデータ構造編【整列】　第７章　マージソート](http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/sort/007.html "http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/sort/007.html")
[2] [C++で様々なソートアルゴリズムを実装する](https://qiita.com/rinse_/items/0c29a4d21131c88065ef "https://qiita.com/rinse_/items/0c29a4d21131c88065ef")
[3] [分割統治](https://jp.xlsoft.com/documents/intel/tbb/2017/tbb2017_ugref/tbb_userguide/Design_Patterns/Divide_and_Conquer.html "https://jp.xlsoft.com/documents/intel/tbb/2017/tbb2017_ugref/tbb_userguide/Design_Patterns/Divide_and_Conquer.html")
[4] [C/C++ プログラムの変換](https://www.xlsoft.com/jp/products/intel/compilers/manual/cpp_all_os/GUID-CA1C39CC-4742-489F-BFDC-D24688FC845E.htm "https://www.xlsoft.com/jp/products/intel/compilers/manual/cpp_all_os/GUID-CA1C39CC-4742-489F-BFDC-D24688FC845E.htm")
[5] [Faith and Brave - C++で遊ぼう　C++1z 並列アルゴリズムライブラリ](http://faithandbrave.hateblo.jp/entry/2016/09/27/155500 "http://faithandbrave.hateblo.jp/entry/2016/09/27/155500")

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