一番速いfor文はどれか？【前編】

# 最初に
　この記事はタイトルにも書いているのですが、一番速いループ処理が気になり書きました。[^6]

追記１：中編を上げました

https://qiita.com/HnniTns/items/9c69b9f34d4a77420352

[^6]: あくまで、私での環境なのでその点だけ注意してください。

## 検証方法
　配列に入っている数値を適当な変数に四則演算したうえで時間を計って検証します。今回は100回サンプルを取り平均を求めます。そして、CPUでのシングル・マルチスレッドを検証します。[中編]はGPUを使った検証をするので良ければご覧ください。そして、どれが一番速いか結果を見て確かめます。
　注意点として、現実的に**スレッド生成・削除の時間（GPUの場合は開始・終了処理）**も含みます。なので、処理部分だけの時間ではありません。その点だけ注意して下さい。

## 使用技術
　今回をきっかけに初めて触った技術もあるので、その点はご了承ください。それと、参考程度に難易度を書いていますが、実際に導入して使ってみて自分なりの感想（主観）＆結果なので、あくまで「参考」程度にとどめておいてください。

### CPU-シングルスレッド
#### 1. for
+ Cプログラマーなら誰しもが通る道
+ [コードへ](#for)

#### 2.for each（範囲for文）
+ C++プログラマーなら誰しもが通る道
+ [コードへ](#for-each範囲for文)

#### 3. std::for_each
+ マルチスレッドにする時に非常に使うようになる。それ以外で、わざわざ使う事はあまりないですね。
+ [コードへ](#stdfor_each)

---

### CPU-マルチスレッド
#### 1. std::execution
    
+ ``algorithm``などの標準ヘッダーをマルチスレッド化出来るC++17の標準機能になっています。
    + 難易度
        + 導入コスト：★☆☆（インクルードするだけです）
        + 学習コスト：☆☆☆（通常の関数で引数の先頭を指定するだけです）
        + 資料数　　：★★☆（日本語の記事自体は多くないのですが、使い方が簡単なので問題ないです）
    + 参考サイト
        + [std::execution(実行ポリシー)によるマルチスレッド化は実際のところ どうなのか](https://qiita.com/HnniTns/items/9ff9054082ff9c26c686)
        + [std::execution::実行ポリシー（日本語リファレンス）](https://cpprefjp.github.io/reference/execution/execution/execution_policy.html)
    + [コード１へ（par）](#stdfor_eachstdexecutionpar)
    + [コード２へ（unseq）](#stdfor_eachstdexecutionpar_unseq)

#### 2. PPL(Parallel Pattern Library)
    
+ Microsoftが提供する、標準で付属している並列処理ライブラリです。知っている人はかなり少ないイメージです。
    + 難易度
        + 導入コスト：★☆☆（インクルードするだけです）
        + 学習コスト：★★☆（いくつかあるライブラリ内の関数を使うので、使い方を覚えないといけません）
        + 資料数　　：★☆☆（残念ながら記事が少ないので注意が必要です）
    + 参考サイト
        + [Parallel Pattern Library](https://faithandbrave.hateblo.jp/entry/20081028/1225184552)
        + [並列アルゴリズム](https://docs.microsoft.com/ja-jp/cpp/parallel/concrt/parallel-algorithms?view=msvc-160)
    + [コード１へ(for)](#pplparallel_for)
    + [コード２へ(for_each)](#pplparallel_for_each)

#### 3. OpenMP
   
+ 非常に有名だと思います。実質、標準の並列処理ライブラリです。[^7]
    + 難易度
        + 導入コスト：★☆☆（プロパティーの設定をいじって、インクルードするだけです）
        + 学習コスト：★☆☆（通常書いているプログラムコードに特定のコードを追加するだけで使えます）
        + 資料数　　：★★★（流石に有名なので、使い方の記事などもとても多いですね）
    + 参考サイト
        + [OpenMPの基本的な使い方](https://qiita.com/nocturnality/items/cca512d1043f33a3da2c)
        + [Visual Studio C++ で最低限OpenMPをサクッと使う方法](https://qiita.com/tatsubey/items/447a00ece637823e5f00)
        + [C++ 高速化 OpenMP](http://www.sanko-shoko.net/note.php?id=9twp)
        + [OpenMPによる並列化実装](http://www.eccse.kobe-u.ac.jp/assets/images/simulation_school/kobe-hpc-spring-intermediate2019/3dc2a486a4fb814eb28d79a136d990af3933934d.pdf)
    + [コードへ](#openmp)

[^7]: これだけ、Wikiさんにハッキリと開発が書いていないんですが、恐らく、Intelかと思います。企業らしい文字はこれだけだったので...。

## 環境
+ エディター：VisualStudio2019 C++17
+ 実行環境：Release x64
+ OS：Windows 10 Home
+ CPU：Intel(R) Core(TM) i7-9750H CPU ＠ 2.60GHz
+ GPU：NVIDIA GeForce RTX 2070

# 結論
　「合計時間（一処理毎の平均時間）」という形で計算結果をのせます。単位は**ミリ秒（ms）**です。

<details><summary>ある悲しい事件</summary><div>
　この記事のプログラムを書いている時にキーボードが逝かれて、数万円が吹き飛びました。寿命は１年半でした...。もっと、大切に扱うべきだったなぁ...
</div></details>

## シングルスレッド
| 要素数 \ 種類 | for | for each | std::for_each |
|:-:|:-:|:-:|:-:|
|100万|40.04 (0.40)|50.43 (0.5)|54.14 (0.54)|
|500万|227.55 (2.27)|272.23 (2.72)|324.27 (3.24)|
|1000万| 436.84 (4.36) | 546.12 (5.46) | 554.27 (5.54) |
|5000万|2101.77 (21.01)|2717.71 (27.17)|2803.22 (28.03)|
|1億|4516.3 (45.16)|5496.55 (54.96)|5514.25 (55.14)|

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/2809bba6-f465-2b7a-2c24-1ddd0099047a.png)
　見た感じ、シンプルな``for``文が速く、``for each``と``std::for_each``はほとんど変わらずといった感じです。といっても、１億ループ回してようやく約１秒なので余り気にしても仕方ないと思います。実質、通常使う範囲では誤差は無いという事です。

## マルチスレッド
| 要素数 \ 種類 |for_each(par)|for_each(par_unseq)|PPL(parallel_for)|PPL(parallel_for_each)|OpenMP|OpenMP(処理部)|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|100万|24.05 (0.24)|22.63 (0.22)|35.20 (0.35)|26.96 (0.26)|59.51 (0.59)|19.56 (0.19)|
|500万|122.98 (1.22)|156.2 (1.56)|113.23 (1.13)|118.22 (1.18)|294.55 (2.94)|140.97 (1.4)|
|1000万| 342.76 (3.42) | 322.20 (3.22) |346.50 (3.46)|261.30 (2.61)|994.98 (9.94)|225.77 (2.25)|
|5000万|1801.08 (18.01)|1677.68 (16.77)|1276.4 (12.76)|1278.37 (12.78)|3165.78 (31.65)|676.58 (6.76)|
|1億|3509.56 (35.09)|3408.26 (34.08)|3531.71 (35.31)|2530.28 (25.30)|6206.19 (62.06)|1450.94 (14.5)|

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/39898f55-8840-6809-db0e-632f9d30de3c.png)
　どう見ても、OpenMPの時間がかかりすぎです...。シングルスレッドより遅くなっています。流石におかしいので、OpenMPの**実際の処理部分**を上図の<font color="LimeGreen">**緑の点線**</font>として記入してみると、とても速くなります。という事は、他のマルチスレッドライブラリと比べて「**スレッド生成・削除コスト**」が大きいのが分かります。

　具体的には、スレッド生成・削除をループの外側で書き、実際の処理部分とスレッド生成・削除を分割したところ「１億ループで1450.94ms」になりました。つまり、「**スレッド生成する場所に気を付けろ～**」という事になります。

　かなり辛口で言ってしまいましたが、ここで載せているマルチスレッドライブラリにはない利点は、「スレッドの生成・削除と処理部分を簡単に分割可能」と「既存のコードをほとんど壊さずにマルチスレッドプログラミングが可能」な部分だと思いました[^5]。恐らく「スレッドの生成・削除と処理部分」を分けようと思うと、``std::thread``などを使う事になるので、本末転倒のような気もしなくもありません。

[^5]: 私がそう勝手に思っただけで、本当は違うという事は十分にあり得るので、間違えていたらごめんなさい。

## シングル・マルチスレッドの平均値
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/bbd5241d-c58f-7653-0626-e270dddc7bf1.png)

　このグラフはシングル・マルチスレッドの値の平均値をグラフ化したものになっています。見た感じ、1000万まで双方あまり変わりませんが、1000万より上になってくるとかなり異なってきます。今回のFor文の中身はほとんど皆無に等しいですが、実際使う場面になってくると、少ない段階からもっと差が広がってくると思います。

## 各パラメータの順位
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/8267f5cf-7277-5164-c65a-8764528e86a6.png)

　今回からグラフを導入した記事を書いてみました。やはり、数字だけのグラフでは見づらいと思い、視覚的に確認できるグラフがあるといいと思い導入してみました。今まで、Excelとかはほとんど使ってこなかったので、Excelのありがたみを感じています（笑）
　そして、これらの結果・見て下さっている皆さんの感覚・実行環境で使うライブラリを決める参考にしてみて下さい。

# コード
　以下の処理部分のコードを見ていただくと分かるのですが、四則演算した後に、``` += 10;```している部分があります。というのも、こう書かないと、```std::for_each```のシングルスレッド処理がどう考えても飛ばされているので、仕方なくこうしています。Debugではうまく動いていたので、Releaseによる最適化処理が走って「結果変わらないから、これ意味ねぇじゃん」という感じに、```std::for_each```の部分が飛ばされているせいだと思います。[^1]
　それともう一つ、配列の要素数チェックも行っています。本来なら必要ないのですが、CUDAを使う上でチェックを行わないとエラーを吐くので、他のパターンも含めて一律追加しています。結果、負荷チェックになると思っていますが。[^3]

　出来る限り平等にする為、それぞれのコード間に``system("pause");``を入れて、ファン全開モードもONにしました。というのも、ノートパソコンは熱が上がり易く[^4]、直ぐにCPUのクロック周波数が下がってしまうので仕方ありません。

[^1]: この部分だけ、最適化処理を無効化すればいい気もしますが、それでは平等になりません。なので、シンプルに全てに加算する対策をとりました。今回はあくまで処理時間を見たいだけで、処理の結果はどうでもいいのでこうしています。プロパティーから最適化設定をOffにするのは論外ですし...。
[^3]: GPUは条件式が苦手だった気がしますが、ここでは気にしないでおきます。
[^4]: 使用率100%が数十秒続くだけで、100℃近くになり、直ぐにサーマルスロットリングで周波数が下がるので...。ノートパソコンの弱点。

## 事前コード
```cpp:main.cpp
#include <numeric> // std::iotaの為
#include <algorithm> // std::for_eachの為
#include <execution> // std::execution::parなどの為
#include <ppl.h> // PPLを使う為
#include <omp.h> // OpenMPを使う為
#include <amp.h> // C++ AMPを使う為
#include <cuda_runtime.h> // CUDAを使うため

// 計算結果の表示用
template<size_t _Size>
void OutPutResult(const std::array<float, _Size>& times)
{
	namespace exec = std::execution;
	using std::cout;
	using std::endl;

	const float total_time{ static_cast<float>(std::reduce(exec::par, times.begin(), times.end())) };

	cout << "Total Time : " << total_time / 1000.f << " Millisecond" << endl; // 全体計算量
	cout << "Average Time : " << total_time / times.size() / 1000.f << " Millisecond" << endl << endl; // １ループ当たりの平均計算量
}

int main()
{
	namespace exec = std::execution;

	using namespace concurrency; // PPL・C++AMPの為

	using std::cout;
	using std::endl;

	constexpr size_t LoopNum{ 100 };
	static constexpr size_t ArrSize{ 10000000 };
	static constexpr int ConstNumber{ 10 }; // 加減算する値
	std::vector<int> num_array; // 実験対象
	std::vector<float> times; // 時間を保管しておく

	num_array.resize(ArrSize);
	times.resize(LoopNum, 0);

	std::iota(num_array.begin(), num_array.end(), 0);

	Timer timer;

	cout << "Array Size : " << ArrSize << ", Loop Size : " << LoopNum << endl << endl;

	cout << "Timer Start" << endl << endl;
```

## CPU-シングルスレッド
### ・for
```cpp:main.cpp
for (size_t i = 0; i < LoopNum; i++)
{
	timer.Start();
	for (size_t j = 0, length = num_array.size(); j < length; j++)
	{
		if (j >= ArrSize)	continue;

		num_array[j] += ConstNumber;
		num_array[j] -= ConstNumber;
		num_array[j] *= ConstNumber;
		num_array[j] /= ConstNumber;
		num_array[j] += 10;
	}
	timer.End();

	times[i] = timer.GetMicroTimer();
}

cout << "for(CPU : Singlethread) " << endl;
OutPutResult(times);
```

### ・for each（範囲for文）
```cpp:main.cpp
for (size_t i = 0; i < LoopNum; i++)
{
	timer.Start();
	for (int& num : num_array)
	{
		if (num >= ArrSize)	continue;

		num += ConstNumber;
		num -= ConstNumber;
		num *= ConstNumber;
		num /= ConstNumber;
		num += 10;
	}
	timer.End();

	times[i] = timer.GetMicroTimer();
}

cout << "for each(CPU : Singlethread) " << endl;
OutPutResult(times);
```

### ・std::for_each
```cpp:main.cpp
for (size_t i = 0; i < LoopNum; i++)
{
	timer.Start();
	std::for_each(num_array.begin(), num_array.end(), [](int& num)
		{
			if (num >= ArrSize)	return;

			num += ConstNumber;
			num -= ConstNumber;
			num *= ConstNumber;
			num /= ConstNumber;
			num += 10;
		});
	timer.End();

	times[i] = timer.GetMicroTimer();
}

cout << "std::for_each(CPU : Singlethread) " << endl;
OutPutResult(times);
```

## CPU-マルチスレッド
### ・std::for_each(std::execution::par)
```cpp:main.cpp
for (size_t i = 0; i < LoopNum; i++)
{
	timer.Start();
	std::for_each(exec::par, num_array.begin(), num_array.end(), [](int& num)
		{
			if (num >= ArrSize)	return;

			num += ConstNumber;
			num -= ConstNumber;
			num *= ConstNumber;
			num /= ConstNumber;
			num += 10;
		});
	timer.End();

	times[i] = timer.GetMicroTimer();
}

cout << "execution::par(CPU : Multithread) " << endl;
OutPutResult(times);
```

### ・std::for_each(std::execution::par_unseq)
```cpp:main.cpp
for (size_t i = 0; i < LoopNum; i++)
{
	timer.Start();
	std::for_each(exec::par_unseq, num_array.begin(), num_array.end(), [](int& num)
		{
			if (num >= ArrSize)	return;

			num += ConstNumber;
			num -= ConstNumber;
			num *= ConstNumber;
			num /= ConstNumber;
			num += 10;
		});
	timer.End();

	times[i] = timer.GetMicroTimer();
}

cout << "execution::par_unseq(CPU : Multithread, SIMD) " << endl;
OutPutResult(times);
```

### ・PPL（parallel_for）
```cpp:main.cpp
for (size_t i = 0; i < LoopNum; i++)
{
	timer.Start();
	parallel_for(0, (int) num_array.size(), 1, [](int num)
		{
			if (num >= ArrSize)	return;

			num += ConstNumber;
			num -= ConstNumber;
			num *= ConstNumber;
			num /= ConstNumber;
			num += 10;
		});
	timer.End();

	times[i] = timer.GetMicroTimer();
}

cout << "PPL parallel_for(CPU : Multithread) " << endl;
OutPutResult(times);
```

### ・PPL（parallel_for_each）
```cpp:main.cpp
for (size_t i = 0; i < LoopNum; i++)
{
	timer.Start();
	parallel_for_each(num_array.begin(), num_array.end(), [](int num)
		{
			if (num >= ArrSize)	return;

			num += ConstNumber;
			num -= ConstNumber;
			num *= ConstNumber;
			num /= ConstNumber;
			num += 10;
		});
	timer.End();

	times[i] = timer.GetMicroTimer();
}

cout << "PPL parallel_for_each(CPU : Multithread) " << endl;
OutPutResult(times);
```

### ・OpenMP
```cpp:main.cpp
for (size_t i = 0; i < LoopNum; i++)
{
	timer.Start();

#pragma omp parallel for
	for (int j = 0, length = num_array.size(); j < length; j++)
	{
		if (j >= ArrSize)	continue;

		num_array[j] += ConstNumber;
		num_array[j] -= ConstNumber;
		num_array[j] *= ConstNumber;
		num_array[j] /= ConstNumber;
		num_array[j] += 10;
	}

	timer.End();

	times[i] = timer.GetMicroTimer();
}

cout << "OpenMP(CPU : Multithread) " << endl;
OutPutResult(times);
```

# 感想
　今回色々と触ってみて思ったのが、PPLが想像以上に速い事です。というのも、以前少し使ってみたことがあるのですが、その時に「遅すぎない？」と思い、避けてきたと言う経緯がありました。今回の検証結果から見ると今後手段の一つとして考えても問題なさそうですね。
　そして、OpenMPについては内心使いづらいイメージがあり、今回初めて使いました。調べてみたりすると非常に簡単に使えるものなんですね。確かにこの手軽さなら有名になるのも納得です。ただ、私としてはたくさんある中の一つの手段ということになるとは思います。

# 次回へ
　この記事では、CPUを使った方法でfor文の速さを検証しました。[中編](https://qiita.com/HnniTns/items/9c69b9f34d4a77420352)はGPUを使った検証をしたいと思います。