More than 1 year has passed since last update.

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

Last updated at 2022-07-03Posted at 2021-05-17

最初に

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

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

検証方法

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

使用技術

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

CPU-シングルスレッド

1. for

Cプログラマーなら誰しもが通る道
コードへ

2.for each（範囲for文）

C++プログラマーなら誰しもが通る道
コードへ

3. std::for_each

マルチスレッドにする時に非常に使うようになる。それ以外で、わざわざ使う事はあまりないですね。
コードへ

CPU-マルチスレッド

1. std::execution

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

2. PPL(Parallel Pattern Library)

Microsoftが提供する、標準で付属している並列処理ライブラリです。知っている人はかなり少ないイメージです。
- 難易度
  - 導入コスト：★☆☆（インクルードするだけです）
  - 学習コスト：★★☆（いくつかあるライブラリ内の関数を使うので、使い方を覚えないといけません）
  - 資料数　　：★☆☆（残念ながら記事が少ないので注意が必要です）
- 参考サイト
  - Parallel Pattern Library
  - 並列アルゴリズム
- コード１へ(for)
- コード２へ(for_each)

3. OpenMP

非常に有名だと思います。実質、標準の並列処理ライブラリです。²
- 難易度
  - 導入コスト：★☆☆（プロパティーの設定をいじって、インクルードするだけです）
  - 学習コスト：★☆☆（通常書いているプログラムコードに特定のコードを追加するだけで使えます）
  - 資料数　　：★★★（流石に有名なので、使い方の記事などもとても多いですね）
- 参考サイト
- コードへ

環境

エディター：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）**です。

ある悲しい事件

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

シングルスレッド

要素数 \ 種類	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)

　見た感じ、シンプルな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)

　どう見ても、OpenMPの時間がかかりすぎです...。シングルスレッドより遅くなっています。流石におかしいので、OpenMPの実際の処理部分を上図の緑の点線として記入してみると、とても速くなります。という事は、他のマルチスレッドライブラリと比べて「スレッド生成・削除コスト」が大きいのが分かります。

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

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

シングル・マルチスレッドの平均値

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

各パラメータの順位

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

コード

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

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

事前コード

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

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文）

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

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)

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)

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）

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）

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

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文の速さを検証しました。中編はGPUを使った検証をしたいと思います。

あくまで、私での環境なのでその点だけ注意してください。 ↩
これだけ、Wikiさんにハッキリと開発が書いていないんですが、恐らく、Intelかと思います。企業らしい文字はこれだけだったので...。 ↩
私がそう勝手に思っただけで、本当は違うという事は十分にあり得るので、間違えていたらごめんなさい。 ↩
この部分だけ、最適化処理を無効化すればいい気もしますが、それでは平等になりません。なので、シンプルに全てに加算する対策をとりました。今回はあくまで処理時間を見たいだけで、処理の結果はどうでもいいのでこうしています。プロパティーから最適化設定をOffにするのは論外ですし...。 ↩
GPUは条件式が苦手だった気がしますが、ここでは気にしないでおきます。 ↩
使用率100%が数十秒続くだけで、100℃近くになり、直ぐにサーマルスロットリングで周波数が下がるので...。ノートパソコンの弱点。 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up