プリフェッチをストライドしたときにループ順序が問題になるのはなぜですか？

Question

Cでは、配列がフードの下に格納され、行の主要な繰り返しがキャッシュライン全体を利用するため、行のメジャーな順序で行列を反復するように指示されます。これによりキャッシュミスが少なくなります。実際、私のマシンでは、行と列の大規模な繰り返しのパフォーマンスに大きな違いがあります。テストコード：

#include <stdio.h> 
#include <stdlib.h> 

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

int getTime() 
{ 
    struct timespec tsi; 

    clock_gettime(CLOCK_MONOTONIC, &tsi); 
    double elaps_s = tsi.tv_sec; 
    long elaps_ns = tsi.tv_nsec; 
    return (int) ((elaps_s + ((double)elaps_ns)/1.0e9) * 1.0e3); 
} 

#define N 1000000 
#define M 100 

void main() 
{ 
    int *src = malloc(sizeof(int) * N * M); 
    int **arr = malloc(sizeof(int*) * N); 
    for(int i = 0; i < N; ++i) 
    arr[i] = &src[i * M]; 

    for(int i = 0; i < N; ++i) 
    for(int j = 0; j < M; ++j) 
     arr[i][j] = 1; 

    int total = 0; 

    int pre = getTime(); 


    for(int j = 0; j < M; ++j) 
    for(int i = 0; i < N; ++i) 
     total += arr[i][j]; 

    /* 
    for(int i = 0; i < N; ++i) 
    for(int j = 0; j < M; ++j) 
     total += arr[i][j]; 
    */ 

    int post = getTime(); 

    printf("Result: %d, took: %d ms\n", total, post - pre); 
} 

しかし、現代のメモリ・システムは、ストライドのアクセスを予測することができ、あなたが列を反復処理するときに、非常に規則的なパターンを以下の通りですプリフェッチャーを持っています。これは、列メジャー反復が行メジャー反復と同様に機能するようにしてはいけませんか？

Answer 1

キャッシュラインは特定のサイズ（たとえば64バイト）を持ち、プロセッサは完全なキャッシュラインを読み書きします。処理されるバイト数と読み書きされるバイト数を比較します。