【C言語】配列へのアクセス順序による処理速度の違い【キャッシュ】

このページでは、特に配列アクセスの高速化について解説します。

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];
    }
}

同じことをやっているループ文ですが、実は速度には大きな差があります。配列へのアクセス順が違うだけで大きく速度に差が出ます。

この理由についてこのページで解説していきます。

配列へのアクセス順による速度の差

まずは下記プログラムで配列へのアクセス順の違いによりどの程度処理速度に差が出るかを確認してみましょう。

#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 へのコピーの約９倍処理時間が長いことが確認できると思います。

速度の差の要因はキャッシュ

なぜこんなにも差が出るのでしょうか？ここからはこの差が発生する理由について解説していきたいと思います。

この差が発生する理由は、このページのタイトルにもあるように「キャッシュ」にあります。

スポンサーリンク

キャッシュとは

キャッシュとは CPU とメモリの間に配置されるデータを記憶するハードウェアです。

メモリアクセス速度は CPU の処理速度に比較してめちゃめちゃ遅いです。この速度差を埋めるために、このキャッシュが設けられています。

CPU はアクセスしたいデータがキャッシュに存在する場合はキャッシュにアクセスし、キャッシュに存在しない場合はメモリにアクセスします。

キャッシュはメモリと比較して下記のような特徴があります。

• メモリよりもアクセス速度が速い
• メモリよりも記録可能容量が小さい

ですので、キャッシュに格納されたデータにのみアクセスして処理ができれば、処理が高速になることになります。

逆にキャッシュに存在しないデータにアクセスする場合は処理速度が低下することになります。

キャッシュには、あるアルゴリズム（おそらくコンピュータアーキテクチャによって違う）に従ってデータが格納されます。

例えば下記のようなデータはキャッシュに格納されます。データにアクセスする度に、キャッシュのデータは更新されるようです。

• 最近使用したデータ
• 現在アクセスしているデータ付近のデータ

特に注目していただきたいのは「現在アクセスしているデータ付近のデータ」です。

あるアドレスのデータにアクセスした際、そのアドレス付近のデータはキャッシュに格納されることになるため、アドレスの近いデータへのアクセスは非常に高速に実行することができます。

配列アクセス順序とキャッシュの関係

で、ここで思い出していただきたいのが前述の main.c です。

このプログラムでは２次元配列を利用しています。２次元配列では、下記のようにメモリ上にデータが配置されることになります（array1 の例ですが array2 も array3 も同様です）。

ここでキャッシュを考慮すると、例えば array1[y][x] にアクセスしている場合、array1[y][x] 付近のデータがキャッシュに格納されることになります。

上の図はアクセスされたデータの上位方向４バイト分をキャッシュに格納されるイメージです（本当は下位方向のバイトや格納されるバイト数も正確ではないですが、イメージとしてはこんな感じでキャッシュにデータが格納されます）。

array1[y][x + 1] は「現在アクセスしているデータ付近のデータ」となりますので、キャッシュに格納されることになります。

したがって、array1[y][x] の次に array1[y][x + 1] のデータ取得を行った場合、高速に処理することが可能になります。

しかし、array1[y][x] の次に 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 の定義を下記のように変更すると、アクセス順による処理速度の差はほとんど生じません。

#define WIDTH 2
#define HEIGHT 8388608

実行結果は下記のようになりました。

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言語】画像処理プログラムの高速化方法を解説