どのバージョンがより効率的で、なぜそうですか？ 両方とも同じ計算をするようです。コンパイラが（a）jで値を変更せず、何度も何度も計算する必要がないことをコンパイラが認識した場合のみ、私が考えることができます。 すべての入力は素晴らしいでしょう！どちらが良いメモリアクセスですか？ （C++）
#define M /* some mildly large number */
double a[M*M], x[M], c[M];
int i, j;
(a) First version
for (j = 0; j < M; j++)
for (i = 0; i < M; i++)
c[j] += a[i+j*M]*x[i];
(b) Second version
for (i = 0; i < M; i++)
for (j = 0; j < M; j++)
c[j] += a[i+j*M]*x[i];
これは、計算効率ではなくメモリアクセスパターンです。一般に、（a）はユニットストライドを持つメモリにアクセスするので高速ですが、これは（b）よりもはるかにキャッシュ効率が高く、ストライドはMです。 （a）各キャッシュラインが完全に利用されているのに対し、（b）では、各キャッシュラインから追い出される前に1つの配列要素のみが使用される可能性がある。
ループの並べ替えの最適化を実行するので、実際には、そのようになると違いは見られないかもしれません。いつものように、推測するのではなく、コードをベンチマーク/プロファイリングする必要があります。
私はユニットストライドの頭をしたことはありませんでした。私はウィキペディアでこれについて読んでいます。あなたの答えをありがとう:) – Samu
"ユニットストライド"は、この文脈で事実上単に「連続的に」または「連続的に」を意味します。 –
@ Samu：文字通り「一度に一歩」。それは、棚1から何かを得る代わりに、スーパーマーケットの通路を歩き、棚10から何かを得るために歩いてから、棚2に戻って棚11に歩いていくのではなく、スーパーマーケットの通路を歩く順番でアイテムを拾うようなものです。あなたのコンピュータは実際には棚1から10までのすべてを拾い上げて、あなたが何か歩くことをしなくても、あなたが望むものをチェリーピックアップできるという前提で始まります。そして今、それは棚1-10からすべてを拾い上げなければならない。次に棚11-20からすべてが、次に棚1-10からすべてが再び棚上げされなければならない。 –
対象のコンピュータで測定して調べます。 –
@PaulR：本物の質問 - 現代のコンパイラはこれを見つけず、ループプリアンブルを入れ替えることができますか？セマンティクスが同じであることを見ることは同じです。 –
@LightnessRacesinOrbit：はい、いくつかのコンパイラは、少なくともこのような単純なケースではループの並べ替えを行うことができます。 –