Cでのアルゴリズム比較、違いは何ですか？

Question

#define IMGX 8192 
#define IMGY 8192 
int red_freq[256]; 
char img[IMGY][IMGX][3]; 

main(){ 

int i, j; 
    long long total; 
    long long redness; 

    for (i = 0; i < 256; i++) 
    red_freq[i] = 0; 

    for (i = 0; i < IMGY; i++) 
    for (j = 0; j < IMGX; j++) 
     red_freq[img[i][j][0]] += 1; 

    total = 0; 
    for (i = 0; i < 256; i++) 
    total += (long long)i * (long long)red_freq[i]; 

    redness = (total + (IMGX*IMGY/2))/(IMGX*IMGY); 

あなたは同じままされている他の

for (j = 0; j < IMGX; j++) 
    for (i = 0; i < IMGY; i++) 
     red_freq[img[i][j][0]] += 1; 

すべてにループする第二を交換し、なぜ最初のアルゴリズムはその後、第2のアルゴリズムよりも高速です違いは何ですか？

メモリ割り当てと関係がありますか？

Answer 1

最初のバージョンでは、メモリが順番に変更されるため、プロセッサキャッシュが最適に使用されます。 2番目のバージョンでは、ロードする各キャッシュラインから1つの値が使用されるため、キャッシュの使用には不向きです。

理解するポイントは、キャッシュが行に分割され、それぞれが全体の構造に多くの値を含むことです。

第1のバージョンは、より高速なより巧妙な命令（SIMD命令）を使用するようにコンパイラによって最適化されることもあります。

Answer 2

これは、物理的にレイアウトされた順番で最初のバージョンがメモリを繰り返し、2番目のバージョンが配列の1つの列から次のメモリにジャンプしているためです。これにより、キャッシュのスラッシングが発生し、CPUの最適なパフォーマンスが妨げられ、キャッシュが何度も更新されるのを待つのに多くの時間を費やさなければなりません。

Answer 3

はい、メモリの割り当てと関係があります。最初のループは、imgという内部ディメンションを索引付けします。このディメンションは、たびに3バイトに及ぶだけです。それは1つのメモリページ内に簡単にあります（私はここで共通のサイズは1ページあたり4KBです）。しかし、2番目のバージョンでは、外寸のインデックスが速く変化します。これにより、はるかに広い範囲のメモリ、つまりsizeof (char[IMGX][3])バイト（24kB）にメモリの読み取りが広がります。内側のインデックスが変更されるたびに、それらのジャンプが再び発生します。それは別のページにヒットし、おそらくいくらか遅いでしょう。また、私はCPUが先読みメモリを聞いた。これにより、最初のバージョンのメリットが得られます。これは、読み込み時にデータが既にキャッシュに存在している可能性があるためです。私は、2番目のバージョンがそれを享受していないと想像することができます。なぜなら、これらの大きなジャンプをメモリの周りを前後に移動させるからです。

私はその違いはあまりないと思うでしょうが、アルゴリズムが何度も実行されると、最終的に目立つようになります。ウィキペディアの記事Row-major Orderを読んでみてください。これは、Cで多次元配列を格納するためのスキームです。

Answer 4

メモリがどのようにレイアウトされているかによって、最初のバージョンではデータの局所性が維持され、キャッシュミスが少なくなります。

Answer 5

最近の大きなプロセッサアーキテクチャ（PCのものなど）は、最近アクセスしたメモリに「近く」（アドレス関連の用語では）近いメモリで動作するように大量に最適化されているからです。実際の物理メモリへのアクセスは、CPUが理論的に実行できる速度よりはるかに遅いため、プロセスを最も効率的にアクセスするためのすべてがパフォーマンスに役立ちます。

それ以上に一般化することはかなり不可能ですが、「参照の地域」は目指すべき良いことです。

Answer 6

メモリアロケーションは一度だけ起こり、最初にありますので理由はありません。ランタイムがアドレスをどのように計算するのかが理由です。両方の場合において、メモリアドレスが

(i * (IMGY * IMGX)) 

ので、第2のアルゴリズム

(i * (IMGY * IMGX)) gets calculates 8192 * 8192 times 
(j * IMGX) gets calculated 8192 times 

に最初アルゴリズム

(i * (IMGY * IMGX)) gets calculates 8192 times 
(j * IMGX) gets calculated 8192 * 8192 times 

に

(i * (IMGY * IMGX)) + (j * IMGX) + 0 

として計算されること、2回の乗算を必要としますそれ より多くの時間がかかります。それは理由です