6

私は C シミュレーションをコーディングしています。検証する一連のルールが与えられた場合、それを「スライス」に分割し、各スライスを検証します。(基本的な考え方は、順序が重要であり、ルールの実際の意味はその上にあるいくつかのルールの影響を受けるということです。各ルールと、その上にある重複するルールのみで「スライス」を作成できます。通常、シーケンス全体よりもはるかに小さいスライスです。)

私の問題は次のとおりです。

構造体 (ルール) の配列と int (長さ) を含む構造体 (ポリシー) があります。私の元の実装では、malloc と realloc を自由に使用していました。

struct{
  struct rule *rules;
  int length;
}policy;
...
struct policy makePolicy(int length)
{
  struct policy newPolicy;
  newPolicy.rules = malloc(length * sizeof(struct rule));
  newPolicy.length = length;
  return newPolicy;
}
...
struct policy makeSlice(struct policy inPol, int rulePos)
{
  if(rulePos > inPol.length - 1){
    printf("Slice base outside policy \n");
    exit(1);
   }
  struct slice = makePolicy(inPol.length);
  //create slice, loop counter gets stored in sliceLength
  slice.rules = realloc(slice.rules, sliceLength * sizeof(struct rule));
  slice.length = sliceLength;
  return slice;
}

これはmallocされたメモリを使用するため、ヒープを大量に使用すると想定しています。現在、malloc を持たない実験的な並列マシンに移植しようとしています。

悲しいことに、固定サイズの配列ですべてを割り当てました。

ここでショッカーです。

新しいコードの実行は遅くなります。はるかに遅い。

(元のコードは、スライスの長さが 200 のときは数分、300 を超えるとおそらく 1 時間待機していました。 120 と言いますが、まだ 200 ではありません。)

唯一のことは、スライスに完全なポリシー (MAXBUFLEN が 10000) と同じメモリが割り当てられていることですが、全体でメモリが不足しているようには見えません。'top' は、以前と同様に、消費されたメモリの合計が非常に控えめで、数十メガバイトの範囲であることを示しています。(そしてもちろん、長さを保存しているので、全体をループするのではなく、実際のルールのある部分だけをループします。)

なぜ突然遅くなったのか、誰か説明してもらえませんか？

4

1 に答える 1

3

構造体のサイズをより大きなサイズ (たとえば 10000 ルール) に修正すると、キャッシュの局所性が元のものよりもはるかに悪くなる可能性があるようです。プロファイラー (Valgrind の oprofile または cachegrind) を使用して、キャッシュに問題があるかどうかを確認できます。

元のプログラムでは、1 つのキャッシュ ラインは最大で 8 つを保持できますstruct policy(64 バイトのキャッシュ ラインを備えた 32 ビット マシン上)。しかし、変更されたバージョンでは、キャッシュ ラインのサイズよりもはるかに大きいため、1 つしか保持できません。

この場合、フィールドを上に移動するとlengthパフォーマンスが向上します。これはlength、最初の数struct rule秒が 1 つのキャッシュ ラインに収まるようになったためです。

struct policy{
  int length;
  struct rule rules[10000];
};

この問題を解決するには、独自のカスタム アロケータを記述して、キャッシュの局所性を確保する必要があります。このプログラムの並列バージョンを作成している場合は、キャッシュ ラインの競合を避けるために、異なるスレッドが使用するメモリを異なるキャッシュ ラインに分離することも忘れないでください。

于 2013-05-29T08:31:46.897 に答える