C++の演算子の実行時間について

C++
1const int N = 100000000;
2

と

C++
1for (i = 0; i < N; i++) {
2    a[i] = i;
3    b[i] = i;
4}

をしておいた上で、
以下のコード(変数の宣言、for文,cに代入)の実行時間を計測します。

C++
1double d0, d1;
2
3d0 = 0.0; d1 = 0.0;
4for (int i = 0; i < N; i += 2) {
5    d0 += b[i + 0];
6    d1 += b[i + 1];
7}
8c = d0 + d1;

次に、上と同様の処理をd0,d1,d2,d3の4つで実行し、
その次にd0,d1,,d7の8で実行し、
16,32,64のもそれぞれ10回実行し、平均を取りました。

すると2~32回目までは実行時間が減り続けていたのですが、64回のものを試すと、32回のものより64回のもののほうが僅かに時間がかかっていました。

上のコードの演算子(=,+,<)の回数を比較すると、
32のときは309375075回
64のときは304687630回となっており、確かに64回の方が演算関数は少なくなっています。

にも関わらず全体の実行時間は64回の方が長くなっています。
ここで原因を突き止めたいと思い考えてみたところ、
「＋」と「＝」と「＜」の実行時間に差があるのではないか、と思ったのですが、
実際のところどうなのでしょう。

【補足】
少し補足します。

C++
1startTimer();
2double d0, d1, d2, d3;
3
4d0 = 0.0; d1 = 0.0; d2 = 0.0; d3 = 0.0; 
5for (int i = 0; i < N; i += 4) {
6    d0 += b[i + 0];
7    d1 += b[i + 1];
8    d2 += b[i + 2];
9    d3 += b[i + 3];
10}
11c = d0 + d1 + d2 + d3;
12
13stopTimer();

以上のようなコード（これは4つバージョン）でかかる時間を計測し、2,4,8,16,32,64のバージョンもそれぞれ試して、その実行時間の差を比べます。

するとコード内の演算子（+,=,<)の数が異なるので、実行時間い差が生じます。
例えば変数が2個の場合は、
「＝」が 3N/3 + 4回
「＋」が 5N/2 + 1回
「<」が 1N/2 + 1回で
合計で,(9N/2 + 6)回演算が行われていることになります。

また、変数が4つの場合は、合計で(15N/4 + 10)回の演算が行われているので、この演算の回数に依存するので、変数が増えれば増えるほど実行時間が短くなるのかなと思っていました。

しかし、この変数を32個、64個と増やしていくと、32個のときよりも64個のときのほうが時間(+0.002秒ほど)がかかってしましました。
演算の回数自体は64個のもののほうが少ないので、直感的には64個のもののほうが32個のものよりも短くなると思うのですが、どうしてこんな結果が出るのでしょうか。

【補足に補足】
回答していただいた3人の方、ありがとうございます。
「C++はコンパイル時に最適化されるので、どんなふうに書いても、それは今回の質問内容に対する議論にはならない」と、あるのですが、まだちゃんと納得することができていません。

実際、段数が2回のときと4回のときの実行時間(10回行ったものの平均)は
2: 0.12299
4: 0.07963
となっており、この辺では大幅に効果が出ています。
どんなコードでも同じ挙動を示すものなら最適化され、最も良いもので実行されるのであれば、こんな風にはならない気がします。

また、僕は普段はC++を使っていないので、友だちに聞いた方法でコンパイルしたのですが、それは「windowsPCのコマンドプロンプトで<code>cl ファイル名.cpp</code>を実行」するものです。このコンパイルの方法が最適化されたものなのかどうかはわかっていません。

またソフトウェアパイプラインのwikiのページでは、こんな記述がありました。

パイプライン化された（命令パイプラインの記事を参照）プロセッサの実行ユニットで効率良く実行できるように命令スケジューリングできるよう、プログラムを変形するという手法である。高度なコンパイラではコンパイラ最適化により行われることもあるが、一般にはしばしば、多数回繰り返されるが1回の処理内容がごくわずかなループ（画像処理や信号処理などには多い）について、手作業で、一種のアウト・オブ・オーダー実行のようなプログラムの書換え（ループの繰返しをまたいで、コードの順序を前後に入れ替えることが多い）を行う。

と、あります。以上の結果と、このページの説明を見ると、最適化されておらず、やはり変数の数を変えることで実行時間に影響があるのかなと感じます。

そして、その上で僕が知りたくて四苦八苦しているのは、以上のことが前提としてある上で、「なぜ64個の方が32個のものより時間がかかったのか」なのです。

長々と、そして何度も補足してすみません。

どなたかわかる方がいらっしゃれば教えて頂けるとうれしいです。
よろしくお願いします。

行動規範の内容に同意します

回答3件

残念ながら、このコードでは実行内容について何も議論できません。

というのも、C++では最適化が許されているため、最終的な外部とのやり取りがおなじになるのであれば、どんなコードを生成してもかまわないからです。

極端な話、猛烈に優秀なコンパイラなら、コンパイル時にすべての計算結果が決まるので、それを決め打ちにしておく、というコンパイルをやっても全く問題ありません。

投稿2017/07/26 10:29

maisumakun

総合スコア145183

momon-ga

2017/07/26 10:49

自前でループ最適化をやってる感じですよね。コンパイラオプションで、最適化を無効にすることを前提にしたら、議論の土台にのりますか？計測は難しいので完全に無風なのかも気になりますが。

maisumakun

2017/07/26 10:53

最適化を無効にする方法として、「volatile」という手段もあります。volatileを冠した変数への書き込み、読み出しはすべて書いたとおりに行われます。ただ、実行時間は演算回数だけでなくて、それがCPUでどのように並行実行できるか、さらにはコードやデータがレジスタやキャッシュにどう割り当てられるかなどにも依存しますので、本気で追いかけたいなら逆アセンブルして、CPUの動作と照らし合わせて考える必要があります。

行動規範の内容に同意します

ベストアンサー

32→64で、ループ１回分のコードサイズは確実に長くなります。そのため、命令キャッシュに収まりきらなくなった、或いは命令キャッシュミスの発生頻度が上がった（そのプログラム実行中、他のコード…OSや種々の割込み処理等…も動作するのだから）、可能性を挙げます。

ソフトウェアパイプラインのwikiのページでは

このページにも「ループ部分のコードは12倍以上増加する(使用するメモリ量に影響するだけでなく、キャッシュ性能にも影響する。コードの膨張参照)」という記述があります。

ただ、こちらはそのプログラムコードのサイズがわからないばかりか、命令キャッシュの具体的なサイズを把握しておらず、机上の思いつきであることを予めお断りいたしますw

投稿2017/07/27 07:55

rubato6809

総合スコア1380

退会済みユーザー

2017/08/03 03:49

返信遅くなってすみません。rubato6809さんの回答とwikiを読むことで理解が進みました。ありがとうございました。

行動規範の内容に同意します

（maisumakunさんと同意見ですが、いくつか私見を追加しています。）

質問中のソースコード変形は「ループ展開(loop unrolling)」と呼ばれる最適化技法です。このような最適化処理は基本的にコンパイラの仕事（コンパイル時に勝手に行われる）ですが、状況によってはプログラマ自身の手によるループ展開が有用なケースもあります。ソースコード変形による手動最適化はむやみに行うべきではなく、必ず実プログラムによる計測で効果が得られることを確認しながら行うものです。【最適化の大原則】

するとコード内の演算子（+,=,<)の数が異なるので、実行時間い差が生じます。
演算の回数自体は64個のもののほうが少ないので、直感的には64個のもののほうが32個のものよりも短くなると思うのですが、どうしてこんな結果が出るのでしょうか。

演算回数がひとつの目安であることは否定しませんが、モダンなCPU・OS・コンパイラによる実行環境下ではあまり大きな性能要因とはならないことが多いです。ループ展開の意義を議論するようなケースでは、C++ソースコードレベルの議論ではほとんど意味が無く、コンパイル後の生成アセンブリコードを確認する必要があるでしょう。

ループ展開に関連する性能要因は、CPU動作レベル（＝CPU命令＋実行時の様子）での分岐予測の状況、データキャッシュミス、命令キャッシュミス、命令レベル並列実行(IPC=Instruction Per Cycle)といった観点で議論されるものです。

追記