プログラマ専用SNS ミクプラ

今年からC言語を学び始めました。
このアクセス順のプログラムでサイズを20000にすると列:2.5(sec),行:9.3(sec)という結果になるのですがこの違いは何故ですか？
また、自分でも少し調べたのですが、C言語だと列で配列が確保されているから列でアクセスしたため高速になるそうなのですが、行による配列の確保、アクセスするにはプログラムをどう変えるべきか教えてください。
よろしくお願いします。

コード:

#include <stdio.h>
#include <time.h>
#include <sys/time.h>

#define n 20000
void sumij();
void sumji();
int  A[n][n];

int main() {
    struct timeval s, e;

    printf("サイズ：d\n", n);

    gettimeofday(&s, NULL);    
    sumij();
    gettimeofday(&e, NULL);    
    printf("列： %.2f (sec)\n", (e.tv_sec - s.tv_sec) + (e.tv_usec - s.tv_usec)*1.0E-6);    

    gettimeofday(&s, NULL);    
    sumji();
    gettimeofday(&e, NULL);    
    printf("行： %.2f (sec)\n", (e.tv_sec - s.tv_sec) + (e.tv_usec - s.tv_usec)*1.0E-6);    

    return 0;
}

void sumij() {
    int i, j, sum=0;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            sum += A[i][j] ;
        }
    }
}


void sumji() {
　int i, j, sum=0;
    for(j=0; j<n; j++) {
        for(i=0; i<n; i++) {
            sum += A[i][j] ;
        }
    }
}

KuKu さんが書きました:このアクセス順のプログラムでサイズを20000にすると列:2.5(sec),行:9.3(sec)という結果になるのですがこの違いは何故ですか？

列でアクセスするとCPUのキャッシュヒット率が上がるからだと思われます。

キャッシュについて：
コンピュータに搭載されているメインメモリ（4GBとかそのくらいのやつ）は非常にアクセスが遅いので、CPUの内部に高速で小容量のメモリが載っています。
それをキャッシュメモリと言います。
メインメモリにアクセスする命令を実行すると、アクセスしようとしているアドレスにあるデータだけでなく、その回りのデータも一緒にキャッシュメモリにコピーします。
2回目以降アクセスしたとき、既に欲しいデータがキャッシュに載っていれば、非常に高速にアクセスできるというわけですね。

列でアクセスすると、連続したアドレスにアクセスすることになり、欲しいデータがキャッシュに載っている可能性が高まります。
つまり、キャッシュを有効活用でき、速く実行できるわけです。

KuKu さんが書きました:また、自分でも少し調べたのですが、C言語だと列で配列が確保されているから列でアクセスしたため高速になるそうなのですが、行による配列の確保、アクセスするにはプログラムをどう変えるべきか教えてください。

まさにsumjiが行によるアクセスです。

C言語で2次元配列を確保すると、絶対に列になります。
a[n][m]という書き方が、nが行、mが列を表す決まりなので諦めましょう。

大変貴重な説明をどうもありがとうございます。

これからC言語にはかなりお世話になるため、自分で調べて分からないことはどんどん学んでいこうと思います。

こちらの質問に返答していただき本当にありがとうございました。

プログラマ専用SNS ミクプラ

アクセス順について

アクセス順について

Re: アクセス順について

Re: アクセス順について