3 
#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);

2番目のforループをに置き換えるときの違いは何ですか

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

他のすべては同じままで、なぜ最初のアルゴリズムが2番目のアルゴリズムよりも速いのですか？

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

4

6 に答える 6

8

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

理解しておくべきポイントは、キャッシュが行に分割されており、各行には構造全体に多くの値が含まれているということです。

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

于 2009-03-29T20:07:01.767 に答える
5

これは、最初のバージョンが物理的に配置された順序でメモリを反復処理し、2番目のバージョンがメモリ内で配列の1つの列から次の列にジャンプしているためです。これにより、キャッシュのスラッシングが発生し、CPUの最適なパフォーマンスが妨げられ、キャッシュが何度も更新されるのを待つために多くの時間を費やす必要があります。

于 2009-03-29T20:06:32.110 に答える
2

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

それ以上に一般化することはほとんど不可能ですが、「参照の局所性」を目指すのは良いことです。

于 2009-03-29T20:07:46.647 に答える
1

メモリのレイアウト方法により、最初のバージョンはデータの局所性を維持するため、キャッシュミスが少なくなります。

于 2009-03-29T20:07:31.623 に答える
1

メモリ割り当ては1回だけ発生し、最初に発生するため、理由にはなりません。その理由は、ランタイムがアドレスを計算する方法です。どちらの場合も、メモリアドレスは次のように計算されます。

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

最初のアルゴリズムでは

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

2番目のアルゴリズムでは

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

以来

(i * (IMGY * IMGX))

2つの乗算が含まれ、それを行うにはより多くの時間がかかります。それが理由です

于 2009-03-29T20:16:32.537 に答える
0

はい、それはメモリ割り当てと関係があります。最初のループは、の内部ディメンションにインデックスを付けます。これはimg、毎回3バイトにしか及ばないことがあります。これは1つのメモリページ内に簡単に収まります（ここでの一般的なサイズは1ページで4kBだと思います）。ただし、2番目のバージョンでは、外部ディメンションのインデックスが急速に変化します。これにより、メモリの読み取りがはるかに広い範囲のメモリに分散されます。sizeof (char[IMGX][3])バイト、つまり24kB。そして、内部インデックスが変更されるたびに、それらのジャンプが再び発生し始めます。それは別のページにヒットし、おそらく多少遅くなります。また、CPUが先読みメモリを読み取ると聞きました。これにより、最初のバージョンのメリットが得られます。これは、読み取り時に、そのデータがおそらくすでにキャッシュにあるためです。2番目のバージョンは、メモリを前後に大きくジャンプするため、そのメリットがないことを想像できます。

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

于 2009-03-29T20:07:23.777 に答える