【配列の要素数による処理速度の違い】なぜ多い方速くなるのか知りたいです！

Question

前提・実現したいこと

C言語で配列へのアクセス順序による処理速度の違いを調べるために、2次配列のコピーを行うコード内のfor文のi,jを入れ替えたものをそれぞれ実行し、timeコマンドで実行時間を調べ、格納されている場所が近いほどキャッシュの恩恵を受けられて実行速度は速くなるということは分かったのですが、今度は用意する配列の要素数を１ずつ増やして実行してみると、実行時間は増やす前と比べて速くなりました。一見参照する数が増えた分遅くなりそうな気がするのですが、処理速度が速くなるのはなぜでしょうか？

該当のソースコード

【C言語】

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define N 32768

char a[N+1][N+1]; //ここがa[N][N]の時と実行時間の比較
char b[N+1][N+1]; //ここがb[N][N]の時と実行時間の比較

main(){
　　int i, j;

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

　　return 0;
}

Comments

[Kaleidoscope]

速さの違いとはどの程度でしょう？ミリ秒単位であれば誤差の世界です。
コンパイラの最適化オプションや測定時の環境で実行時間は変わりますので、
それらの環境も記載ください。

[退会済みユーザー]

すいません！
[N][N]の時で15.77秒
[N+1][N+1]の時で10.82秒
と大きな誤差でした。
ちなみに
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
の場合は圧倒的に速く2.11秒で終わりました。
初心者の為、最適化オプション？などはよくわからないのですが、結果はこうなると保証されている中で理由を考える問題でした。ヒントは「メモリ番地」とのことで、自分でよく考えてみたのですが、結局分からなかったので質問しました。

[退会済みユーザー]

メモリ配置上jは連続しているので、ポインタのインクリメントで次を参照出来るので早くなります。場合によっては専用命令に置き換わります。また、連続したメモリアクセスをしたほうが、よりキャッシュに入り易くなります。
本当に細かくつめるなら、他の方が言ってるように平均を取ったり、メモリアライメントを揃えたり、出力されたアセンブリコードまで確認するくらいまでやるべきです。

[退会済みユーザー]

それは[0][0],[0][1],[0][2]…と参照していく場合(内側for文がj)と[0][0],[1][0],[2][0]…と参照していく場合(内側for文がi)を比較したときに出る差の原理だと認識していたのですが、今回のような[0][0],[1][0],[2][0]…と参照していく(内側for文がi)という条件は一緒で、最初に定義する配列の要素数を上記のように増やした場合についてはどうでしょうか？　理解せず変なことを言っていたらすいません。。

[退会済みユーザー]

要素数増やして早くなるのはちょっと理由判らないですね。平均とっても早い感じです？

[退会済みユーザー]

＜[N][N]の場合１＞
$ /usr/bin/time ./a.out
16.27user 0.04system 0:16.33elapsed 99%CPU (0avgtext+0avgdata 1051032maxresident)k
0inputs+0outputs (0major+1681minor)pagefaults 0swaps

＜[N][N]の場合２＞
$ /usr/bin/time ./a.out
16.05user 0.05system 0:16.10elapsed 99%CPU (0avgtext+0avgdata 1051032maxresident)k
0inputs+0outputs (0major+1682minor)pagefaults 0swaps

＜[N+1][N+1]の場合１＞
$ /usr/bin/time ./a.out
11.09user 0.05system 0:11.14elapsed 99%CPU (0avgtext+0avgdata 1051032maxresident)k
0inputs+0outputs (0major+1705minor)pagefaults 0swaps

＜[N+1][N+1]の場合２＞
$ /usr/bin/time ./a.out
10.95user 0.05system 0:11.01elapsed 99%CPU (0avgtext+0avgdata 1051032maxresident)k
0inputs+0outputs (0major+1705minor)pagefaults 0swaps

何回も実行したところ、やはり[N+1][N+1]の方が5秒ほど速いという結果は変わりませんでした。。

[dodox86]

ページサイズとか割り当てメモリのアラインメントが関係あるとして、今はN=32768でページサイズの等倍ですが、N=32769とかにして、NとN+1の計測をすると状況が変わったりしませんでしょうか。

[退会済みユーザー]

<[N][N]でN=32768の場合>
$ cat n.c
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define N 32768
char a[N][N];
char b[N][N];
main()
{
int i, j;
for (j = 0; j < N; j++)
for (i = 0; i < N; i++)
b[i][j] = a[i][j];
return 0;
}
$cc n.c
$ /usr/bin/time ./a.out
15.43user 0.05system 0:15.48elapsed 99%CPU (0avgtext+0avgdata 1051032maxresident
0inputs+0outputs (0major+1681minor)pagefaults 0swaps

<[N][N]でN=32769の場合>
$ cat n.c
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define N 32769 //32769に変えました
char a[N][N];
char b[N][N];
main()
{
int i, j;
for (j = 0; j < N; j++)
for (i = 0; i < N; i++)
b[i][j] = a[i][j];
return 0;
}

$cc n.c
$ /usr/bin/time ./a.out
10.79user 0.04system 0:10.84elapsed 99%CPU (0avgtext+0avgdata 1051032maxresident
0inputs+0outputs (0major+1714minor)pagefaults 0swaps

<[N+1][N+1]でN=32768の場合>
$ cat n1.c
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define N 32768
char a[N+1][N+1];
char b[N+1][N+1];
main()
{
int i, j;
for (j = 0; j < N; j++)
for (i = 0; i < N; i++)
b[i][j] = a[i][j];
return 0;
}

$cc n1.c
$ /usr/bin/time ./a.out
10.98user 0.04system 0:11.03elapsed 99%CPU (0avgtext+0avgdata 1051028maxresident
0inputs+0outputs (0major+1705minor)pagefaults 0swaps

<[N+1][N+1]でN=32769の場合>
$ cat n1.c
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define N 32769 //32769に書き換えた
char a[N+1][N+1];
char b[N+1][N+1];
main()
{
int i, j;
for (j = 0; j < N; j++)
for (i = 0; i < N; i++)
b[i][j] = a[i][j];
return 0;
}
$cc n1.c
$ /usr/bin/time ./a.out
11.00user 0.04system 0:11.05elapsed 99%CPU (0avgtext+0avgdata 1051032maxresident
0inputs+0outputs (0major+1738minor)pagefaults 0swaps

結果は以上のようになりました。書き換えの際間違いがあるといけないのでcatで表示して確認してから実行しました。どうやら配列の要素数が32768の時と32769の時に大きな時間差が出るようで、32770になる時と32769の時の差はないようでした。

[dodox86]

思い付きでのコメントですが、CPUキャッシュメモリの問題もあるかもしれませんね。それと、32768と32769は4096を単位とすると境界をまたいでいますが、32769,32770はそうではありません。何か関係ありそうです。（あくまで思い付きです）

[退会済みユーザー]

なるほど！気づきませんでした。なにか関係ありそうですね。ちょっと調べてみます。

Answer 1

その程度だと誤差なので、時間を測る度に変動し、増えたり減ったりします。

NとN+1でなくもっと差を付けた上で、時間測定をそれぞれ1万回繰り返してみて平均を取るとかすればどうでしょうか？
#追記
Nと最適化オプションを変えながら３回ずつ実行してみました。

for o in 0 1 2 3
do
  for n in 32767 32768 32769
  do
    gcc -O$o -DN=$n -o aa aa.c
    echo -O$o N=$n `sh -c "time ./aa" 2>&1`
    echo -O$o N=$n `sh -c "time ./aa" 2>&1`
    echo -O$o N=$n `sh -c "time ./aa" 2>&1`
  done
done

結果は、下記の通り。32768の時だけ効率の悪いコードが生成されるようですが、-O1で解消します。また、-O3で極端な最適化がされてますが、これはもしかするとaがオールゼロということに依存しているかも。

いずれにせよ、32768の時の挙動はメモリの局所か云々とは関係ないようです。

-O0 N=32767 real 0m36.468s user 0m35.531s sys 0m0.947s
-O0 N=32767 real 0m36.067s user 0m35.079s sys 0m0.992s
-O0 N=32767 real 0m35.462s user 0m34.546s sys 0m0.925s
-O0 N=32768 real 0m41.269s user 0m40.445s sys 0m0.832s
-O0 N=32768 real 0m41.422s user 0m40.604s sys 0m0.828s
-O0 N=32768 real 0m40.849s user 0m40.014s sys 0m0.841s
-O0 N=32769 real 0m35.384s user 0m34.431s sys 0m0.963s
-O0 N=32769 real 0m35.304s user 0m34.338s sys 0m0.972s
-O0 N=32769 real 0m35.321s user 0m34.338s sys 0m0.991s
-O1 N=32767 real 0m37.349s user 0m36.368s sys 0m0.991s
-O1 N=32767 real 0m36.908s user 0m35.982s sys 0m0.937s
-O1 N=32767 real 0m38.006s user 0m36.998s sys 0m1.005s
-O1 N=32768 real 0m36.027s user 0m35.181s sys 0m0.857s
-O1 N=32768 real 0m35.852s user 0m34.985s sys 0m0.869s
-O1 N=32768 real 0m35.931s user 0m35.117s sys 0m0.823s
-O1 N=32769 real 0m36.885s user 0m35.851s sys 0m1.036s
-O1 N=32769 real 0m37.754s user 0m36.699s sys 0m1.064s
-O1 N=32769 real 0m37.556s user 0m36.614s sys 0m0.943s
-O2 N=32767 real 0m37.712s user 0m36.437s sys 0m1.274s
-O2 N=32767 real 0m38.905s user 0m37.538s sys 0m1.377s
-O2 N=32767 real 0m38.007s user 0m36.634s sys 0m1.372s
-O2 N=32768 real 0m36.707s user 0m35.564s sys 0m1.153s
-O2 N=32768 real 0m36.210s user 0m35.069s sys 0m1.141s
-O2 N=32768 real 0m36.290s user 0m35.123s sys 0m1.177s
-O2 N=32769 real 0m37.559s user 0m36.406s sys 0m1.151s
-O2 N=32769 real 0m38.134s user 0m37.114s sys 0m1.030s
-O2 N=32769 real 0m37.429s user 0m36.410s sys 0m1.015s
-O3 N=32767 real 0m37.227s user 0m36.202s sys 0m1.021s
-O3 N=32767 real 0m38.070s user 0m37.100s sys 0m0.979s
-O3 N=32767 real 0m37.569s user 0m36.614s sys 0m0.949s
-O3 N=32768 real 0m9.433s user 0m8.587s sys 0m0.849s
-O3 N=32768 real 0m9.605s user 0m8.753s sys 0m0.853s
-O3 N=32768 real 0m9.471s user 0m8.638s sys 0m0.835s
-O3 N=32769 real 0m37.490s user 0m36.478s sys 0m1.018s
-O3 N=32769 real 0m37.814s user 0m36.699s sys 0m1.115s
-O3 N=32769 real 0m37.140s user 0m36.178s sys 0m0.971s

Comments

[退会済みユーザー]

すいません！
[N][N]の時で15.77秒
[N+1][N+1]の時で10.82秒
と大きな誤差でした。
ちなみに
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
の場合は圧倒的に速く2.11秒で終わりました。
結果はこうなると保証されている中で理由を考える問題でした。ヒントは「メモリ番地」とのことで、自分でよく考えてみたのですが、結局分からなかったので質問しました。
上記のような飛び飛びにアドレスを参照するようなfor文の書き方だと配列の要素数が大きく処理速度に関係してくるなどありますか？

[退会済みユーザー]

なるほど！メモリの局所は関係なさそうですね。
試行していただきありがとうございます！

[otn]

32767と32769を比べると、誤差の範囲かと思います。

[momon-ga]

すいません。C言語うとくgccのオプションの理解もあやしいのですが、当該検証コードは
配列宣言時のNに対して+1するものでなく、defineのNの値を変更するものという理解でよいでしょうか？

当該質問は、ループの回数はNのままで、確保する配列の数を増やという意味だと思っていたのですが、これは私の認識違いでしょうか？
※ソースのforループにN+1するという記述がなかったので、そう思ってました。

つまり、ループ回数は変わらないが、メモリの配置？の仕方でパフォーマンスが変わるのか？という趣旨なのかなと思っていました。

検証するならNとは別の定義をして、Nは、そのままで配列の宣言している部分(新しいDefine)だけ変更するのかなぁというイメージです。

そもそも的外れな内容でしたら、ごめんなさい。

[otn]

ああ、なるほど。追記のテストでは、ループ回数まで変化しちゃってましたね。
うっかりしてました。momon-gaさんのご認識の通りだと思います。
時間掛かるので、テストし直しはしませんが、結果の時間は大差ないと思います。

[momon-ga]

返答ありがとうございました。
たしかに、実際にループ回数増えても時間に差がでないというより、
-O3 N=32768について、調べないといけないんでしょうかねぇ。

Answer 2

コンパイルオプションで、アセンブルコードを出すオプションがあるので、それでアセンブルコードを出して見比べてはどうでしょうか
そこでなにか違いが出るかどうかですね

おそらくOSのメモリマネージャの挙動の問題かと思われますが。