このページでは、特に配列アクセスの高速化について解説します。
for(x = 0; x < 4096; x++){
for(y = 0; y < 4096; y++){
array2[y][x] = array1[y][x];
}
}for(y = 0; y < 4096; y++){
for(x = 0; x < 4096; x++){
array2[y][x] = array1[y][x];
}
}
どっちも array2 に array1 の値をコピーしてるループ文だね
同じことやってるから同じじゃないの？
同じことをやっているループ文ですが、実は速度には大きな差があります。配列へのアクセス順が違うだけで大きく速度に差が出ます。
この理由についてこのページで解説していきます。
配列へのアクセス順による速度の差
まずは「配列へのアクセス順の違い」により、どの程度処理速度に差が出るのか下記プログラムで確認してみましょう。
#include <stdio.h>
#include <time.h>
/* 配列の大きさ */
#define WIDTH 4096
#define HEIGHT 4096
/* 配列 */
char array1[HEIGHT][WIDTH];
char array2[HEIGHT][WIDTH];
char array3[HEIGHT][WIDTH];
int main(void){
unsigned int x, y;
clock_t start, end;
int *out, *in;
/* コピー元の配列を初期化 */
for(x = 0; x < WIDTH; x++){
for(y = 0; y < HEIGHT; y++){
array1[y][x] = 50;
}
}
/* 配列のコピー１ */
start = clock();
for(x = 0; x < WIDTH; x++){
for(y = 0; y < HEIGHT; y++){
array2[y][x] = array1[y][x];
}
}
end = clock();
printf("%f[sec]\n", (double)(end - start) / CLOCKS_PER_SEC);
/* 配列のコピー２ */
start = clock();
for(y = 0; y < HEIGHT; y++){
for(x = 0; x < WIDTH; x++){
array3[y][x] = array1[y][x];
}
}
end = clock();
printf("%f[sec]\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}4096 x 4096 の２次元配列 array1 のデータを同じサイズの array2 と array3 に２重ループを用いてコピーを行っています。
ただし、２重ループの順序（array2 では y のループが内側、array3 では x のループが内側）が異なるため、これにより配列のアクセス順序が異なることになります。
プログラムを実行すると、それぞれのコピーに要した CPU 時間を表示するようになっていますので、このアクセス順序によりどれくらい速度に差が出るのかは実行してみると確認できます。
私の PC で実行すると下記のように表示されました。
0.870658[sec] 0.102659[sec]
array2 と array3 に格納されるデータは同じですが、配列へのアクセス順序が異なるだけで array2 へのデータのコピーは array3 へのコピーの約９倍処理時間が長いことが確認できると思います。
ちなみに上記結果はコンパイル時の最適化オプションを OFF にした時のものになります。ただし、最適化オプションを ON （-O2 オプションを付加）しても、array3 へのコピーの方が圧倒的に速いという結果は変わりません。
速度の差の要因はキャッシュ
なぜこんなにも差が出るのでしょうか？ここからはこの差が発生する理由について解説していきたいと思います。
この差が発生する理由は、このページのタイトルにもあるように「キャッシュ」にあります。
スポンサーリンク
キャッシュとは
キャッシュとは CPU とメモリの間に配置されるデータを記憶するハードウェアです。
メモリアクセス速度は CPU の処理速度に比較してめちゃめちゃ遅いです。この速度差を埋めるために、このキャッシュが設けられています。
CPU はアクセスしたいデータがキャッシュに存在する場合はキャッシュにアクセスし、キャッシュに存在しない場合はメモリにアクセスします。
キャッシュはメモリと比較して下記のような特徴があります。
- メモリよりもアクセス速度が速い
- メモリよりも記録可能容量が小さい
ですので、キャッシュに格納されたデータにのみアクセスして処理ができれば、処理が高速になることになります。
逆にキャッシュに存在しないデータにアクセスする場合は処理速度が低下することになります。
キャッシュには、あるアルゴリズム（おそらくコンピュータアーキテクチャによって違う）に従ってデータが格納されます。
例えば下記のようなデータはキャッシュに格納されます。データにアクセスする度に、キャッシュのデータは更新されるようです。
- 最近使用したデータ
- 現在アクセスしているデータ付近のデータ
特に注目していただきたいのは「現在アクセスしているデータ付近のデータ」です。
あるアドレスのデータにアクセスした際、そのアドレス付近のデータはキャッシュに格納されることになるため、アドレスの近いデータへのアクセスは非常に高速に実行することができます。
配列アクセス順序とキャッシュの関係
で、ここで思い出していただきたいのが前述の main.c です。このプログラムでは２次元配列を利用しています。
ここで少し、この２次元配列の各データがメモリ上にどのように配置されるかについておさらいをしておきたいと思います。
例えば２次元配列 a[3][4] であれば、下の図のような配列をイメージするのではないかと思います。要は要素数 5 の配列が縦方向に 3 つ並ぶイメージです。
この時、２次元配列において “後ろ側の添字” で指定する値を増加した場合、アクセスするデータが横方向に移動することになります。その一方で、”前側の添字” で指定する値を増加した場合、アクセスするデータが縦方向に移動することになります（行が変化する）。
具体的には、変数 x と変数 y を用いて a[y][x] にアクセスする場合、アクセスするデータは、x を増やせば横方向に、y を増やせば縦方向に移動することになります。
ここまで紹介してきたソースコードで、配列にアクセスする際に array1[y][x] という風に、前側の添字に y、後ろ側の添字に x を指定しているのを見て違和感を感じた方もおられるかもしれません。
これは、上記の２次元配列のイメージ図において、アクセスするデータを縦方向に移動するための添字を y、横方向に移動するための添字を x としたかったからです（逆に array1[x][y] でアクセスしてしまうと、x が縦方向、y が横方向に移動するための添字となってしまって数学等の座標のイメージと合わなくなってしまいます）。
で、ここまではあくまでもイメージの話で、実際には２次元配列の各データは、下の図のようにメモリ上に横に並べる形で配置されます（縦に並べる形でもいいです、要は１次元的に配置されます）。
なので、a[y][x] で配列のデータにアクセスする場合、a[y][x] に対して a[y][x + 1] はメモリ配置的にすぐ近く（隣）に存在しますが、a[y][x + 1] はメモリ配置的に遠くに存在することになります。
ここで前述で紹介したソースコード main.c について考えてみましょう。main.c では２次元配列を使用しており、その１つである array1 の各データは下記のようにメモリ上にデータが配置されることになります（array1 の例ですが array2 も array3 も同様です）。
ポイントは前述の通り、array1[y][x] に対し、array1[y][x + 1] はすぐ隣に存在するものの、array1[y + 1][x] は遠くに存在する点です。
ここでキャッシュを考慮すると、例えば array1[y][x] にアクセスしている場合、array1[y][x] 付近のデータがキャッシュに格納されることになります。
上の図はアクセスされたデータの上位方向４バイト分をキャッシュに格納されるイメージです（本当は下位方向のバイトや格納されるバイト数も正確ではないですが、イメージとしてはこんな感じでキャッシュにデータが格納されます）。
array1[y][x + 1] は「現在アクセスしているデータ付近のデータ」となりますので、キャッシュに格納されることになります。
したがって、array1[y][x] の次に array1[y][x + 1] のデータ取得を行った場合、高速に処理することが可能になります。
その一方で、 array1[y + 1][x] のデータは array1[y][x] から遠いアドレス（4096 Byte 分も離れている）にあるのでキャッシュには格納されません。
したがって、array1[y][x] の次に array1[y + 1][x] にアクセスするようなプログラムを作成すると処理時間が遅くなってしまいます。
つまり、下記のようにループ文を組めば今アクセスしているデータに対して常に次にアクセスするデータが近い位置にあるので、常にキャッシュからデータをアクセスできることができ、処理が高速になります。
for(x = 0; x < 4096; x++){
for(y = 0; y < 4096; y++){
array2[y][x] = array1[y][x];
}
}一方、下記のようにループ文を組むと、今アクセスしているデータに対して常に次にアクセスするデータが遠い位置にあるので、毎回メモリにアクセスする必要があるため（キャッシュにデータが存在しない）、処理が低速になります。
for(y = 0; y < 4096; y++){
for(x = 0; x < 4096; x++){
array2[y][x] = array1[y][x];
}
}これが配列へのアクセス順により（ループ文の記述の仕方により）、処理速度が大きく異なる理由になります。
ただし、本当に重要なのはアクセスする順序よりも、キャッシュにデータが格納されているかどうかです。
例えば上記の main.c の WIDTH と HEIGHT の定義を下記のように変更すると、アクセス順による処理速度の差はほとんど生じません。
実行結果は下記のようになりました。
0.119272[sec] 0.118094[sec]
２つのループによる２次元配列のデータコピーで処理速度に差が発生しない理由は、両方ともアクセスするデータがキャッシュに格納されているためです。
プログラム中に登場する２次元配列 array1 のデータはメモリ上に下記のように配置されます（array1 の説明ですが、array2 も array3 も同様です）。
つまり、array1[y][x] のデータに対し、array1[y][x + 1] も array1[y + 1][x] も十分近い位置にあるのでキャッシュに格納されることになります。
ですので、配列のアクセス順序にかかわらず、２つのループはほぼ同じ処理速度になるというわけです。
こんな感じで２次元配列の横方向のサイズが小さい場合は、配列へのアクセス順序はほぼ処理時間に影響なしとなります。
逆に２次元配列の横方向のサイズが大きい場合は、配列へのアクセス順序が処理時間に大きな影響を与えます。
基本的に２重ループの中で二次元配列にアクセスする場合は、下図のように配列の後ろ側の要素に対するループを内側に記述することで、キャッシュを有効利用できる可能性が高くなります。この書き方は癖をつけておいた方が良いと思います。
参考サイト
このページではキャッシュについてかなりぼかして解説を行いました。もっとキャッシュについて知りたい方は下記のページがおすすめです。私もこのページを参考にしてプログラムを作成しました。
http://myoga.web.fc2.com/prog/cpp/opti02.htm
スポンサーリンク
まとめ
このページではキャッシュを利用して配列アクセスを高速化する方法について解説しました。
キャッシュに格納されているデータへは高速にアクセスすることができます。そして、キャッシュが有効利用できるように配列へのアクセス順序を工夫することでプログラムを高速化することが可能です。
といっても、特にプログラミング入門者の方はそこまでキャッシュは意識する必要はないと思います。まずは読みやすいプログラムを書くことの方が重要です。
ただし、下記のことを知っておくとプログラムを高速化したい場合に役立つと思いますので、是非頭に入れておいてください！
- キャッシュが活用できるとプログラムが高速化できる
- 配列へのアクセス順序を工夫することでキャッシュが活用できる場合がある
画像処理を高速化する一例を下記ページでも紹介していますので、プログラムの高速化に興味のある方はこちらもぜひ読んでみてください！
【C言語】画像処理プログラムの高速化方法を解説
オススメの参考書（PR）
C言語学習中だけど分からないことが多くて挫折しそう...という方には、下記の「スッキリわかるC言語入門」がオススメです！
まず学習を進める上で、参考書は２冊持っておくことをオススメします。この理由は下記の２つです。
- 参考書によって、解説の仕方は異なる
- 読み手によって、理解しやすい解説の仕方は異なる
ある人の説明聞いても理解できなかったけど、他の人からちょっと違った観点での説明を聞いて「あー、そういうことね！」って簡単に理解できた経験をお持ちの方も多いのではないでしょうか？
それと同じで、１冊の参考書を読んで理解できない事も、他の参考書とは異なる内容の解説を読むことで理解できる可能性があります。
なので、参考書は２冊持っておいた方が学習時に挫折しにくいというのが私の考えです。
特に上記の「スッキリわかるC言語入門」は、他の参考書とは違った切り口での解説が豊富で、他の参考書で理解できなかった内容に対して違った観点での解説を読むことができ、オススメです。題名の通り「なぜそうなるのか？」がスッキリ理解できるような解説内容にもなっており、C言語入門書としてもかなり分かりやすい参考書だと思います。
もちろんネット等でも色んな観点からの解説を読むことが出来ますので、分からない点は別の人・別の参考書の解説を読んで解決していきましょう！もちろん私のサイトも参考にしていただけると嬉しいです！
入門用のオススメ参考書は下記ページでも紹介していますので、こちらも是非参考にしていただければと思います。
https://daeudaeu.com/c_reference_book/
[…] ≫多次元配列のメモリレイアウト方式について – Qiita≫【C言語】配列へのアクセス順序による処理速度の違い【キャッシュ】 _ だ… […]