質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.35%

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

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 443

cloudspider

score 86

const int N = 100000000;


for (i = 0; i < N; i++) {
    a[i] = i;
    b[i] = i;
}


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

double d0, d1;

d0 = 0.0; d1 = 0.0;
for (int i = 0; i < N; i += 2) {
    d0 += b[i + 0];
    d1 += b[i + 1];
}
c = 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回の方が長くなっています。
ここで原因を突き止めたいと思い考えてみたところ、
「+」と「=」と「<」の実行時間に差があるのではないか、と思ったのですが、
実際のところどうなのでしょう。

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

startTimer();
double d0, d1, d2, d3;

d0 = 0.0; d1 = 0.0; d2 = 0.0; d3 = 0.0; 
for (int i = 0; i < N; i += 4) {
    d0 += b[i + 0];
    d1 += b[i + 1];
    d2 += b[i + 2];
    d3 += b[i + 3];
}
c = d0 + d1 + d2 + d3;

stopTimer();

以上のようなコード(これは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個のものより時間がかかったのか」なのです。

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+2

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/26 19:49

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

    キャンセル

  • 2017/07/26 19:53

    最適化を無効にする方法として、「volatile」という手段もあります。volatileを冠した変数への書き込み、読み出しはすべて書いたとおりに行われます。

    ただ、実行時間は演算回数だけでなくて、それがCPUでどのように並行実行できるか、さらにはコードやデータがレジスタやキャッシュにどう割り当てられるかなどにも依存しますので、本気で追いかけたいなら逆アセンブルして、CPUの動作と照らし合わせて考える必要があります。

    キャンセル

checkベストアンサー

0

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/08/03 12:49

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

    キャンセル

0

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

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


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

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

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


追記

どんなコードでも同じ挙動を示すものなら最適化され、最も良いもので実行されるのであれば、こんな風にはならない気がします。

「コンパイラが全知全能であれば」あなたの理解通りのことが起こると思います。もちろん、現実的にはそんなことはありませんから、プログラマの記述したC++ソースコードによって実性能が左右されます。

それは「windowsPCのコマンドプロンプトで cl ファイル名.cpp を実行」するものです。このコンパイルの方法が最適化されたものなのかどうかはわかっていません。

Microsoft Visual C++コンパイラ(cl)のデフォルト動作では、最適化は行われません。

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

繰り返しになりますが、提示されているC++ソースコードからだけでは、確かなことは何も言えません。

個人的な経験則に基づく推測にすぎませんが、rubato6809さん回答にある「生成される機械語命令列が肥大化したことにより、実行時の命令キャッシュミスが発生しているため」が最も有力だと思います。

(ループ展開を 2 → 4 →... と進めていくと最初は性能向上がみられるが、展開回数を大きくすると性能劣化が始まるという状況からの類推)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/08/03 12:50

    返信遅くなってすみません。丁寧に回答してくださったおかげで大分理解が進みました。ありがとうございました。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.35%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る