12

CPUキャッシュ（参照の局所性の恩恵を受けることが知られている）をより有効に活用することに関して、何がより効率的であるかを長い間疑問に思っていました-それぞれが同じ数学的な数値のセットを繰り返し、それぞれが異なる本文ステートメントを持つ2つのループ（たとえば、セットの各要素の関数を呼び出す）、または2つ（またはそれ以上）のbodyステートメントと同等のbodyを持つ1つのループを持つ。すべてのループの後、同じアプリケーション状態を想定しています。

私の意見では、ループで使用される命令とデータがキャッシュに収まるため、ループが2つあると、キャッシュミスとエビクションが少なくなります。私は正しいですか？

仮定：

  1. ループのコストと比較してf、呼び出しのコストはごくわずかです。g

  2. fキャッシュの大部分をそれぞれ単独でg使用するため、キャッシュが次々に呼び出されたときにキャッシュが流出します（シングルループバージョンの場合）

  3. Intel Core Duo CPU

  4. C言語のソースコード

  5. GCCコンパイラ、「余分なスイッチなし」

可能であれば、「時期尚早の最適化は悪」という性格以外の答えが欲しい。

私が提唱している2ループバージョンの例：

int j = 0, k = 0;

for(int i = 0; i < 1000000; i++)
{
    j += f(i);
}

for(int i = 0; i < 1000000; i++)
{
    k += g(i);
}
4

7 に答える 7

10

測定することは知ることです。

于 2010-07-23T20:51:26.370 に答える
6

直感的には、1つのループの方が優れています。インクリメントiする回数が100万回少なくなり、他のすべての操作カウントは同じままです。

一方、それは完全にとに依存しfますg。両方が十分に大きいため、使用するコードまたはキャッシュ可能なデータのそれぞれが重要なキャッシュをほぼ埋め尽くす場合は、それらを交換するfとg、単一のループの利点が完全に失われる可能性があります。

あなたが言うように：それは異なります。

于 2010-07-23T21:15:49.973 に答える
6

私は3つの変数を見ることができます（一見単純なコードのチャンクでも）：

  • 何をしf()、何をg()しますか？それらの1つはすべての命令キャッシュラインを無効にすることができますか（事実上他の1つを押し出します）？それはL2命令キャッシュでも起こり得ますか（ありそうもない）？次に、それらの1つだけをその中に保持することが有益である可能性があります。注：次の理由により、逆は「単一のループがある」ことを意味しません。
  • によると、大量のデータを実行f()および操作しますか？次に、それらが同じデータセットで動作するかどうかを知っておくと便利です。ここでも、2つの異なるセットで動作すると、キャッシュミスによって問題が発生するかどうかを検討する必要があります。g()i
  • あなたが最初に述べたように、f()そしてg()実際にその原始的であり、コードサイズと実行時間およびコードの複雑さの両方を想定している場合、キャッシュの局所性の問題は、このようなコードの小さなチャンクでは発生しません-あなたの最大の懸念は他のいくつかのプロセスは、実際に実行する作業でスケジュールされ、プロセスが実行される番になるまですべてのキャッシュを無効にしました。

最後の考え：上記のようなプロセスがシステムでまれに発生する可能性があることを考えると（そして私は「まれ」を非常に自由に使用しています）、両方の関数をインラインにして、コンパイラーにループを展開させることを検討できます。これは、命令キャッシュの場合、L2にフォールトバックすることは大したことではなくi, j, k、そのループで含まれる単一のキャッシュラインが無効になる可能性はそれほどひどく見えないためです。ただし、そうでない場合は、さらに詳細が役立つでしょう。

于 2010-07-24T06:51:45.773 に答える
2

あなたの質問は、リモートで正確な答えを出すのに十分明確ではありませんが、私はあなたがどこに向かっているのか理解していると思います。反復するデータは十分に大きいため、最後に到達する前にデータの削除を開始するため、2回目（2番目のループ）に反復する場合は、すべてではないにしても一部を再度読み取る必要があります。

2つのループが結合され、各要素/ブロックが最初の操作でフェッチされ、2番目の操作ですでにキャッシュにある場合、2番目の操作のすべてではないにしても、データがキャッシュに対してどれだけ大きいかに関係なく、キャッシュからデータを取得します。

キャッシュの性質、データによってループが削除されてからフェッチされてデータが削除されるなど、さまざまなことが2番目の操作でミスを引き起こす可能性があります。オペレーティングシステムを搭載したPCでは、他のプログラムがタイムスライスを取得すると、多くの立ち退きが発生します。ただし、理想的な世界を想定すると、データのインデックスiに対する最初の操作でメモリからフェッチされ、2番目の操作でキャッシュから取得されます。

キャッシュの調整はせいぜい困難です。私は定期的に、組み込みシステムでも、割り込みがなく、単一のタスクで、同じソースコードであることを示しています。実行時間/パフォーマンスは、コンパイラ最適化オプションの変更、コンパイラの変更、コンパイラの両方のブランドまたはコンパイラのバージョン、gcc 2.x vs 3.x vs 4.x（gccは必ずしも新しいバージョンでより高速なコードを生成するわけではありません）によって劇的に変化する可能性があります）（そして、多くのターゲットでかなり優れているコンパイラは、特定の1つのターゲットでは実際には優れていません）。同じコードの異なるコンパイラまたはオプションは、実行時間を数倍、3倍、10倍など変更できます。キャッシュの有無にかかわらずテストを開始すると、さらに興味深いものになります。スタートアップコードに単一のnopを追加して、プログラム全体が1つの命令をメモリ内に移動し、キャッシュラインがさまざまな場所でヒットするようにします。同じコンパイラ同じコード。これを2つのnop、3つのnopなどで繰り返します。同じコンパイラ、同じコードで、（そのコンパイラを使用してそのターゲットでその日に実行したテストの場合）数十パーセントの違いが見られます。これは、キャッシュを調整できないことを意味するのではなく、調整が助けになっているのか、それとも傷ついているのかを理解しようとするのが難しいことを意味します。通常の答えは「時間を計って見る」だけですが、それはもう機能しません。その日、そのコンパイラを使用したそのプログラムを使用すると、コンピュータで素晴らしい結果が得られる可能性があります。しかし、明日は自分のコンピューターで、または他の誰かのコンピューターでは、物事を速くするのではなく遅くする可能性があります。

私があなたの質問を正しく理解したと仮定すると、私はシングルループがおそらく一般的に速いと思います。

于 2010-07-24T05:55:59.433 に答える
2

ループを小さなチャンクに分割することをお勧めします。これにより、キャッシュヒット率が大幅に向上し、パフォーマンスに大きな違いが生じる可能性があります...

あなたの例から：

int j = 0, k = 0;

for(int i = 0; i < 1000000; i++)
{
    j += f(i);
}

for(int i = 0; i < 1000000; i++)
{
    k += g(i);
}

次のように、2つのループを1つのループに融合します。

int j = 0, k = 0;

for(int i = 0; i < 1000000; i++)
{
    j += f(i);
    k += g(i);
}

これが不可能な場合は、ループタイリングと呼ばれる最適化を行います。

#define TILE_SIZE 1000 /* or whatever you like - pick a number that keeps   */
                       /* the working-set below your first level cache size */

int i=0; 
int elements = 100000;

do {
  int n = i+TILE_SIZE; 
  if (n > elements) n = elements;

  // perform loop A
  for (int a=i; a<n; a++)
  {
    j += f(i);
  }

  // perform loop B
  for (int a=i; a<n; a++)
  {
    k += g(i);
  }

  i += n
} while (i != elements)

ループタイリングの秘訣は、ループがアクセスパターンを共有している場合、2番目のループ本体が最初のループ本体によってキャッシュに既に読み込まれたデータを再利用する機会があることです。キャッシュがこのすべてのデータを保持するのに十分な大きさではないため、ループAを100万回実行した場合、これは発生しません。

ループを小さなチャンクに分割し、それらを次々に実行すると、ここで大いに役立ちます。秘訣は、メモリのワーキングセットを第1レベルのキャッシュのサイズ未満に制限することです。私はキャッシュの半分のサイズを目指しているので、その間に実行される他のスレッドは私のキャッシュをそれほど混乱させません。

于 2010-07-25T22:07:32.073 に答える
1

説明的なコメントのないコードで2ループバージョンに出くわした場合、プログラマーがなぜそのようにしたのか疑問に思い、おそらくテクニックが疑わしい品質であると考えますが、1ループバージョンは驚くことではありませんが、コメントしたかどうか。

しかし、「CPU YのキャッシュでX％速く実行されるため、2つのループを使用しています」などのコメントとともに、2ループのバージョンに出くわした場合、少なくともコードに戸惑うことはありません。それが真実であり、他のマシンに適用できるかどうかはまだ疑問です。

于 2010-07-24T06:22:58.387 に答える
-1

これはコンパイラーが最適化できるもののように思われるので、自分で理解して高速化するのではなく、コードをより明確で読みやすくする方法を使用してください。本当に知っておく必要がある場合は、アプリケーションが使用する入力サイズと計算タイプの両方の方法の時間を計ります（現在のコードを試してください。ただし、計算を何度も繰り返し、最適化を無効にしてください）。

于 2010-07-23T20:38:06.073 に答える