行列の要素への列方向または列方向へのアクセス

Question

行列A[i][j]が与えられます。行列の要素を追加したい場合は、どちらの方が優れているのですか？なぜですか？

1. 配列表現要素に連続したメモリ位置に格納されているので賢明

私の視点から列方向

行、行が賢明優れているので、それらにアクセスすることであるため以下time.Butを取りすべての場所をフェッチするRAMには同じ時間がかかりますが、それは重要ですか？

Answer 1

がCでSpatial Locality

を活用して、マトリックスはR ow-major orderに格納されています。したがって、要素a[i][j]にアクセスすると、要素a[i][j+1]へのアクセスがキャッシュにヒットする可能性が高くなります。メインメモリへのアクセスは実行されません。キャッシュはメインメモリより高速であるため、アクセスパターンは重要です。

もちろん、書き込みアクセス/読み取りアクセス、書き込みポリシー（書き込みスルー、ライトバック/ライトアロケート、書き込み割り当てなし）、マルチレベルキャッシュなど、より多くの要素を考慮する必要があります。しかし、それはこの質問のために過度のようです。

cachegrindのようなプロファイリングツールで楽しくお楽しみください。

たとえば、4MBの行列にアクセスするダミープログラムを考えてみましょう。各アクセスパターンのミス率の違いを確認してください。

アレイが、それは重要ではない小さい場合列アクセス

$ cat col_major.c 
#include <stdio.h> 

int main(){ 

    size_t i,j; 

    const size_t dim = 1024 ; 

    int matrix [dim][dim]; 

    for (i=0;i< dim; i++){ 
     for (j=0;j <dim;j++){ 
      matrix[j][i]= i*j; 
     } 
    } 
    return 0; 
} 

$ valgrind --tool=cachegrind ./col_major 

==3228== D refs:  10,548,665 (9,482,149 rd + 1,066,516 wr) 
==3228== D1 misses:  1,049,704 (  968 rd + 1,048,736 wr) 
==3228== L2d misses:  1,049,623 (  893 rd + 1,048,730 wr) 
==3228== D1 miss rate:  9.9% (  0.0%  +  98.3% ) 
==3228== L2d miss rate:  9.9% (  0.0%  +  98.3% ) 

行アクセス

$ cat row_major.c 
#include <stdio.h> 

int main(){ 
    size_t i,j; 
    const size_t dim = 1024 ; 
    int matrix [dim][dim]; 

    for (i=0;i< dim; i++) 
     for (j=0;j <dim;j++) 
      matrix[i][j]= i*j; 

    return 0; 
} 

$ valgrind --tool=cachegrind ./row_major 

==3524== D refs:  10,548,665 (9,482,149 rd + 1,066,516 wr) 
==3524== D1 misses:  66,664 (  968 rd + 65,696 wr) 
==3524== L2d misses:  66,583 (  893 rd + 65,690 wr) 
==3524== D1 miss rate:  0.6% (  0.0%  +  6.1% ) 
==3524== L2d miss rate:  0.6% (  0.0%  +  6.1% ) 

Answer 2

。それらが大きければ、読み込み時間に影響が出る可能性があります。大きな問題はキャッシュです。完全な行列がキャッシュに一度にロードされることを期待できない場合は、キャッシュミスの処理に比較的時間がかかるため、遭遇するキャッシュミスの数を最小限に抑えたいと考えています。

アレイが本当に大きい場合は、必要以上にページをスワップすることで、パフォーマンスがさらに低下する可能性があります。 Cについては

Answer 3

、多次元配列を処理するための最良の方法は次のとおりです。このため

int a[MAX_I][MAX_J]; 
for (i = 0; i < MAX_I; ++i) { 
    for (j = 0; j < MAX_J; ++j) { 
     /* process a[i][j] */ 
    } 
} 

理由は、C言語で参照、オフセットを持つポインタとして配列を扱うことです：The C Programming Language。